题解：CF2109E Binary String Wowee

ax_by_c · 2025-05-25 15:47:28 · 题解

考虑一个操作序列 a_1,\dots,a_k 是否合法。

要求 \forall i,2\mid(\sum_{j=1}^{i-1}[a_j\ge a_i]+s_{a_i})。

那么显然是从大到小 DP，设 f_{i,j} 为 a_x\ge i,\lvert a\rvert=j 的合法方案数。

不想思考了，再搞一个 DP 算一下得了。设 g_{p,x,y} 表示 s_i=p 时，x 个 i 和 y 个 >i 的组合方法，转移显然，可以预处理出来。

时间复杂度 O(n^3)。

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
#define repll(i,l,r) for(ll i=(l);i<=(r);i++)
#define perll(i,r,l) for(ll i=(r);i>=(l);i--)
#define pb push_back
#define ins insert
#define clr clear
using namespace std;
namespace ax_by_c{
typedef long long ll;
const ll mod=998244353;
const int N=1005;
int n,k;
char s[N];
ll f[N][N],g0[N][N],g1[N][N];
void slv(){
    scanf("%d %d",&n,&k);
    scanf("%s",s+1);
    rep(i,0,n)rep(j,0,n){
        g0[i][j]=0;
        if(i==0&&j==0){
            g0[i][j]=1;
            continue;
        }
        if(j)g0[i][j]=(g0[i][j]+g0[i][j-1])%mod;
        if(i&&(!((i+j-1)&1)))g0[i][j]=(g0[i][j]+g0[i-1][j])%mod;
    }
    rep(i,0,n)rep(j,0,n){
        g1[i][j]=0;
        if(i==0&&j==0){
            g1[i][j]=1;
            continue;
        }
        if(j)g1[i][j]=(g1[i][j]+g1[i][j-1])%mod;
        if(i&&((i+j-1)&1))g1[i][j]=(g1[i][j]+g1[i-1][j])%mod;
    }
    rep(i,0,n+1)rep(j,0,n+1)f[i][j]=0;
    f[n+1][0]=1;
    per(i,n+1,2)rep(j,0,k)rep(x,0,k-j){
        if(s[i-1]=='0')f[i-1][j+x]=(f[i-1][j+x]+f[i][j]*g0[x][j]%mod)%mod;
        else f[i-1][j+x]=(f[i-1][j+x]+f[i][j]*g1[x][j]%mod)%mod;
    }
    printf("%lld\n",f[1][k]);
}
void main(){
    int T=1;
    // int csid=0;scanf("%d",&csid);
    scanf("%d",&T);
    while(T--)slv();
}
}
int main(){
    string __name="";
    if(__name!=""){
        freopen((__name+".in").c_str(),"r",stdin);
        freopen((__name+".out").c_str(),"w",stdout);
    }
    ax_by_c::main();
    return 0;
}