很遗憾，您上传的题解 数字串 Number String 未能通过审核。原因是 数学公式中的文本应使用 \text，字符串应使用 \texttt（?）；审核管理员：shinzanmono，对审核结果有疑问请私信交流。 。 难不成这个dp，这个sum，这个a和括号里的i都要加\text ???

题意：给你一个字符串 $s$，$s_i = \texttt D$ 表示排列中 $a_i > a_{i+1}$，$s_i = \texttt I$ 表示排列中 $a_i < a_{i+1}$，$s_i = ?$ 表示无限制。

$dp_{ij}$ 表示前 $i$ 个满足字符串条件的结尾为 $j$ 的 $i$ 的排列。

如果 $s_{i-1}$ 是 $\texttt I$，那么 $dp_{ij} = dp_{i-1,1} + dp_{i-1,2} + \dots + dp_{i-1,j-1}$。

如果 $s_{i-1}$ 是 $\texttt D$，那么 $dp_{ij} = dp_{i-1,j} + dp_{i-1,j+1} + \dots + dp_{i-1,i}$，因为要令当前位为 $j$，如果前面出现过 $j$，就令前面的所有大于等于 $j$ 的数 $+1$，就能构造出新的排列了。比如 ${1, 3, 5, 2, 4}$，要在第六位插入 $3$，令 $\ge 3$ 的数都 $+1$，于是就构造出新的排列 ${1, 4, 6, 2, 5, 3}$。然后代码的话处理出前缀和 $sum_{ij}$，就不用 $dp_{ij}$ 了。

#include <bits/stdc++.h>
using namespace std;

const int mod = 1000000007;
const int maxn = 1e3 + 10;
char s[maxn];
long long dp[maxn][maxn];//前缀和。

int main()
{
    while(scanf("%s", s) != EOF){
        int n = strlen(s);

        dp[0][1] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i + 1; j++){
                dp[i][j] = dp[i][j-1];//前缀和累加。
                if(s[i-1] != 'I') dp[i][j] += dp[i-1][i] - dp[i-1][j-1] + mod;
                if(s[i-1] != 'D') dp[i][j] += dp[i-1][j-1];
                dp[i][j] %= mod;
            }
        }

        printf("%lld\n", dp[n][n+1]);
    }

    return 0;
}

题意：给你一个字符串 $s$，$s_i = \texttt D$ 表示排列中 $a_i > a_{i+1}$，$s_i = \texttt I$ 表示排列中 $a_i < a_{i+1}$，$s_i  = ?$ 表示无限制。

$dp_{ij}$ 表示前 $i$ 个满足字符串条件的结尾为 $j$ 的 $i$ 的排列。

如果 $s_{i-1}$ 是 $\texttt I$，那么 $dp_{ij} = dp_{i-1,1} + dp_{i-1,2} + \dots + dp_{i-1,j-1}$。

如果 $s_{i-1}$ 是 $\texttt D$，那么 $dp_{ij} = dp_{i-1,j} + dp_{i-1,j+1} + \dots + dp_{i-1,i}$，因为要令当前位为 $j$，如果前面出现过 $j$，就令前面的所有大于等于 $j$ 的数 $+1$，就能构造出新的排列了。比如 ${1, 3, 5, 2, 4}$，要在第六位插入 $3$，令 $\ge 3$ 的数都 $+1$，于是就构造出新的排列 ${1, 4, 6, 2, 5, 3}$。然后代码的话处理出前缀和 $sum_{ij}$，就不用 $dp_{ij}$ 了。

#include <bits/stdc++.h> using namespace std;

const int mod = 1000000007; const int maxn = 1e3 + 10; char s[maxn]; long long dp[maxn][maxn];//前缀和。

int main() { while(scanf("%s", s) != EOF){ int n = strlen(s);

    dp[0][1] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i + 1; j++){
            dp[i][j] = dp[i][j-1];//前缀和累加。
            if(s[i-1] != 'I') dp[i][j] += dp[i-1][i] - dp[i-1][j-1] + mod;
            if(s[i-1] != 'D') dp[i][j] += dp[i-1][j-1];
            dp[i][j] %= mod;
        }
    }

    printf("%lld\n", dp[n][n+1]);
}

return 0;

}