Accept: 147    Submit: 434Time Limit: 3000 mSec    Memory Limit : 32768 KB

 Problem Description

“我需要一個案件！！！”，沒有案件卷福快瘋了。花生不忍心看卷福這個樣子，他決定幫卷福找點事情做。

花生拿了兩個長度為N的相同的序列，序列都為WB(WBWBWB...)相間，并且由W開頭。他將兩個序列并在了一起，其中屬于同個序列的元素相對位置不變。花生高興的把新序列拿給卷福，要求卷福給每個元素標上1或2編號，表示這個元素是原來的第幾個序列的元素。

卷福看完花生的序列，哭笑不得。“笨蛋！你難道不知道這個標號不唯一么！那你知道有多少種不同的標號方案么？”

可憐的花生給自己挖了個坑。快來幫他解決這個問題！

 Input

輸入第一行包含一個整數t，表示輸入組數。

每組數據第一行為一個整數N(1<=N<=3000)，表示每個原序列的長度。

接下來一行為一個只包含’W’, ’B’的字符串，長度為2*N。

 Output

輸出一個整數占一行，為標號的方案數。由于答案比較大，請將答案mod 1000000007。

 Sample Input

 Sample Output

思路：

1、統計方案計數問題，前后狀態有相互限制性，我們可以考慮dp，設定dp【i】【j】表示原串到位子i+j長度處，其中串1長度為i，串2長度為j的方案數。

2、那么不難推出其狀態轉移方程：

①dp【i】【j】=dp【i-1】【j】+dp【i】【j-1】；表示要么這個字符（a【i+j】）歸到串1中，要么歸到串2中。

②那么對應我們知道W一定要放在奇數長度處 ，B一定要放在偶數長度處，那么就有：

③題目設定內存為32M，1e7的數組是比32M要大很多的，所以我們考慮到dp【i】【j】只受到第i行和第i-1行的dp方案影響，所以我們可以縮減空間，設定為dp【2】【j】，并且采用滾動數組的方法，不斷的更新兩行數據即可。

Ac代碼：

#include<stdio.h>#include<string.h>using namespace std;#define mod 1000000007char a[6500];int dp[1111][1111];int main(){    int t;    scanf("%d",&t);    while(t--)    {        int n;scanf("%d",&n);        scanf("%s",a);        memset(dp,0,sizeof(dp));        dp[0][0]=1;        for(int i=0;i<=n;i++)        {            for(int j=0;j<=n;j++)            {                if(i==0&&j==0)continue;                if(i==0)                {                    if(a[i+j-1]=='W')                    {                        if(j%2==1&&j-1>=0)dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;                        if(i%2==1&&i-1>=0)dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;                    }                    if(a[i+j-1]=='B')                    {                        if(j%2==0&&j-1>=0)dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;                        if(i%2==0&&i-1>=0)dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;                    }                }                else                {                    if(a[i+j-1]=='W')                    {                        if(j%2==1&&j-1>=0)dp[1][j]=(dp[1][j]+dp[1][j-1])%mod;                        if(i%2==1&&i-1>=0)dp[1][j]=(dp[1][j]+dp[0][j])%mod;                    }                    if(a[i+j-1]=='B')                    {                        if(j%2==0&&j-1>=0)dp[1][j]=(dp[1][j]+dp[1][j-1])%mod;                        if(i%2==0&&i-1>=0)dp[1][j]=(dp[1][j]+dp[0][j])%mod;                    }                }            }            if(i>0)            for(int j=0;j<=n;j++)dp[0][j]=dp[1][j],dp[1][j]=0;        }        printf("%d/n",dp[0][n]);    }}