目录
显示
题目链接
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;
}