机器人表演

题解

相当离谱的状态定义。
看到这道题我们首先比较容易想到的方法是$dp$。
如果我们要$dp$的话必然可能会涉及同一个串通过不同路径同时贡献到答案的问题，也就是说，我们要尽可能让每个串属于一个唯一的状态。
考虑该怎么定义状态。
当前串如果是由不同的方式转移过来的，那么它就只与它在原串中转移到的长度有关，因为确定它在原串中使用的前缀后，自然而然就可以知道它新增了几个$0/1$了。
所以一种方法是在状态中记录能够转移到这个点的原串前缀集合，这样来状压$dp$。

但显然这是不太可能过我们$n⩽300$的数据范围的，也就是说，我们不太可能把整个集合都记录下来。
那我们尝试考虑一下，只记录集合中的最大值，能否通过回撤还原整个集合。
显然，如果当前最大值下一个就是我们要扩展的元素，那么就可以直接扩展。否则，我们考虑能不能通过加入$0/1$的形式扩展，再不行就考虑回撤。
如果我们下一个是$0$不行需要撤回的话，现在肯定是处在临时加入的$0$已经填满的状况，不可能再填出更多的$0$了，所以回撤也是没有解的。
如果下一个位置要填$1$，但我们现在填不动，那我们肯定是临时加入的$0$的数量与$1$一样。所以现在我们只需要回撤找到第一个$0$数量大于$1$的点即可。
实际上，这个回撤也是相当于在进行子序列的$next\_permutation$的枚举，只取了当前集合最小点的一个代表元，就能这样枚举还原整个集合。
当然，我们不太可能每次转移的时候都去找到它会回退到哪个点，这个可以预处理出来。
其它的转移就是按当前的最优填数方案填即可。

时间复杂度$O\left(n{m}^2\right)$。

源码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,LL> pii;
#define MAXN (1<<20)+5
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lowbit(x) (x&-x)
const int mo=998244353;
const int inv2=5e8+4;
const int jzm=2333;
const int zero=15;
const int INF=0x3f3f3f3f;
const double Pi=acos(-1.0);
const double eps=1e-9;
const int lim=1000000;
const int orG=3,ivG=332748118;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
    _T f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
    x*=f;
}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1;}return t;}
int n,m,dp[305][305][305],pre[305];
char str[305];
int main(){
    read(n);read(m);scanf("%s",str+1);
    for(int i=1;i<=n;i++){
        int now=(str[i+1]=='1');pre[i]=i;
        while(pre[i]>=0&&now<=0)
            now+=(str[pre[i]]=='0'?1:-1),pre[i]--;
    }
    dp[0][0][0]=1;
    for(int i=0;i<n+m+m;i++)
        for(int x=0;x<=min(i,m);x++)
            for(int y=0;x+y<=i&&y<=x;y++){
                int z=i-x-y;if(z>n||!dp[x][y][z])continue;
                if(x<m&&str[z+1]!='0')Add(dp[x+1][y][z],dp[x][y][z],mo);
                if(y<x&&str[z+1]!='1')Add(dp[x][y+1][z],dp[x][y][z],mo);
                if(z<n)Add(dp[x][y][z+1],dp[x][y][z],mo);
                if(str[z+1]!='1'&&x==y&&pre[z]>=0){
                    int t=(z-pre[z]+1)/2;if(x+t>m)continue;
                    Add(dp[x+t][y+t][pre[z]],dp[x][y][z],mo);
                }
            }
    printf("%d\n",dp[m][m][n]);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

谢谢！！！