К-ичные числа Версия 2

#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <cmath>
#include <math.h>
#include <queue>
#include <stack>
#include <climits>
#include <deque>
#include <ctime>
#include <iterator>

using namespace std;
const int INF = (int)(2e9);

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;

#define mh() make_heap()
#define poph() pop_heap()
#define pushh() push_heap()
#define sor(n) n.begin(), n.end()
#define mp make_pair


#define files freopen("secretroom.in", "rt", stdin); freopen("secretroom.out", "wt", stdout)
const int base = 1000 * 1000 * 1000;
typedef vector<int> lnum;

lnum sum(lnum a, lnum b)
{
    int carry = 0;
    for (size_t i = 0; i<max(a.size(), b.size()) || carry; ++i) {
        if (i == a.size())
            a.push_back(0);
        a[i] += carry + (i < b.size() ? b[i] : 0);
        carry = a[i] >= base;
        if (carry)  a[i] -= base;
    }
    return a;
}

lnum proz(lnum a, lnum b)
{
    lnum c(a.size() + b.size());
    for (size_t i = 0; i<a.size(); ++i)
        for (int j = 0, carry = 0; j<(int)b.size() || carry; ++j) {
            long long cur = c[i + j] + a[i] * 1ll * (j < (int)b.size() ? b[j] : 0) + carry;
            c[i + j] = int(cur % base);
            carry = int(cur / base);
        }
    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
    return c;
}

lnum dec(lnum a, lnum b)
{
    int carry = 0;
    for (size_t i = 0; i<b.size() || carry; ++i) {
        a[i] -= carry + (i < b.size() ? b[i] : 0);
        carry = a[i] < 0;
        if (carry)  a[i] += base;
    }
    while (a.size() > 1 && a.back() == 0)
        a.pop_back();
    return a;
}

lnum perev(ll b)
{
    string s = to_string(b);
    lnum a;
    for (int i = (int)s.length(); i>0; i -= 9)
        if (i < 9)
            a.push_back(atoi(s.substr(0, i).c_str()));
        else
            a.push_back(atoi(s.substr(i - 9, 9).c_str()));
    return a;
}
int main()
{
    ull n, k;
    cin >> n >> k;
    vector<lnum> dpz(n + 1);
    vector<lnum> dpzn(n + 1);

    lnum K = perev(k);
    lnum N = perev(n);
    lnum o = dec(K, perev(1));
    dpz[2] = o;
    dpzn[2] = dec(proz(o,K), o);
    for (int i = 3; i <= n; i++)
    {
        dpz[i] = dpzn[i - 1];
        dpzn[i] = proz(sum(dpz[i - 1], dpzn[i - 1]),o);
    }
    lnum a =sum(dpz[n],dpzn[n]);
    printf("%d", a.empty() ? 0 : a.back());
    for (int i = (int)a.size() - 2; i >= 0; --i)
        printf("%09d", a[i]);
    system("pause");
    return 0;
}