Description
热情好客的请森林中的朋友们吃饭，他的朋友被编号为 1～N，每个到来的朋友都会带给他一些礼物：。其中，第一个朋友会带给他 1 个，之后，每一个朋友到来以后，都会带给他之前所有人带来的礼物个数再加他的编号的 K 次方那么多个。所以，假设 K=2，前几位朋友带来的礼物个数分别是：1,5,15,37,83假设 K=3，前几位朋友带来的礼物个数分别是：1,9,37,111现在，好奇自己到底能收到第 N 个朋友多少礼物，因此拜托于你了。已知 N,K请输出第 N 个朋友送的礼物个数 mod1000000007。
Input
第一行，两个整数 N,K
N≤10^18,K≤10
Output
一个整数，表示第 N 个朋友送的礼物个数 mod1000000007。
Sample Input
4 2
Sample Output
37
正解：矩阵快速幂。
首先一眼就能看出这题要用矩阵快速幂。
然后发现我们需要维护的就是$i^{k}$，不过$k$最大只有$10$。
于是根据二项式定理，写一个杨辉三角就行了。
1 #include <bits/stdc++.h> 2 #define il inline 3 #define RG register 4 #define ll long long 5 #define rhl (1000000007) 6 7 using namespace std; 8 9 struct data{ int m[15][15]; }a,p; 10 11 int c[15][15],k,sz; 12 ll n; 13 14 il data mul(data a,data b){ 15 data c; 16 for (RG int i=0;i<=sz;++i) 17 for (RG int j=0;j<=sz;++j){ 18 c.m[i][j]=0; 19 for (RG int k=0;k<=sz;++k){ 20 c.m[i][j]+=1LL*a.m[i][k]*b.m[k][j]%rhl; 21 if (c.m[i][j]>=rhl) c.m[i][j]-=rhl; 22 } 23 } 24 return c; 25 } 26 27 il data qpow(data a,RG ll b){ 28 data ans=a; --b; 29 while (b){ 30 if (b&1) ans=mul(ans,a); 31 a=mul(a,a),b>>=1; 32 } 33 return ans; 34 } 35 36 int main(){ 37 #ifndef ONLINE_JUDGE 38 freopen("gift.in","r",stdin); 39 freopen("gift.out","w",stdout); 40 #endif 41 cin>>n>>k,c[0][0]=1; 42 for (RG int i=1;i<=k;++i){ 43 c[i][0]=c[i][i]=1; 44 for (RG int j=1;j<i;++j) c[i][j]=(c[i-1][j-1]+c[i-1][j])%rhl; 45 } 46 for (RG int i=0;i<=k;++i) 47 for (RG int j=0;j<=i;++j) p.m[j][i]=c[i][j]; 48 sz=k+2,p.m[k+1][k+1]=p.m[k+2][k+1]=1; 49 p.m[k][k+2]=p.m[k+1][k+2]=p.m[k+2][k+2]=1,p=qpow(p,n); 50 for (RG int i=0;i<=k;++i) a.m[1][i]=1; a=mul(a,p); 51 cout<<a.m[1][sz]; return 0; 52 }