首页 > 代码库 > 这是一道智障题
这是一道智障题
这是一道智障题
题目链接：http://acm.xidian.edu.cn/problem.php?id=1180
dp+矩阵快速幂
这道题的n为1e18，故复杂度为O(1)或者O(lgn)。比赛的时候只看出了是dp，感觉复杂度太高，没想到用矩阵来优化，gg。
先来定义状态：dp[i][j][k]表示取第i个珠子颜色为j且末尾有k个连续的珠子的总数，
转移方程：
当k=1时，dp[i][j][k]=dp[i-1][不为j的颜色][所有k];
当k！=1时，dp[i][j][k]=dp[i-1][j][k-1].
但是这样一来，无论是时间复杂度还是空间复杂度都过大，必须优化。
考虑到不管j取何值，对于相同的i和k来说，dp[i][j][k]一定相同（对称性），所以dp[i][j][0]=dp[i-1][j][所有k]*(m-1)，
如此，可以构造转移矩阵
matrix=[[m-1,m-1,...,m-1,m-1],[1,0,...,0,0],[0,1,...,0,0],...,[0,0,...,1,0]].
初始状态为[1,0,0,...,0,0]^(-1).
（比较神奇的是，编译的时候遇到了编译器错误：internal compiler error: Segmentation fault，人品简直不要太好= =）
代码如下：
1 #include<cstdio> 2 #include<cstring> 3 #define N 100 4 #define M 23333 5 using namespace std; 6 typedef long long LL; 7 LL n,m,k; 8 struct matrix{ 9 LL mp[N][N];10 matrix mul(matrix A){11 matrix temp;12 for(int i=0;i<k;++i)13 for(int j=0;j<k;++j){14 temp.mp[i][j]=0;15 for(int t=0;t<k;++t){16 LL r=(mp[i][t]*A.mp[t][j])%M;17 temp.mp[i][j]=(temp.mp[i][j]+r)%M;18 }19 }20 return temp;21 }22 };23 matrix pow(matrix E,matrix A,LL n){24 while(n){25 if(n&1)E=E.mul(A);26 A=A.mul(A);27 n>>=1;28 }29 return E;30 }31 matrix e,a;32 int main(void){33 for(int i=0;i<N;++i)e.mp[i][i]=1;34 for(int i=1;i<N;++i)a.mp[i][i-1]=1;35 while(~scanf("%lld%lld%lld",&n,&m,&k)){36 k--;37 for(int i=0;i<k;++i)a.mp[0][i]=m-1;38 matrix temp=pow(e,a,n-1);39 LL ans=0;40 for(int i=0;i<k;++i)ans=(ans+temp.mp[i][0])%M;41 ans=(ans*m)%M;42 printf("%lld\n",ans);43 }44 }
这是一道智障题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。