Pair Programming (USACO Gold 2022 US Open)

有一定难度的DP题目（Paths on Grids）。

初看找不到什么规律，不同的表达式的数量上限可以看出来，就是 $2n \choose n$ ，但到底有多少不知道。把所有表达式生成出来肯定不行，因为 $n$ 最大 $2\cdot 10^5$ 。所以从复杂度来，这应该是 $\mathcal{O}(n^2)$ 的DP，应该状态是两维（比如两个串各用了几个字符，再加以谁结束这样），但状态转移不清楚。

然后写出一些表达式来看，我们可以看到最后的表达式都是 $a_1 v_1 + ...$ 这样的不带括号的多项式形式，具体来说，在interleave之后的操作序列中，一个变量项后面的所有数字项，乘起来决定了这个变量前的参数。那这又有什么用呢？

再仔细看会发现不同的interleave中间，有一些是重复的。实际上唯一的重复情况，是相邻的同一种操作（+或者*）之间的交换，也就是算术的交换率。那么我们可以想到，要去掉这些重复的办法，就是固定相邻同一种操作之间的相对顺序，比如一种办法是，不允许同一种操作间从E到B的转移（只允许B-B, B-E, E-E这三种），这样的话，在一段有B也有E贡献的连续乘法运算中（加法也类似），来自B的会在前面，来自E的都在后面，结果就唯一了。

这时候可以看到数字项中有两个数字是特殊的，一是0，乘以0让前面的表达式全没有了。所以处理办法是：预处理，0前面的去掉（0本身要保留）。另一个特殊数字是1，直接把所有1都去掉就行。而其它数字，都会对结果产品影响。

DP状态定义为： $\texttt{dp}[i][j][k]$ ，B用了 $i$ 个操作，E用了 $j$ 个操作，以B结束（ $k=0$ ）或者以E结束（ $k=1$ ）时的方案数。

最后复杂度为 $\mathcal{O}(n^2)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int T, n, nb, ne;  // <= 2000
char B[2005], E[2005], s[2005];
int dp[2005][2005][2];      // dp[i][j][k]: B用了i个操作，E用了j个操作，以B结束（k=0）或者以E结束（k=1）时的方案数
const int M = 1e9 + 7;
 
void proc(char *t) {
    char *in = t;
    int len = strlen(in);
    for (int i = n-1; i >= 0; i--)     // '0'
        if (in[i] == '0') {
            in += i;
            len = strlen(in);
            break;
        }
    int j = 0;
    for (int i = 0; i <= len; i++)
        if (in[i] != '1')           // '1'
            s[j++] = in[i];
    strncpy(t, s, 2000);
}
 
bool same(char prv, char nxt) {
    return prv == nxt || prv >= '0' && prv <= '9' && nxt >= '0' && nxt <= '9';
}
 
int main() {
    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        scanf("%d %s %s", &n, B, E);
        proc(B); proc(E);
        nb = strlen(B); ne = strlen(E);
 
        for (int i = 0; i <= nb; i++)
            for (int j = 0; j <= ne; j++)
                dp[i][j][0] = dp[i][j][1] = 0;
        
        dp[0][0][0] = 1;
        for (int i = 0; i <= nb; i++)
            for (int j = 0; j <= ne; j++) {
                if (i > 0) {
                    dp[i][j][0] = (dp[i][j][0] + dp[i-1][j][0]) % M;
                    // do not allow E to B transition of same type
                    if (j == 0 || !same(B[i-1], E[j-1]))
                        dp[i][j][0] = (dp[i][j][0] + dp[i-1][j][1]) % M;
                }
                if (j > 0)
                    dp[i][j][1] = ((ll)dp[i][j][1] + dp[i][j-1][0] + dp[i][j-1][1]) % M;
            }
        printf("%d\n", (dp[nb][ne][0] + dp[nb][ne][1]) % M);
    }
 
    return 0;
}