题解：AT_abc433_f [ABC433F] 1122 Subsequence 2

1122 Subsequence 2

题目大意

给定一个由数字组成的字符串

S

。

\\

现给出对“

1122

字符串”的定义：对于某字符串

T

，当其满足以下条件时，就被成为“

1122

字符串”。

$T$ 是一个由数字组成的非空字符串。
$|T|$ （字符串 $T$ 的长度）为偶数。
字符串 $T$ 中第 $1$ 个字符至第 $\frac{|T|}2$ 个字符均为同一数字。字符串 $T$ 中从第 $\frac{|T|}2+1$ 个字符到第 $|T|$ 个字符均为 $T$ 的第 $1$ 个字符（表示的）数字加 $1$ 形成的字符。

求字符串

S

中所有（不一定是连续的）子序列中为“

1122

字符串”的数量，结果对

998244353

取模。

\\

若两个子序列来自不同位置，则即使其字符串内容相同，也应分别计数。

思路分析

考虑枚举

S

中满足条件的子序列的左半段最后一个字符的位置（第 $\frac{|T|}2$ 个字符）。

\\

假设这是知道的唯一条件，即设该位置字符必选，考虑在这种情况下计算符合条件的子序列数量。

假设当前答案子序列的左半段最后一个字符的位置（在原字符串中）为

i

，则该字符为

S_i

。

\\

记

i

的左侧（包含

i

）与

S_i

相同的字符有

a

个，

i

的右侧与

S_i+1

相同的字符有

b

个，在

i

的左、右侧都会分别选取

l

个字符（则有

\begin{cases} l \le a \\ 1 \le b \\ \end{cases}

，换句话说，就是

l \le \min(a,b)

）。

\\

因此，

i

的左侧（包含

i

）需要在

a-1

（因为第

i

个字符必选）个字符中选

l

个，

i

的右侧需要在

b

个字符中选

l

个，因此总方案就有

C_{a-1}^{l-1} \cdot C_b^l

种。

则以

S_i

为答案左半段最后一个字符时，对总数的贡献为：

\\

\begin{aligned} \sum_{l=1}^{\min(a,b)}C_{a-1}^{l-1} \cdot C_b^l &=\sum_{l=1}^{\min(a,b)}C_{a-1}^{a-l} \cdot C_b^l\\ &=C_{a+b-1}^a \end{aligned}

大家看着这个转移可能会很迷惑，因此在此做出解释：

第一步只变了一处，依靠的是 $C_x^y=C_x^{y-x}$ 。
第二步注意到式子被表现成了 $\sum_{i=0}^{k} C_m^i \cdot C_n^{k-i}$ 的形式，因此根据 范德蒙恒等式，可以化为 $C_{m+n}^k$ 的形式。

最后就很简单了，逆元预处理阶乘后借助公式求解组合数即可。

代码详解

CPP

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
string s;
unordered_map<char,int> frt,bck; //当前字符在其位置前、后出现的次数
int n,fac[2000005]={1},inv[2000005],ans;
int pows(int a,int b,int p){
	int now=1;
	while(b>0){
		if(b&1) now=now*a%p;
		a=a*a%p;
		b>>=1;
	}
	return now;
}
//利用预处理数组计算组合数
int cxy(int x,int y){
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>s;
	n=s.size();
	s=" "+s;
    //逆元预处理
	for(int i=1;i<=2000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[2000000]=pows(fac[2000000],mod-2,mod);
	for(int i=1999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    //先假设所有字符都在答案后半段
	for(int i=1;i<=n;i++) bck[s[i]]++;
    //O(|S|)计算答案
	for(int i=1;i<=n;i++){
		frt[s[i]]++,bck[s[i]]--;
		ans=(ans+cxy(frt[s[i]]+bck[s[i]+1]-1,frt[s[i]]))%mod; //公式解释见上文
	}
	cout<<ans;
	return 0;
}

题解：AT_abc433_f [ABC433F] 1122 Subsequence 2

文章操作

1122 Subsequence 2

题目大意

思路分析

代码详解

相关推荐

评论

题解：AT_abc433_f [ABC433F] 1122 Subsequence 2