首页 > 代码库 > VOJ 1067 Warcraft III 守望者的烦恼 (矩阵快速幂+dp)
VOJ 1067 Warcraft III 守望者的烦恼 (矩阵快速幂+dp)
题目链接
显然可知
dp[n] = dp[n-k] + dp[n-k+1] + ... +dp[n-1];
然后要用矩阵来优化后面的状态转移。
也就是矩阵
0 1 0 0 a b
0 0 1 0 * b = c
0 0 0 1 c d
1 1 1 1 d a+b+c+d
然后跑快速幂
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #define N 10 using namespace std; const int mod = 7777777; typedef long long LL; struct matrix { LL a[10][10]; }origin; int n,m; matrix multiply(matrix x,matrix y) { matrix temp; memset(temp.a,0,sizeof(temp.a)); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { for(int k=0;k<n;k++) { temp.a[i][j]+=x.a[i][k]*y.a[k][j]; temp.a[i][j]=(temp.a[i][j])%mod; } } } return temp; } matrix matmod(matrix A,int k) { matrix res; memset(res.a,0,sizeof res.a); for(int i=0;i<n;i++)res.a[i][i]=1; while(k) { if(k&1) res=multiply(res,A); k>>=1; A=multiply(A,A); } return res; } void print(matrix x) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) cout<<" "<<x.a[i][j]; puts(""); } printf("---------------\n"); } int main() { int k; while(cin>>n>>k) { memset(origin.a,0,sizeof origin.a); origin.a[0][0]=1; for(int i=1;i<=n;i++) { origin.a[i][0]=1; for(int j=0;j<i;j++) { origin.a[i][0]+=origin.a[j][0]; } } // print(origin); matrix res; memset(res.a,0,sizeof res.a); for(int i=0;i<n-1;i++) { res.a[i][i+1]=1; } for(int i=0;i<n;i++)res.a[n-1][i]=1; //print(res); res=matmod(res,k-1); LL fans=0; for(int i=0;i<n;i++) { fans+=res.a[0][i]*origin.a[i][0]; fans%=mod; } cout<<fans<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。