题解 V1067 【Warcraft III 守望者的烦恼】
Warcraft III 守望者的烦恼
题目大意：
现在有 \(n\) 个格子，一次可以跳过 \(k\) 个格子，问跳完所有格子的方案数。
solution：
首先我们想到一个递推：
设 \(f_{i}\) 为到第 \(i\) 个格子的方案数，那么有：
这是个加法原理。
如果朴素去算是 \(O(nk)\) 的，复杂度爆炸。所以我们考虑优化这个递推。
我们发现这个柿子都是按照一定规律加的，即可以用上柿子表达出所有 \(i\) 的取值构成的柿子。所以考虑矩阵优化。
设：
初始矩阵\(\begin{bmatrix} f_{i-1} & f_{i-2} & f_{i-3} \,\,\,\,... & f_{i-k+1} &f_{i-k} \end{bmatrix}\)，
目标矩阵\(\begin{bmatrix} f_{i} & f_{i-1} & f_{i-2} \,\,\,\,... & f_{i-k} &f_{i-k+1} \end{bmatrix}\)。
可构造出一个 \(k\times k\) 的矩阵：
做矩阵快速幂即可。
细节处理：
- 我们需要初始化一下，即 \(f_0\) 的值应为 \(1\) ，在矩阵中即为 \(res_{1,1}=1\) 。
- 取模的数挺奇怪的，建议复制粘贴。
代码
#include
#include
using namespace std;
typedef long long LL;
const int K=15,p=7777777;
int k,n;
struct M {
LL c[K][K];
}a,res;
M operator * (const M &x,const M &y){
M t;
memset(t.c,0,sizeof(t.c));
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
for(int o=1;o<=k;o++)
t.c[i][j]=(t.c[i][j]+x.c[i][o]*y.c[o][j]%p)%p;
return t;
}
inline void qpow(int b){
while(b){
if(b&1) res=res*a;
a=a*a;
b>>=1;
}
printf("%lld",res.c[1][1]);
}
int main(){
scanf("%d%d",&k,&n);
for(int i=1;i<=k;i++)//构造矩阵
a.c[i][1]=a.c[i][i+1]=1;
res.c[1][1]=1;//初始化
qpow(n);
return 0;
}