[DP记录]AT2161 [ARC065D] シャッフル / Shuffling
command_block
2021-05-02 21:09:35
**题意** ： 给出一个长度为 $n$ 的 $01$ 串 $S$ 。
给出 $m$ 个区间，第 $i$ 个区间为 $[l_i,r_i]$ ，顺次进行下列操作 ：
- 任意地排列 $S$ 的第 $l_i$ 到第 $r_i$ 个字符。
保证 $l_i$ **不降**。
请你求出在 $m$ 次操作后，可以得到多少种不同的 $01$ 串。答案对 $10^9+7$ 取模。
$n,m\leq 3000$ ，时限$\texttt{2s}$。
------------
若两个区间 $[l_i,r_i],[l_j,r_j]$ 满足 $l_i\leq l_j,r_j\leq r_i$ ，则可以丢弃 $[l_j,r_j]$。这样， $r_i$ 也是不降的。
不难发现，由于 $l_i$ 不降，在执行完第 $i$ 次操作后，范围 $[1,l_{i+1})$ 就已经确定了。
第 $i$ 次操作只会确定 $[l_i,\min(l_{i+1}-1,r_i)]$ 这一段。
考虑 $\rm DP$ ： 设 $dp[i][j]$ 表示处理了前 $i$ 个区间，$[1,l_{i+1})$ 内有 $j$ 个 $1$ 的方案数。
记 $c[i]$ 为 $S[1,i]$ 中 $1$ 的个数。
边界 : $dp[0][c[l_1-1]]=1$。
转移 ：
- $r_i<l_{i+1}$
$[l_i,r_i]$ 内 $1$ 的个数必为 $c[r_i]-j$。
$$dp[i+1][c[l_{i+1}-1]]\leftarrow dp[i][j]\dbinom{r_i-l_i+1}{c[r_i]-j}$$
- $r_i\geq l_{i+1}$
$[l_i,l_{i+1})$ 内 $1$ 的个数至多为 $\min\{c[r_i]-j,l_{i+1}-l_{i}\}$，至少为 $\max\big\{c[r_i]-j-(r_i-l_{i+1}+1),0\big\}$
记上下界分别为 $L,R$ ，则对于 $k\in[L,R]$ ：
$$dp[i+1][j+k]= dp[i][j]\dbinom{r_i-l_i+1}{k}$$
$k$ 的范围大小上界为 $[l_{i+1}-l_{i}]$ ，故总复杂度为 $O(n^2)$。
答案为 $dp[m][c[n]]$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 3050
using namespace std;
const int mod=1000000007;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
ll fac[MaxN],ifac[MaxN];
ll C(int n,int m)
{return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
void Init(int n)
{
fac[0]=1;
for (int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
ifac[n]=powM(fac[n]);
for (int i=n;i;i--)
ifac[i-1]=ifac[i]*i%mod;
}
int n,m,m2,l[MaxN],r[MaxN],c[MaxN],dp[MaxN][MaxN];
char s[MaxN];
int main()
{
scanf("%d%d%s",&n,&m,s+1);Init(n);
for (int i=1;i<=n;i++)c[i]=c[i-1]+(s[i]=='1');
for (int t=1,tl,tr;t<=m;t++){
scanf("%d%d",&tl,&tr);
if (tr>r[m2]){
if(l[m2]==tl)m2--;
l[++m2]=tl;r[m2]=tr;
}
}l[m2+1]=n+1;
dp[0][c[l[1]-1]]=1;
for (int i=1;i<=m2;i++)
if (r[i]<l[i+1]){
for (int j=0;j<=c[r[i]];j++)
dp[i][c[l[i+1]-1]]=(dp[i][c[l[i+1]-1]]+dp[i-1][j]*C(r[i]-l[i]+1,c[r[i]]-j))%mod;
}else {
for (int j=0;j<=n;j++)if (dp[i-1][j]){
int R=min(c[r[i]]-j,l[i+1]-l[i]),L=max(c[r[i]]-j-(r[i]-l[i+1]+1),0);
for (int k=L;k<=R;k++)
dp[i][j+k]=(dp[i][j+k]+dp[i-1][j]*C(l[i+1]-l[i],k))%mod;
}
}
printf("%d",dp[m2][c[n]]);
return 0;
}
```