题解：AT_abc433_f [ABC433F] 1122 Subsequence 2

最后一次打 abc 了，罕见地切了数数题（虽然也不是啥难题），写篇题解纪念一下。

首先考虑一个简化版的问题：有一个

01

串，问有多少个长度为偶数的子序列，满足前一半是

0

，后一半是

1

。

考虑枚举最后一个

0

，钦定这个

0

必须选，假设这个位置是

i

，设

i

前面的

0

的个数为

c_0

，

i

后面的

1

的个数为

c_1

，那么贡献为：

\sum \limits_{i=1}^{\min(c_0,c_1)} \binom{c_0-1}{i-1}\binom{c_1}{i}

根据范德蒙德卷积，这个式子就等于

\binom{c_0+c_1-1}{c_0}

，那么预处理组合数就可以做到

\mathcal O(n)

。

那么只要把原串中的相邻的数字挑出来，当成

01

串做就好了，每个位置至多被算两次，时间复杂度

\mathcal O(n)

。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,mod=998244353;
int n,fac[2*N],inv[2*N],facinv[2*N],ans;
string s,t[15];
void init(){
	fac[0]=inv[1]=facinv[0]=1;
	for(int i=1;i<=2*n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=2;i<=2*n;i++) inv[i]=(1ll*inv[mod%i]*(-mod/i)%mod+mod)%mod;
	for(int i=1;i<=2*n;i++) facinv[i]=1ll*facinv[i-1]*inv[i]%mod;
}
int C(int n,int m){
	if(n<0||m<0||m>n) return 0;
	return 1ll*fac[n]*facinv[n-m]%mod*facinv[m]%mod;
}
void solve(string s){
	int n=(int)s.size(),cnt0=0,cnt1=0;
	s=' '+s;
	for(int i=1;i<=n;i++) cnt1+=s[i]-'0';
	for(int i=1;i<=n;i++)
		if(s[i]=='0'){
			cnt0++;
			ans=(ans+C(cnt0+cnt1-1,cnt0))%mod;
		}
		else cnt1--;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>s;
	n=s.size();
	s=' '+s;
	init();
	for(int i=1;i<=n;i++)
		t[s[i]-'0'].push_back('1'),t[s[i]-'0'+1].push_back('0');
	for(int i=1;i<10;i++) solve(t[i]);
	cout<<ans<<'\n';
	return 0;
}

题解：AT_abc433_f [ABC433F] 1122 Subsequence 2

文章操作

相关推荐

评论

题解：AT_abc433_f [ABC433F] 1122 Subsequence 2