hdu 5362 Just A String 2015多校聯合訓練賽#6 動态規劃

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;
}