官方数据全部过掉了,但是民间数据一塌糊涂,错得没剩下几个
这是记录:https://www.luogu.com.cn/record/73152552
把代码贴在这里,求大神帮我看看
#include<bits/stdc++.h>
#define MAXN 410
#define MOD (ll)(1e9+7)
using namespace std;
typedef long long ll;
int n,m,cas;
string s,r,t;
namespace accepted{
ll f[2][MAXN][MAXN],sum[MAXN];
void main(){
for(int i=1;i<=n;i++) sum[i] = sum[i-1] + (s[i] == '-');
f[0][0][0] = 1;
for(int i=0;i<n;i++){
memset(f[(i+1) & 1],0,sizeof(f[(i+1) & 1]));
// for(int j=0;j<m && j<i;j++){
for(int k=0;i - k - sum[i] * 2 >= 0;k++){
// int l = i - sum[i] - k - j;
// if(s[i] == '-'){
// if(k) f[(i+1) & 1][j][k-1] += f[i & 1][j][k];
// if(l) f[(i+1) & 1][j][k] += f[i & 1][j][k];
// }else{
// f[(i+1) & 1][j][k] += f[i & 1][j][k];
// if(j == 0 && l == 0) f[(i+1) & 1][j][k+1] += f[i & 1][j][k];
// if(s[i] == t[j+1] && l == 0){
// f[(i+1) & 1][j+1][k] += f[i & 1][j][k];
// }
// }
// }
for(int l=0;i - k - l - sum[i] * 2 >= 0;l++){
int j = i - k - l - sum[i] * 2;
if(s[i+1] == '-'){
if(k) f[(i+1) & 1][k-1][l] += f[i & 1][k][l], f[(i+1) & 1][k-1][l] %= MOD; // 删去开头的数字
if(l) f[(i+1) & 1][k][l-1] += f[i & 1][k][l], f[(i+1) & 1][k][l-1] %= MOD; // 删去末尾的数字
}else{
f[(i+1) & 1][k][l+1] += f[i & 1][k][l]; // 加入末尾的数字不需要
if(j == 0 && l == 0) f[(i+1) & 1][k+1][l] += f[i & 1][k][l], f[(i+1) & 1][k+1][l] %= MOD;
if(s[i+1] == t[j+1] && l==0){
f[(i+1) & 1][k][l] += f[i & 1][k][l];
f[(i+1) & 1][k][l] %= MOD;
}
}
// printf("i = %d j = %d k = %d l = %d f = %lld\n",i,j,k,l,f[i & 1][k][l]);
}
}
// }
}
printf("%lld\n",f[n & 1][0][0]);
}
}
string read(){
char c; string tmp;
while(!(isdigit(c) || c=='-')) c=getchar();
while(isdigit(c) || c=='-'){
tmp+=c; c=getchar();
}
return tmp;
}
int main(){
scanf("%d",&cas);
while(cas--){
s.clear(); t.clear();
scanf("%d%d",&n,&m);
s += ' '; t += ' ';
s+=read(); t+=read();
// single_dfs::main();
accepted::main();
}
return 0;
}