首页 > 其他分享 >CF785D 题解

CF785D 题解

时间:2024-11-12 11:20:45浏览次数:1  
标签:分界点 suf CF785D int 题解 inv ans

CF题目

luogu题目

题解似乎清一色是同一个做法,这里给一个容斥的做法。

首先枚举一个位置 \(i\),设 \([1,i]\) 的左括号个数为 \(p\),\([i + 1,n]\) 的右括号个数为 \(q\),那么以 \(i\) 这个位置为分界点的合法括号数有 \(\sum_{i = 1}^{\min(p,q)} C_p^i C_q^i\) 个。通过范德蒙德卷积我们可以知道这个的值为 \(C_{p + q}^p - 1\)。

然后枚举 \(i\) 作为分界点求和就行了吗?

算一下样例发现这并不对,原因是会算重,手玩一下容易发现,上面的答案再减去对于一个分界点 \(j\),计算 \([1,j - 1]\) 和 \([j + 1,n]\) 之间的贡献即可。

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,p=1e9+7;
string s;
int n,pre[N],suf[N],fac[N],inv[N],ans=0;
int qpow(int a,int b) {
	int ans=1;
	while(b) {
		if(b&1) ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}
void init(int lim) {
	fac[0]=inv[0]=1;
	for(int i=1; i<=lim; i++) fac[i]=fac[i-1]*i%p;
	inv[lim]=qpow(fac[lim],p-2);
	for(int i=lim-1; i>=1; i--) inv[i]=inv[i+1]*(i+1)%p;
}
int C(int n,int m) {
	if(n<0||m<0||n<m) return 0;
	return fac[n]*inv[m]%p*inv[n-m]%p;
}
signed main() {
	cin>>s;n=s.size();s=' '+s;
	init(n);
	for(int i=1; i<=n; i++) pre[i]=pre[i-1]+(s[i]=='(');
	for(int i=n; i>=1; i--) suf[i]=suf[i+1]+(s[i]==')');
	for(int i=1; i<n; i++) ans=(ans+C(pre[i]+suf[i+1],pre[i])-1+p)%p;
	for(int i=1; i<n-1; i++) ans=(ans-C(pre[i]+suf[i+2],pre[i])+1+p)%p;
	cout<<ans;
	return 0;
}

标签:分界点,suf,CF785D,int,题解,inv,ans
From: https://www.cnblogs.com/System-Error/p/18541488

相关文章

  • CF 1325 题解
    CF1325题解AEhAbAnDgCd有\(\gcd(1,x)=1,\text{lcm}(1,x)=x\),因此输出\(1x\).BCopyCopyCopyCopyCopy要求严格上升子序列,那么答案的上界当然是去重后的元素个数.能否取到上界呢?当然可以,每一段内选一个你想要的就可以了.CEhabandPath-eticMEXs发现\(0,......
  • 历年CSP-J初赛真题解析 | 2020年CSP-J初赛完善程序(34-43)
    学习C++从娃娃抓起!记录下CSP-J备考学习过程中的题目,记录每一个瞬间。附上汇总贴:历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客(质因数分解)给出正整数n,请输出将n质因数分解的结果,结果从小到大输出。例如:输入n=120,程序应该输出22235,表示120=2×2×2×......
  • 博弈论(零和博弈)英文版题解
    翻译:   假设我们有一个两人零和游戏,每个玩家有两种行动,行收益矩阵如下:计算行和列玩家的最小最大最优策略以及游戏的价值。      X     YA    a11   a12B    a21   a22选项:1.行玩家:第一种行动的概率为三分之二,第......
  • P1625求和 题解
    P1625求和题解题意求和题解比较好想,小学一年级奥数可以理解为高精度的大杂烩代码很简洁,可自行理解#include<bits/stdc++.h>//万能头#definelllonglong//开longlong usingnamespacestd;//命名空间lln,m,a[2005],b[2005],c[4000005];//a[0],b[0],c[0]......
  • 牛客周赛Round 67 个人题解(A~F)
    牛客周赛Round67个人题解(A~F)牛客周赛Round67A-排序危机题目分析相对位置不会改变,用三个·字符串模拟即可#include<bits/stdc++.h>#defineendl'\n'usingnamespacestd;voidsolve(){ intn;cin>>n; strings;cin>>s; s=""+s; strings1,s2,s3; for(i......
  • CSP-J2024 复赛T1(洛谷P11227)题解
    前传作者初赛没过。坐标sd,79分过不了已经适应了。话说这次泄题事件闹得沸沸扬扬,都说各省分数线要降,最后sd降了8分,80。挺逆天的,感觉sd再这样下去一点OIer都要没了。思路桶排思想,用二维数组模拟一整副牌,本来做的时候是怕有重复牌才这样做,事实上不会。ACCode#include<bits/......
  • 《【NOIP2000 基础】计算器的改良》 不全对题解
    温馨提示,本题难度略大,本人写不出来正确代码,文章代码并不对,只是提供一些思路,希望大家能谅解!目录题目描述输入描述输出描述解析完整代码描述NCL是一家专门从事计算器改良与升级的实验室,最近该实验室收到了某公司所委托的一个任务:需要在该公司某型号的计算器上加上解一......
  • 洛谷题单103数组题解||by红糖
    P1428小鱼比可爱题目描述人比人,气死人;鱼比鱼,难死鱼。小鱼最近参加了一个“比可爱”比赛,比的是每只鱼的可爱程度。参赛的鱼被从左到右排成一排,头都朝向左边,然后每只鱼会得到一个整数数值,表示这只鱼的可爱程度,很显然整数越大,表示这只鱼越可爱,而且任意两只鱼的可爱程度可能一样......
  • [题解](更新中)Refact.ai Match 1 (Codeforces Round 985)
    A-Set显然答案是\(\max(\lfloor\frac{r}{k}\rfloor-l+1,0)\)。点击查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intt,l,r,k;signedmain(){ cin>>t; while(t--){ cin>>l>>r>>k; cout<<max(0ll,......
  • 题解:P11262 [COTS 2018] 题日 Zapatak
    https://www.luogu.com.cn/article/i7ajvm8e哈希好题。题意给定一个序列,每次询问给定两个长度相等的区间,问这两个区间是否只有一个数不一样。思路发现我们要求的信息只与数的出现次数有关,自然想到桶。那么如果有两个区间合法,那这两个区间的桶只有两个位置不同且桶内的值均相......