题目链接：Click here
Solution:
设(f(x))代表第(x)个人送的礼物的数量，(s(x))代表(f(x))的前缀和，即：
[f(x)=s(x-1)+x^k\
s(x)=s(x-1)+f(x)\
s(x)=2 imes s(x-1)+x^k
]
则我们只需求出(s(n-1))即可，(nle1e18)，考虑矩阵快速幂优化(dp)
这里唯一麻烦的就是(x^k)，考虑二项式定理：((x+1)^k=sum_{i=0}^k{kchoose i}x^{k-i})
则我们得到这样的转移：
[left[
egin{matrix}
2&C_k^0&C_k^1&dots &C_k^k\
0&C_k^0&C_k^1&dots &C_k^k\
0&0&C_{k-1}^0&dots &C_{k-1}^{k-1}\
vdots&ddots&dots& &vdots\
0&0&0&dots&C_0^0
end{matrix}
ight]
left[
egin{matrix}
s(x)\
x^k\
x^{(k-1)}\
vdots\
x^0
end{matrix}
ight]
=
left[
egin{matrix}
s(x+1)\
(x+1)^k\
(x+1)^{(k-1)}\
vdots\
(x+1)^0
end{matrix}
ight]
]
Code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,k,c[11][11];
struct Matrix{
int g[12][12],w,h;
void init(){memset(g,0,sizeof(g));}
void org(){for(int i=0;i<12;i++)g[i][i]=1;}
friend Matrix operator *(Matrix a,Matrix b){
Matrix tmp;tmp.w=a.w;tmp.h=b.h;tmp.init();
for(int i=0;i<a.w;i++)
for(int j=0;j<b.h;j++)
for(int k=0;k<a.h;k++)
tmp.g[i][j]=(tmp.g[i][j]+(a.g[i][k]*1ll*b.g[k][j])%mod)%mod;
return tmp;
}
};
Matrix qpow(Matrix a,int b){
Matrix re;re.w=re.h=k+2;
re.init();re.org();
while(b){
if(b&1) re=re*a;
b>>=1;a=a*a;
}return re;
}
int pow(int a,int b){
int re=1;
while(b){
if(b&1) re=(re*1ll*a)%mod;
b>>=1;a=(a*1ll*a)%mod;
}return re;
}
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
signed main(){
n=read(),k=read();
for(int i=0;i<=k;i++) c[i][i]=c[i][0]=1;
for(int i=1;i<=k;i++)
for(int j=1;j<i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
Matrix trans;trans.w=k+2,trans.h=k+2;
trans.init();trans.g[0][0]=2;
for(int i=1;i<=k+1;i++) trans.g[0][i]=c[k][i-1];
for(int i=1;i<=k+1;i++)
for(int j=i;j<=k+1;j++)
trans.g[i][j]=c[k+1-i][j-i];
if(n==1) return puts("1"),0;
trans=qpow(trans,n-2);
Matrix ans;ans.w=k+2;ans.h=1;ans.init();
for(int i=0;i<=k+2;i++) ans.g[i][0]=1;
ans=trans*ans;printf("%lld
",(ans.g[0][0]+pow(n%mod,k))%mod);
return 0;
}