USACO22OPEN Pair Programming G

P8273 [USACO22OPEN] Pair Programming G

题目大意

一个程序由一系列指令组成，每条指令的类型如下：

• $\times d$，其中$d$是一个$[0,9]$范围内的整数
• $+s$，其中$s$是一个表示变量名称的字符串，不同操作的变量名称互不相同

指令字符串中一个数字$d$表示操作一，一个加号$+$表示操作二。

小$B$和小$E$各有一个有$n$条指令的程序，交错这些程序可以得到一个有$2n$个指令的新程序。计算执行这些交错程序可能得到的不同表达式的数量，输出答案对$10^9+7$取模后的值。

有$T$组数据。

$1\le T\le 10,\sum n\le 2000$

题解

首先，要对小$B$和小$E$的字符串做一些处理。如果有$\times 0$的操作，则之前的部分都没用了，但注意这个$\times 0$还有用。如果有$\times 1$操作，则对答案没有影响，要将其舍去。

设$f_{i,j,0/1}$表示小$B$的串匹配到第$i$位，小$E$的串匹配到第$j$位，最后一个是小$B$的指令还是小$E$的指令的答案。

我们知道，加法和乘法都满足交换律，即$a+b=b+a,a\times b=b\times a$。也就是说，如果有两个类型相同且位置相邻的操作，则两个操作的先后顺序对最后得到的表达式没有影响。

那么，如果两个字符串当前的操作类型相同，则先执行小$B$的操作。

由此可推得转移式
$f_{i+1,j,0}=f_{i,j,0}+f_{i,j,1}$
$f_{i,j+1,1}=f_{i,j,0}\times [S_i\ne T_{j+1}]+f_{i,j,1}$

当最后一个指令是小$B$的指令时，如果下一个指令要是小$E$的指令，则必须满足两个指令的类型不同。这样就能保证没有表达式会被重复计算。

注意一开始$f_{0,0,1}=1$，如果将$1$赋值到$f_{0,0,0}$则会在下一次转移中被计算两次，所以要将$1$赋值到$f_{0,0,1}$才能使开始的空字符串只被计算一次。

时间复杂度为$O(\sum n^2)$。

code

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int T,n,s1,t1;
long long f[2005][2005][2];
char s[2005],t[2005];
void dd(int &a1,char a[]){a1=0;for(int i=1;i<=n;i++){if(a[i]=='0') a1=0;else if(a[i]=='1') continue;if(a[i]!='+') a[i]='*';a[++a1]=a[i];}
}
int main()
{scanf("%d",&T);while(T--){scanf("%d",&n);scanf("%s%s",s+1,t+1);dd(s1,s);dd(t1,t);f[0][0][1]=1;for(int i=0;i<=s1;i++){for(int j=0;j<=t1;j++){if(i<s1) f[i+1][j][0]=(f[i][j][0]+f[i][j][1])%mod;if(j<t1){f[i][j+1][1]=f[i][j][1];if(i&&s[i]!=t[j+1])f[i][j+1][1]=(f[i][j+1][1]+f[i][j][0])%mod;}}}printf("%lld\n",(f[s1][t1][0]+f[s1][t1][1])%mod);}return 0;
}