【DP】-Codeforces Round #110 (Div. 1)-C. Cipher

74 阅读 0 评论 49 点赞

我是靠谱客的博主美满小馒头，最近开发中收集的这篇文章主要介绍【DP】-Codeforces Round #110 (Div. 1)-C. Cipher，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

个人觉得很神奇的一道DP……

题目要求求出给出字符串经过题目要求的变换可以得到多少各不同的字符串。可以证明的是，这些字符串加起来的和都一样，所以dp[i][j]的i表示的是字符串的长度，j表示的是字符串所有字母加起来的和，状态转移方程为dp[i+1][j+k]+=dp[i][j]（1<=k<=26).

题目

#include<iostream>
#include<cstdio>
using namespace std;
#define mod 1000000007
int dp[105][2650];
int main()
{
//freopen("a.txt","r",stdin);
int i,j,k,m,n,t;
char s[105];
memset(dp,0,sizeof(dp));
for(dp[0][0]=1,i=0;i<100;i++)
for(j=0;j<=2600;j++)
if(dp[i][j])
{
for(k=1;k<=26;k++)
(dp[i+1][j+k]+=dp[i][j])%=mod;
}
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
n=strlen(s);
m=0;
for(i=0;i<n;i++)
m+=s[i]-'a'+1;
printf("%dn",dp[n][m]-1);
}
return 0;
}