目录
显示
题目链接
https://www.luogu.com.cn/problem/P5364
题解
乍一看似乎没啥思路,我们来找找规律。
先是第 \(i\) 个数的规律。表格中是各项系数的值。
项 | \(1^k\) | \(2^k\) | \(3^k\) | \(4^k\) | \(5^k\) |
1 | 1 | ||||
2 | 1 | 1 | |||
3 | 2 | 1 | 1 | ||
4 | 4 | 2 | 1 | 1 | |
5 | 8 | 4 | 2 | 1 | 1 |
看起来有些规律,不过似乎不太好表示。
让我们把前 \(i\) 项的和表示一下吧。
项 | \(1^k\) | \(2^k\) | \(3^k\) | \(4^k\) | \(5^k\) |
1 | 1 | ||||
2 | 2 | 1 | |||
3 | 4 | 2 | 1 | ||
4 | 8 | 4 | 2 | 1 | |
5 | 16 | 8 | 4 | 2 | 1 |
到这里似乎豁然开朗了。前 \(i+1\) 项的和,在前 \(i\) 项的和的基础上乘二,并添加了一个新项。
设前 \(i\) 项的和为 \(S_i\),易知:
$$S_i=2S_{i-1}+i^k$$
考虑用矩阵快速幂来加速递推。
原式中的 \(i^k\) 不太好处理,这时候需要用到一点二项式定理的知识来解决。
将 \((i+1)^k\) 展开:
$$(i+1)^k=\sum_{p=0}^k C_k^p i^p$$
从而我们就将 \((i+1)^k\) 拆分成了若干个 \(i^p\) 相加的形式。
在转移矩阵中维护 \(i^0 \sim i^k\) 以及 \(S_i\),就可以以 \(O(k^3 \log n)\) 的时间复杂度通过此题。
#include <cstring> #include <iostream> #define MOD 1000000007 using namespace std; long long n,k; struct mat { long long a[15][15]; mat(int x=0) { memset(a,0,sizeof(a)); for(int i=0;i<=k;i++) a[i][i]=x; } mat operator*(const mat&b)const { mat ans; for(int l=0;l<=k+1;l++) for(int i=0;i<=k+1;i++) for(int j=0;j<=k+1;j++) ans.a[i][j]=(ans.a[i][j]+a[i][l]*b.a[l][j])%MOD; return ans; } }f,g; void init() { //[n^0,n^1,...,n^k,s_0] for(int i=0;i<=k;i++) f.a[0][i]=1; for(int i=0;i<=k;i++) g.a[0][i]=1; for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) g.a[i][j]=g.a[i-1][j-1]+g.a[i][j-1]; g.a[k][k+1]=1,g.a[k+1][k+1]=2; } mat fpow(mat x,long long y) { mat ans(1); while(y) { if(y&1)ans=ans*x; x=x*x; y>>=1; } return ans; } int main() { cin>>n>>k; init(); long long res1=(f*fpow(g,n)).a[0][k+1],res2=(f*fpow(g,n-1)).a[0][k+1]; cout<<(res1-res2+MOD)%MOD<<endl; return 0; }