这题在vp的时候做出来了，但是今天在做2023CCPC秦皇岛的热身赛的时候发现这道题又想了很久才做出来，于是决定还是把思路写一遍
链接
题意
给一个长为 n 的01串，其中1有 m 个，最长连续的1的个数为 k ，求不同的串的个数
解
最长连续的1的个数为 k 的不太好做，可以转化为最长连续的1的个数不超过 k ，这样不用去考虑那个 k 是谁
由容斥原理可以知道最长连续1的个数为 k 的串数 = 最长连续的1的个数不超过 k 的串数 - 最长连续的1的个数不超过 k − 1 的串数
这种不超过多少的问题可以转化为一个多元方程，例如这个题可以转化为
但这样搞需要遍历 s ，复杂度不够，无法通过此题，于是考虑优化
可以想到一个类似的但较弱的问题（想不起来具体是什么，只记得可以将一些元素绑定起来然后用隔板法解决），然后给了某种启发。
原序列中有 n 个位置，有 m 个1，去掉这 m 个1后有 n − m 个0。原问题可以化成在这些0中间插入1的串，每个串长不超过 k 。
n − m 个0有 n − m + 1
个空位，于是可以写出母函数：
f(x) 中 x 的 m 次方项系数 ans 为
AC代码： 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
63
64
65
66
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=0x3f3f3f3f3f3f3f3fLL;
typedef pair<int,int> pii;
const int mod=998244353;
const int N=1e5+100;
int fac[N],rev[N];
ll qpow(ll a,ll n,ll m)
{
ll ans=1;
while(n)
{
if(n&1)
ans=(__int128_t)ans*a%m;
a=(__int128_t)a*a%m;
n>>=1;
}
return ans;
}
void init(int n)
{
fac[0]=1;
for(int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
rev[n]=qpow(fac[n],mod-2,mod);//n must be less than mod
for(int i=n;i>=1;i--)
rev[i-1]=rev[i]*i%mod;
assert(rev[0]==1);
}
int C(int n,int m)
{
if(m>n)
return 0;
return fac[n]*rev[m]%mod*rev[n-m]%mod;
}
inline int cal(int n,int m,int k){
int ans=0;
for(int i=0;i*(k+1)<=m;i++){
ans=(ans+(i%2==0?1:-1)*C(n-m+1,i)%mod*C(n-i*(k+1),n-m)%mod)%mod;
}
return ans;
}
signed main() {
ios::sync_with_stdio(false);cin.tie(0);
int n,m,k;
cin>>n>>m>>k;
init(1e5+10);
if(!(m<=n&&k<=m)){
cout<<0<<'\n';
return 0;
}
if(k==0){
if(m==0)
cout<<1<<'\n';
else
cout<<0<<'\n';
return 0;
}
cout<<((cal(n,m,k)-cal(n,m,k-1))%mod+mod)%mod<<'\n';
return 0;
}