# 【UNR #6】机器人表演()-其他

## 【UNR #6】机器人表演()

### Sample Input

``````3 1
101
``````

### Sample Output

``````4
``````

### Data Constraint

\(1\le n\le 300,1\le t\le 300\)

### Code

``````#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define mo 998244353
#define N 310

int f[N*3][N][N],n,t,len,to[N],a[N];
char s[N];

int mod(int x){return x>=mo?x-mo:x;}

void upd(int&x,int y){x=mod(x+y);}

bool pd(int l,int r){
int sum=0;
F(i,l,r){
sum+=(a[i]==0?1:-1);
if(sum<0)return 0;
}
return (sum==1);
}

int main(){
scanf("%d%d",&n,&t);
scanf("%s",s+1);
F(i,1,n)a[i]=s[i]-'0';
len=n+t*2;
f[0][0][0]=1;
memset(to,127,sizeof(to));
F(i,1,n) Fd(j,i-1,0)if(pd(j+1,i)){to[i]=j;break;}
F(i,0,len-1) F(j,0,n) F(k,0,t)if(f[i][j][k]){
if(a[j+1]==0&&j+1<=n)upd(f[i+1][j+1][k],f[i][j][k]);
else upd(f[i+1][j][k+1],f[i][j][k]);
if(a[j+1]==1&&j+1<=n)upd(f[i+1][j+1][k],f[i][j][k]);
else{
if(k-1>=0)upd(f[i+1][j][k-1],f[i][j][k]);
else if(to[j]<j)upd(f[i+1][to[j]][k],f[i][j][k]);
}
}
printf("%d",f[len][n][0]);
return 0;
}
``````
————————

### Sample Input

``````3 1
101
``````

### Sample Output

``````4
``````

### Data Constraint

\(1\le n\le 300,1\le t\le 300\)

### Code

``````#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define mo 998244353
#define N 310

int f[N*3][N][N],n,t,len,to[N],a[N];
char s[N];

int mod(int x){return x>=mo?x-mo:x;}

void upd(int&x,int y){x=mod(x+y);}

bool pd(int l,int r){
int sum=0;
F(i,l,r){
sum+=(a[i]==0?1:-1);
if(sum<0)return 0;
}
return (sum==1);
}

int main(){
scanf("%d%d",&n,&t);
scanf("%s",s+1);
F(i,1,n)a[i]=s[i]-'0';
len=n+t*2;
f[0][0][0]=1;
memset(to,127,sizeof(to));
F(i,1,n) Fd(j,i-1,0)if(pd(j+1,i)){to[i]=j;break;}
F(i,0,len-1) F(j,0,n) F(k,0,t)if(f[i][j][k]){
if(a[j+1]==0&&j+1<=n)upd(f[i+1][j+1][k],f[i][j][k]);
else upd(f[i+1][j][k+1],f[i][j][k]);
if(a[j+1]==1&&j+1<=n)upd(f[i+1][j+1][k],f[i][j][k]);
else{
if(k-1>=0)upd(f[i+1][j][k-1],f[i][j][k]);
else if(to[j]<j)upd(f[i+1][to[j]][k],f[i][j][k]);
}
}
printf("%d",f[len][n][0]);
return 0;
}
``````