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;
}