首页 > 代码库 > Codeforces 176B (线性DP+字符串)
Codeforces 176B (线性DP+字符串)
题目链接: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=28214
题目大意:源串有如下变形:每次将串切为两半,位置颠倒形成新串。问经过K次变形后,与目标串相同的变形方案数。mod 1000000007。
解题思路:
奇葩的字符串DP。照着别人的题解写的,解释不出原理是什么。
首先统计出经过1次变形,就能和目标串相同的中间产物串(包含源串)的个数cnt。len表示源串长度,那么len-cnt就表示和目标串不同的个数。
用dp[i][0]表示第i步变形后,与目标串相同方案数,dp[i][1]则表示不同的方案数,
那么对于每次变形i:
dp[i][0]=dp[i-1][0]*(cnt-1)+dp[i-1][1]*cnt
dp[i][1]=dp[i-1][0]*(len-cnt)+dp[i-1][1]*(len-cnt-1)
-1的原因是本次变形要去掉自身变为自身的情况。
那么最后ans=dp[k][0]。
由于是线性DP,可以滚动数组优化内存,只要2*2空间就行了。
#include "cstdio"#include "cstring"#define maxn 2010#define mod 1000000007#define LL long longchar s[maxn],e[maxn];LL dp[2][2],k,cnt=0,len;int main(){ //freopen("in.txt","r",stdin); scanf("%s%s%I64d",&s,&e,&k); len=strlen(s); for(int i=0;i<len;i++) { s[i+len]=s[i]; if(!strncmp(s+i,e,len)) cnt++; } dp[0][strncmp(s,e,len)!=0]=1; for(int i=1;i<=k;i++) { dp[i%2][0]=(dp[(i-1)%2][0]*(cnt-1)+dp[(i-1)%2][1]*cnt)%mod; dp[i%2][1]=(dp[(i-1)%2][0]*(len-cnt)+dp[(i-1)%2][1]*(len-cnt-1))%mod; } printf("%I64d\n",dp[k%2][0]);}
2913373 | neopenx | CodeForces | 176B | Accepted | 30 | GNU C++ 4.6 | 602 | 2014-10-31 20:00:42 |
Codeforces 176B (线性DP+字符串)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。