首页 > 代码库 > 守望者的烦恼
守望者的烦恼
OJ P1352
这道题是个很浅显的DP，根据题意我们可以得到状态转移方程：
这个方程很简单，复杂度是的，这个复杂度在这道题下显然是不可接受的。考虑优化DP方程，继续观察这个DP方程，我们发现在K=2时其本质就是斐波那契数列，所有考虑斐波那契数列的优化方法：矩阵乘法
我们设这个矩阵为A，那么显然可以得到以下的关系
那么只要可以得到A，我们就能在的复杂度内完成此题
下面给出矩阵A,具体的推理过程我也不知道
然后用快速幂优化,最后就是本题答案。
1 //OJ 1352 2 //by Cydiater 3 //2016.8.28 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 #include <string> 8 #include <algorithm> 9 #include <queue>10 #include <map>11 #include <ctime>12 #include <cmath>13 #include <cstdlib>14 #include <iomanip>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(int i=j;i<=n;i++)18 #define down(i,j,n) for(int i=j;i>=n;i--)19 const int oo=0x3f3f3f3f;20 const int mod=7777777;21 inline ll read(){22 char ch=getchar();ll x=0,f=1;23 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}24 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}25 return x*f;26 }27 ll N,K;28 struct matrix{29 ll num[15][15];30 void build(){31 memset(num,0,sizeof(num));32 up(i,1,K)num[i][1]=1;33 up(i,2,K)num[i-1][i]=1;34 }35 }ans;36 namespace solution{37 matrix mul(matrix a,matrix b){38 matrix c;39 memset(c.num,0,sizeof(c.num));40 up(i,1,K)up(j,1,K)up(k,1,K){41 c.num[i][j]+=a.num[i][k]*b.num[k][j];42 c.num[i][j]%=mod;43 }44 return c;45 }46 matrix quick_pow(ll p){47 matrix a;a.build();48 matrix b;49 memset(b.num,0,sizeof(b));50 up(i,1,K)b.num[i][i]=1;51 while(p){52 if(p&1)b=mul(b,a);53 p>>=1;54 a=mul(a,a);55 }56 return b;57 }58 void init(){59 K=read();N=read();60 }61 void slove(){62 ans=quick_pow(N);63 cout<<ans.num[1][1]<<endl;64 }65 }66 int main(){67 //freopen("input.in","r",stdin);68 using namespace solution;69 init();70 slove();71 return 0;72 }
守望者的烦恼
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。