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 long
char s[maxn],e[maxn];
LL dp[][],k,cnt=,len;
int main()
{
//freopen("in.txt","r",stdin);
scanf("%s%s%I64d",&s,&e,&k);
len=strlen(s);
for(int i=;i<len;i++)
{
s[i+len]=s[i];
if(!strncmp(s+i,e,len)) cnt++;
}
dp[][strncmp(s,e,len)!=]=;
for(int i=;i<=k;i++)
{
dp[i%][]=(dp[(i-)%][]*(cnt-)+dp[(i-)%][]*cnt)%mod;
dp[i%][]=(dp[(i-)%][]*(len-cnt)+dp[(i-)%][]*(len-cnt-))%mod;
}
printf("%I64d\n",dp[k%][]); }
2913373 neopenx CodeForces 176B Accepted   30 GNU C++ 4.6 602
2014-10-31 20:00:42
上一篇:Codeforces 55D (数位DP+离散化+数论)


下一篇:Dubbo相关博文整理