【AtCoder Regular Contest 065 F】Shuffling | Mrsrz's blog

动态规划。

题目大意：

给定 $n,m$，一个 01 串和 $m$ 个区间。

要求依次对串中 $m$ 个区间内的数进行任意重排。

问最终的串有多少种不同的可能。

题解：

我们考虑一位一位确定。

如果有区间 $l,r$，那么我们在决策位置 $i$（$i\in[l,r]$） 时，$[i,r]$ 区间内的所有数是可以任意排列的。

我们对每个位置求出这个最右端点。令 $f_{i,j}$ 表示前 $i$ 个位置，当前可以自由使用的 1 的个数为 $j$ 的方案数。

转移考虑这个位置放 0 还是 1 即可。

时间复杂度 $O(n^2)$。

Code：

#include<cstdio>
const int N=3005,md=1e9+7;
int f[N][N],rg[N],pre[N],n,m;
char ss[N];
inline void upd(int&a){a+=a>>31&md;}
int main(){
    scanf("%d%d%s",&n,&m,ss+1);
    for(int i=1;i<=n;++i)pre[i]=pre[i-1]+ss[i]-48,rg[i]=i;
    for(int i=1;i<=m;++i){
        int l,r;
        scanf("%d%d",&l,&r);
        if(rg[l]<r)rg[l]=r;
    }
    for(int i=2;i<=n+1;++i)if(rg[i-1]>rg[i])rg[i]=rg[i-1];
    f[1][pre[rg[1]]]=1;
    for(int i=1;i<=n;++i)
    for(int _1=0;_1<=n;++_1)
    if(int d=f[i][_1]){
        int s1=pre[rg[i+1]]-pre[rg[i]],_0=rg[i]-i+1-_1;
        if(_1)upd(f[i+1][_1-1+s1]+=d-md);if(_0)upd(f[i+1][_1+s1]+=d-md);
    }
    printf("%d\n",f[n+1][0]);
    return 0;
}