组合数+dp

我们从合法的新串下手，考虑制定出一种方法来从中找出原串。

对这种方法的要求是：按照这种方法 找出的新串 的下标 必须唯一。

一种合理的匹配方式是：

• 假如原串是：abcabcabc
• 假如新串是：aaabbbcccaaabbbccaaccaaabbbcccaaabbbccaaccaaabbbcccaaabbbccaacc
• 匹配应该是：aaabbbcccaa[a]bb[b]ccaac[c]aaabbbcccaa[a]bb[b]ccaac[c]aaabbbcccaa[a]bb[b]ccaac[c]
• 匹配规则是：对于某个被匹配到的字符 chchch 开始，从它右边第一个开始，到它右边下一个被匹配的字符左边第一个为止，不得出现跟 chchch 相同的字符。
• 能发现，按照这种方法 找出的新串 的下标是唯一的。
• 总结一下这种匹配方式：

• • 我们知道，由子序列 SSS 构造原序列 TTT，问方案数这类问题，就是要保证，
  • 如果你在 TTT 确定 TTT 的第 iii 个字符 tit_iti​，匹配的是 SSS 中的第 ppp 个字符 sps_psp​，
  • 并且你在 TTT 确定 TTT 的第 jjj 个字符 tjt_jtj​，匹配的是 SSS 中的第 p+1p+1p+1 个字符 sp+1s_{p+1}sp+1​，
  • 除了 ti=spt_i=s_pti​=sp​，tj=sp+1t_j=s_{p+1}tj​=sp+1​ 以外，还要保证，ti+1...tj−1t_{i+1}...t_{j-1}ti+1​...tj−1​ 的所有字符，都不包含 tit_iti​。

现在考虑按照这种匹配思路，从原串开始，构造新串。

void Sol()
{
    dp[0][0] = 1;
    for (int i=1; i<=m; i++)    //从你决定开始匹配原串第一个字符之前，放什么都行，每一个位置有26种放法。
    {
        dp[i][0] = dp[i-1][0] * 26 % MOD;
    }
     
    for (int i=1; i<=m; i++)//枚举新串
    {
        for (int j=1; j<=min(i, n); j++)//枚举原串
        {
            //对于新串的第 i 个字符，有两种情况：
            //一种是第i个字符匹配上原串的第j个字符
            //一种是第i个字符在前i-1个已经匹配上原串的第j个字符的情况下，有25种放法。
            dp[i][j] += (j-1<0?0:dp[i-1][j-1]) + dp[i-1][j] * 25 % MOD, dp[i][j] %= MOD;
        }
    }
    printf("%lld\n",dp[m][n]);

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

Link doesn't remember bbb, so he wonders the number of possible sequences bbb.
 

A bracket sequence is valid if it satisfies any of the following conditions:

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=205,mod=1e9+7;
ll dp[N][N][N];
void solve()
{
    int n,m;cin>>n>>m;
    string s;
    cin>>s;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=m;k++) dp[i][j][k]=0;
        }
    }
    dp[0][0][0]=1;
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<=i;j++) 
        {
            dp[0][i][j]+=(j-1<0?0:dp[0][i-1][j-1])+dp[0][i-1][j+1];
            dp[0][i][j]%=mod;
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=min(i,n);j++)
        {
            for(int k=0;k<=i;k++)
            {
                int d=-1+2*(s[j-1]=='(');
                if(k-d>=0&&k-d<=m) dp[j][i][k]+=dp[j-1][i-1][k-d];
                if(k+d<=m&&k+d>=0) dp[j][i][k]+=dp[j][i-1][k+d];
                dp[j][i][k]%=mod;
            }
        }
    }
    cout<0]<
}
int main()
{
    int t;cin>>t;
    while(t--)
    {
        solve();
    }
}