C11CAL - Tính toán

Tác giả: RR

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <complex>

#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(i,a) for(int i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back
using namespace std;

const long long BASE = 1000000007LL;

struct Poly {
    int deg;
    long long a[55];

    Poly multX() {
        Poly res;
        res.deg = deg + 1;
        memset(res.a, 0, sizeof res.a);
        FORD(i,res.deg,1)
            res.a[i] = a[i-1];
        return res;
    }

    Poly operator + (Poly p) {
        Poly res;
        res.deg = max(p.deg, deg);
        memset(res.a, 0, sizeof res.a);

        FOR(i,0,res.deg) {
            res.a[i] = (p.a[i] + a[i]) % BASE;
        }
        return res;
    }

    Poly operator - (Poly p) {
        Poly res;
        res.deg = max(p.deg, deg);
        memset(res.a, 0, sizeof res.a);

        FOR(i,0,res.deg) {
            res.a[i] = (a[i] + BASE - p.a[i]) % BASE;
        }
        return res;
    }

    Poly operator * (long long x) {
        Poly res;
        res.deg = deg;
        memset(res.a, 0, sizeof res.a);

        FOR(i,0,res.deg) {
            res.a[i] = (a[i] * x) % BASE;
        }
        return res;
    }

    void print() {
        FOR(i,0,deg) cout << a[i] << ' '; cout << endl;
    }
} f[55];

long long power(long long x, int k) {
    if (k == 0) return 1;
    if (k == 1) return x % BASE;
    long long mid = power(x, k >> 1);
    mid = (mid * mid) % BASE;
    if (k & 1) return (mid * x) % BASE;
    else return mid;
}

long long inverse(long long x) {
    return power(x, BASE - 2);
}

void init() {
    f[0].deg = 1;
    f[0].a[0] = 0;
    f[0].a[1] = 1;

    f[1].deg = 2;
    f[1].a[0] = 0;
    f[1].a[1] = inverse(2);
    f[1].a[2] = inverse(2);

    FOR(k,2,50) {
        f[k] = f[k-1].multX() + f[k-1];
        FOR(i,0,k-1) {
            f[k] = f[k] - f[i] * f[k-1].a[i];
        }
        f[k] = f[k] * inverse((f[k-1].a[k] + 1) % BASE);
    }
}

long long n, k;

int main() {
    init();
    while (cin >> n >> k) {
        long long res = 0;
        long long pN = 1;
        FOR(i,0,k+1) {
            res = (res + f[k].a[i] * pN) % BASE;
            pN = (n * pN) % BASE;
        }
        cout << res << endl;
    }
    return 0;
}

Download