Just A String
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 221 Accepted Submission(s): 40
Problem Description soda has a random string of length n which is generated by the following algorithm: each of n characters of the string is equiprobably chosen from the alphabet of size m .
For a string s , if we can reorder the letters in string s so as to get a palindrome, then we call s a good string.
soda wants to know the expected number of good substrings in the random string.
Input There are multiple test cases. The first line of input contains an integer T , indicating the number of test cases. For each test case:
The first line contains two integers n and m (1≤n,m≤2000) .
Output For each case, if the expected number is E , a single integer denotes E⋅mn mod 1000000007 .
Sample Input
3
2 2
3 2
10 3
Sample Output
10
40
1908021
Source 2015 Multi-University Training Contest 6
博主表示很兴奋,居然有人私信我说我的题解写的好。。。。。那我以后要写的更详细啦!
题目:
给长度为n,字母表个数为m。对于长度为n的任意字符串(字符只能是1-m中的),如果存在一个子串,
该子串重新排列后为回文串,称该子串为好的子串。求得到回文串个数的期望,乘M^n%1e10+7
解析:
乘M^n意味着对所有可能的长度为n的字符串,求出它的是好的子串的个数的累加和。
如果长度为奇数的子串,那么该子串的字母中除了一种字母是奇数外,其他字母必须是偶数个。
如果长度为偶数,那么每种字母都必须是偶数个。-------------------显然是吧~~~
接下来定义状态:
dp[i][j] 表示长度为i的有j种字母是奇数个的串的个数。
那么dp[i][j] 只能是从dp[i-1][j-1]-------------表示添加一个原来字母数时偶数的字母字母后,奇数个字母的种数增加了,
那么添加的字母只能是已经包含的奇数个数字母以外的字母了有m-j+1
dp[i-1][j+1] ----------- 表示添加一个原来是奇数个的字母,那么奇数个字母的种数减少1,
那么只能添加原来是奇数的字母了,有j+1种字母
dp[i][j] = dp[i-1][j-1]]*(m-j+1) + dp[i-1][j+1]*(j+1)
====================================================================
以上讲完了,接下来讲
1. 边界处理一下即可0,和最大的情况
2. 如果i为奇数,那么j为偶数的dp[i][j]为0,是不需要计算的,减少了2的常数复杂度
3. 不能用memset来初始话,最多只能用for来初始话
--------------------为什么说这些没用的!!
因为数据有1000组,标程有两个,标程1自己T了,标程2也是500+ms。(g++交的)
我也t了无数发。一下种种就是为了不t,个估计你们自己写的话会比我好;
#include<cstdio>
#define maxn 2048
#define ll long long
int dp[maxn][maxn],mod=1000000007; //据说int 存储比longlong快
int po[maxn];
int main(){
int t,m,n;
//freopen("1010.in","r",stdin);
//freopen("10101.out","w",stdout);
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
dp[1][0] = 0; //初始话dp[1],以及后面直接计算dp[n]都是为了减少计算(毕竟1000组case)
dp[1][1] = m;
po[0] = 1;
for(int i = 1;i <= n;i++){
po[i] = (ll)po[i-1]*m%mod;
}
int j;
for(int i = 2;i < n; i++){
dp[i][0] = dp[i-1][1];
dp[i][i] = (ll)dp[i-1][i-1]*(m-i+1) % mod ;
if(i & 1) j = 1;
else j = 2; //为了减少2的常数复杂度
for(;j < i; j+=2)
dp[i][j] = ((ll)dp[i-1][j-1]*(m-j+1)+(ll)dp[i-1][j+1]*(j+1))%mod;
}
if(n>1)dp[n][0] = dp[n-1][1];
if(n>1)dp[n][1] = ((ll)dp[n-1][0] * m + (ll)dp[n-1][2] * 2)% mod;
int ans = 0;
for(int i = 1;i <= n; i++){
ans = (ans+(ll)dp[i][i&1]*(n-i+1)%mod*po[n-i])%mod;
}
printf("%d\n",ans);
}
return 0;
}