Description
给出 (n,k) ，求出：
[sum_{i=1}^{n} f_i·i^k
]
其中 (f_i) 表示斐波拉契第 (i) 项。(nle 10^{18},kle 40) 。
Solution
哎，被这个 (kle 40) 误导了，以为是斯特林数。/kk
发现假如我们用矩阵表示 (f_i)，那么我们就只需要求出：
[sum_{i=1}^{n} G^ii^k
]
其中 (G=egin{bmatrix}1 & 1\ 1 & 0end{bmatrix}) 。
考虑倍增，设 (f(n,m)=sum_{i=1}^{n} G^ii^m)，则有：
[f(2n,m)=f(n,m)+G^nsum_{h=0}^{m} n^hinom{m}{h}f(n,m-h)
]
然后我们就可以做到 (Theta(k^2log n)) 了，不过似乎分治的时候用 ( ext{fft}) 的话可以做到 (Theta(klog klog n))，不过这个题中 (k) 不是很大，所以可以接受。
（矩阵的 ( ext{fwt}) 可以对于每一项搞）
Code
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define mod 1000000007
#define int long long
#define MAXN 45
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> inline void chkmax (T &a,T b){a = max (a,b);}
template <typename T> inline void chkmin (T &a,T b){a = min (a,b);}
int k,C[MAXN][MAXN];
int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}
void Add (int &a,int b){a = add (a,b);}
void Sub (int &a,int b){a = dec (a,b);}
struct matrix{
int mat[2][2];
matrix(){memset (mat,0,sizeof (mat));}
int * operator [] (const int key){return mat[key];}
matrix operator * (const matrix &p)const{
matrix now;
for (Int i = 0;i < 2;++ i)
for (Int j = 0;j < 2;++ j)
for (Int k = 0;k < 2;++ k)
Add (now.mat[i][k],mul (mat[i][j],p.mat[j][k]));
return now;
}
matrix operator * (const int &p)const{
matrix now;
for (Int i = 0;i < 2;++ i)
for (Int j = 0;j < 2;++ j)
now.mat[i][j] = mul (mat[i][j],p);
return now;
}
matrix operator + (const matrix &p)const{
matrix now;
for (Int i = 0;i < 2;++ i)
for (Int j = 0;j < 2;++ j)
now.mat[i][j] = add (mat[i][j],p.mat[i][j]);
return now;
}
}one,ret;
struct node{
matrix gn,f[MAXN];
};
node getit (int n){
node now;
if (n == 1){
now.gn = ret;
for (Int i = 0;i <= k;++ i) now.f[i] = ret;
return now;
}
if (n & 1){
node lst = getit (n - 1);
now.gn = lst.gn * ret;
for (Int i = 0,res = 1;i <= k;++ i,res = mul (res,n % mod)) now.f[i] = lst.f[i] + now.gn * res;
}
else{
int mid = n >> 1;
node lst = getit (mid);now.gn = lst.gn * lst.gn;
for (Int m = 0;m <= k;++ m){
now.f[m] = lst.f[m];
for (Int h = 0,res = 1;h <= m;++ h,res = mul (res,mid % mod)) now.f[m] = now.f[m] + (lst.gn * lst.f[m - h]) * mul (res,C[m][h]);
}
}
return now;
}
int n;
signed main(){
read (n,k),one[0][0] = one[1][1] = 1,ret[0][0] = ret[0][1] = ret[1][0] = C[0][0] = 1;
for (Int i = 1;i <= k;++ i){
C[i][0] = 1;
for (Int j = 1;j <= i;++ j) C[i][j] = add (C[i - 1][j - 1],C[i - 1][j]);
}
node now = getit (n);
write (now.f[k][0][0]),putchar ('
');
return 0;
}