[cf] Educational Codeforces Round 57 (Rated for Div. 2) B 组合数学,字符串删除问题

前言

t a g : tag : tag:字符串 组合数 *1300 传送门 :

题意

给定一个 字符串, 仅删除一次子串(连续),询问有多少种方法使得最后剩余的串只出现相同的字符

思路

组合数问题,首先我们考虑分类讨论

• 如果本来的串就是相同的 , 那么我们考虑使用隔板法,对于 n + 1 n+1 n+1个空隙,我们选 2 2 2个空隙删除,即 C n + 1 2 = n ∗ ( n + 1 ) 2 C_{n+1}^2=\frac{n*(n+1)}{2} Cn+12​=2n∗(n+1)​
• 如果头尾一样,则 ( p r e + 1 ) ∗ ( s u l ∗ 1 ) (pre+1)*(sul*1) (pre+1)∗(sul∗1),作乘法原理
• 否则就只能单一的删除 p r e + s u l + 1 pre+sul+1 pre+sul+1

Code

const int mod = 998244353;

void solve(){
	int n;cin>>n;
	string s;cin>>s;
	
	int flag = 0 ;
	
	ll pre =  1 ;
	ll sul =  1 ;
	
	for(int i=1;i