我也是2 8 9 10 ……所以到底错哪了?
by Gamin @ 2018-10-18 21:54:14
```cpp
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int dp[3][205][205][3],n,m,k;bool v=1;//v是取奇偶数用的v^1如果为1就是奇数,得0为偶数
char a[1005],b[205];
const int maxn=(int)(1e9)+7;
int main()
{
cin>>n>>m>>k;
scanf("%d%d%d",&n,&m,&k);
//scanf("%s%s",a+1,b+1);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=m;i++)
cin>>b[i];
dp[0][0][0][0]=dp[1][0][0][0]=1;
for(int i=1;i<=n;i++,v^=1)//跑A串的长度
{
for(int j=1;j<=m;j++)//跑B串的长度
{
for(int p=1;p<=k;p++)//有k个字符串组成
{
if(a[i]==b[j])
{
dp[v][j][p][0]=(dp[v^1][j][p][0]%maxn+dp[v^1][j][p][1]%maxn)%maxn;
dp[v][j][p][1]=(dp[v^1][j-1][p-1][1]%maxn+dp[v^1][j-1][p][1]%maxn+dp[v^1][j-1][p-1][0]%maxn)%maxn;//dp[v^1][j-1][p][1]是说两个i和i-1是连在一起的一个字符串(都要取)
}
else
{
dp[v][j][p][0]=(dp[v^1][j][p][1]%maxn+dp[v^1][j][p][0]%maxn)%maxn;
dp[v][j][p][1]=0;
}
}
}
}
//cout<<(dp[n&1][m][k][0]+dp[n&1][m][k][1])%maxn<<endl;
printf("%d\n",(dp[n&1][m][k][0]%maxn+dp[n&1][m][k][1]%maxn)%maxn);
return 0;
}
```
我也WA了 2 8 9 10
by Gamin @ 2018-10-18 22:13:03
太巧了,我也是2 8 9 10
```cpp
#include<cstdio>
#include<iostream>
using namespace std;
const int p=1e9+7;
int n,m,K,ans=0,v=1,f[2][250][250][2];
char s1[1010],s2[250];
inline int read(){
char ch=getchar();int j=0,k=1;
while(ch<'0'||ch>'9'){if(ch=='-')k=-1;ch=getchar();}
while(ch>='0'&&ch<='9')j=j*10+ch-'0',ch=getchar();
return j*k;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
return;
}
int main(){
//freopen("substring.in","r",stdin);
//freopen("substring.out","w",stdout);
n=read(),m=read(),K=read();
scanf("%s%s",s1+1,s2+1);
f[0][0][0][0]=f[1][0][0][0]=1;
for(int i=1;i<=n;i++,v^=1)
for(int j=0;j<=m;j++)
for(int k=1;k<=K;k++){
f[v][j][k][0]=(f[v^1][j][k][0]+f[v^1][j][k][1])%p;
if(s1[i]==s2[j])f[v][j][k][1]=(f[v^1][j-1][k][1]+f[v^1][j-1][k-1][0]+f[v^1][j-1][k-1][1])%p;
else f[v][j][k][1]=0;
}
write((f[n&1][m][K][0]+f[n&1][m][K][1])%p);
//fclose(stdin);
//fclose(stdout);
return 0;
}
```
by 求败 @ 2018-10-26 11:23:47
@[Gamin](/space/show?uid=86284) 咱俩是一样的
by 求败 @ 2018-10-26 11:24:21
@[求败](/space/show?uid=33615) 目前我还没发现错误……
by Gamin @ 2018-10-26 17:07:00
@[Gamin](/space/show?uid=86284) 我A了,我是
```cpp
for(int j=0;j<=m;j++)
```
应该是
```cpp
for(int j=1;j<=m;j++)
```
你好像不是这个错误
by 求败 @ 2018-10-27 07:17:31
@[Gamin](/space/show?uid=86284) @[Forever_coding](/space/show?uid=75203) 注意一下取mod,在转移里面有个三个数相加的可能会爆
by 空の軌跡 @ 2019-04-25 20:05:35
@[空の軌跡](/user/89785) (考古)我也是这三个点,这三个单独取mod就不对,前两个相加再取mod就对了?
```
(f[(i-1)%2][j-1][k-1][1]+f[(i-1)%2][j-1][k-1][0])%d+f[(i-1)%2][j-1][k][1];
by wangyansong @ 2020-11-26 08:43:29
@[wangyansong](/user/180453) 考古+1,真的怪啊这个取模规则,我也两个相加取两次就对了,其它都是错的
by Akama1 @ 2023-07-18 20:38:24