福田响应式网站建设服务,威海网站建设开发公司,网站建设公司正规吗,网站seo优化外包P8273 [USACO22OPEN] Pair Programming G
题目大意
一个程序由一系列指令组成#xff0c;每条指令的类型如下#xff1a; d \times d d#xff0c;其中 d d d是一个 [ 0 , 9 ] [0,9] [0,9]范围内的整数 s s s#xff0c;其中 s s s是一个表示变量名称的字符串#xff…P8273 [USACO22OPEN] Pair Programming G
题目大意
一个程序由一系列指令组成每条指令的类型如下 × d \times d ×d其中 d d d是一个 [ 0 , 9 ] [0,9] [0,9]范围内的整数 s s s其中 s s s是一个表示变量名称的字符串不同操作的变量名称互不相同
指令字符串中一个数字 d d d表示操作一一个加号 表示操作二。
小 B B B和小 E E E各有一个有 n n n条指令的程序交错这些程序可以得到一个有 2 n 2n 2n个指令的新程序。计算执行这些交错程序可能得到的不同表达式的数量输出答案对 1 0 9 7 10^97 1097取模后的值。
有 T T T组数据。 1 ≤ T ≤ 10 , ∑ n ≤ 2000 1\leq T\leq 10,\sum n\leq 2000 1≤T≤10,∑n≤2000 题解
首先要对小 B B B和小 E E E的字符串做一些处理。如果有 × 0 \times 0 ×0的操作则之前的部分都没用了但注意这个 × 0 \times 0 ×0还有用。如果有 × 1 \times 1 ×1操作则对答案没有影响要将其舍去。
设 f i , j , 0 / 1 f_{i,j,0/1} fi,j,0/1表示小 B B B的串匹配到第 i i i位小 E E E的串匹配到第 j j j位最后一个是小 B B B的指令还是小 E E E的指令的答案。
我们知道加法和乘法都满足交换律即 a b b a , a × b b × a abba,a\times bb\times a abba,a×bb×a。也就是说如果有两个类型相同且位置相邻的操作则两个操作的先后顺序对最后得到的表达式没有影响。
那么如果两个字符串当前的操作类型相同则先执行小 B B B的操作。
由此可推得转移式 f i 1 , j , 0 f i , j , 0 f i , j , 1 f_{i1,j,0}f_{i,j,0}f_{i,j,1} fi1,j,0fi,j,0fi,j,1 f i , j 1 , 1 f i , j , 0 × [ S i ≠ T j 1 ] f i , j , 1 f_{i,j1,1}f_{i,j,0}\times [S_i\neq T_{j1}]f_{i,j,1} fi,j1,1fi,j,0×[SiTj1]fi,j,1
当最后一个指令是小 B B B的指令时如果下一个指令要是小 E E E的指令则必须满足两个指令的类型不同。这样就能保证没有表达式会被重复计算。
注意一开始 f 0 , 0 , 1 1 f_{0,0,1}1 f0,0,11如果将 1 1 1赋值到 f 0 , 0 , 0 f_{0,0,0} f0,0,0则会在下一次转移中被计算两次所以要将 1 1 1赋值到 f 0 , 0 , 1 f_{0,0,1} f0,0,1才能使开始的空字符串只被计算一次。
时间复杂度为 O ( ∑ n 2 ) O(\sum n^2) O(∑n2)。
code
#includebits/stdc.h
using namespace std;
const long long mod1e97;
int T,n,s1,t1;
long long f[2005][2005][2];
char s[2005],t[2005];
void dd(int a1,char a[]){a10;for(int i1;in;i){if(a[i]0) a10;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,s1,t1);dd(s1,s);dd(t1,t);f[0][0][1]1;for(int i0;is1;i){for(int j0;jt1;j){if(is1) f[i1][j][0](f[i][j][0]f[i][j][1])%mod;if(jt1){f[i][j1][1]f[i][j][1];if(is[i]!t[j1])f[i][j1][1](f[i][j1][1]f[i][j][0])%mod;}}}printf(%lld\n,(f[s1][t1][0]f[s1][t1][1])%mod);}return 0;
}
