CF1622D题解
Tyyyyyy
2021-12-28 10:05:38
# CF1622D
### 题意简述
给定一个长为 $n$ 的 $\text{01}$ 串，你可以进行以下操作**最多一次**：
选定一个**恰好**包含 $k$ 个 $\text{1}$ 的**子串**，并将其**任意重排**。其中，$k$ 是给定的常数。
求你最多能变换出多少种不同的字符串。答案对 $998244353$ 取模。
$1\leq n\leq 5000,0\leq k\leq n$。
### 题目分析
首先，为了方便讨论，我们选择的子串一定是**极长的**，即不能再扩展的子串。证明显然，因为包含某个短串的串的变换方案一定包含了所有该短串的变换方案。
我们先不考虑算重的情况，则设当前的极长字串内 $\text{1}$ 的个数为 $cnt$，子串长度为 $len$，则该子串的变换方案为 $C_{len}^{cnt}$ 种。
接下来我们考虑什么时候会算重复。设有两个相邻的极长子串 $[l_1,r_1],[l_2,r_2]$，且满足 $l_1<l_2<r_1<r_2$。那么它们的变换方案会产生重复，当且仅当 $[l_1,l_2),(r_1,r_2]$ 中的 $\text{1}$ 保持原位。读者可以自己写下样例的所有方案来理解。
也就是说，对于这样的两个子串，设 $[l_2,r_1]$ 中有 $cnt$ 个 $\text{1}$，则重复的方案数为 $C_{r_1-l_2+1}^{cnt}$。
因此，我们只需要找到所有的极长子串，再进行上述的计算即可。注意因为可以不进行操作，所以上述的方案数应当减去 $1$（不变的情况），最后再给答案加上 $1$ 即可。
Code：
```cpp
#include<bits/stdc++.h>
#define int long long
const int mod=998244353;
using namespace std;
int n,k,ans,jc[5010],inv[5010],a[5010];
char s[5010];
int power(int x,int y)
{
int t=1;
while(y)
{
if(y&1)t=1ll*t*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return t;
}
vector<pair<int,int> >v;
signed main()
{
scanf("%lld%lld",&n,&k);
scanf("%s",s+1);
if(k<1){printf("1");return 0;}
for(int i=1;i<=n;i++)a[i]=a[i-1]+(s[i]=='1');
jc[1]=inv[1]=jc[0]=inv[0]=1;
for(int i=2;i<=n;i++)jc[i]=1ll*jc[i-1]*i%mod,inv[i]=power(jc[i],mod-2);
for(int i=1;i<=n;i++)
{
if(s[i-1]=='0')continue;
int j,l;
for(j=i,l=0;j<=n;j++)
{
if(s[j]=='1'&&l==k)break;
if(s[j]=='1')l++;
}
if(l<k)break;
if(s[j]=='1'||j>n)j--;
if(i>j)continue;
int len=j-i+1;
ans=(ans+1ll*jc[len]*inv[k]%mod*inv[len-k]%mod-1+mod)%mod;
v.push_back({i,j});
if(j==n)break;
}
for(int i=1;i<(int)v.size();i++)
{
int l=v[i].first,r=v[i-1].second;
if(l>r)continue;
int cnt=a[r]-a[l-1];
if(cnt)ans=(ans-1ll*jc[r-l+1]*inv[cnt]%mod*inv[r-l+1-cnt]%mod+1+mod)%mod;
}
printf("%lld",(ans+1)%mod);
return 0;
}
```