Upd.2022.2.3 代码写的太烂,删了(
这题如果不仔细分析的话,很容易被当成DP白白浪费很多时间(就像我)。
首先根据题意,可以认为左右括号是一种相互“抵消”的关系:
对于每个左括号,它右面总要有且仅有一个对应的右括号与其配对,才能使其成为一个合法括号序列。
在已知序列不无限循环的时候,为了使一个序列为合法括号序列,我们需要保证的条件有:
- 左右括号数目相等。
- 每个右括号出现时,必须保证它左边有可以和它配对的左括号。
如果还是不理解,可以看下代码:
bool check(){
int l=0;//统计左右括号之差
for(int i=1;i<=n;i++){
if(s[i]=='(')l++;
else{
if(l==0)return 0;//保证右括号左边有可以和它配对的左括号
else l--;
}
}
return l==0;//保证左右括号数目相等
}
但是在无限循环的情况下,我们只需要保证左右括号相等即可,证明如下:
首先如果不相等,它一定不是合法括号序列,因为这样即使无限循环下去,也一定存在无法配对的括号,这是显然的。
在左右括号相等时,序列不合法的情况只有一个:即当一个右括号出现时,左边所有左括号都配对完了,没有剩下和它配对的了,例如 (()())))((
。
由于左右括号数目相等,无法配对的右括号一定和无法配对的左括号数目相等。
那么,如果将无法配对的右括号都搬到无法配对的左括号右边,这个序列就一定是一个合法括号序列了。
比如,对于 (()())))((
,我们如果将 (()())))
都搬到序列右边,使无法配对的右括号和无法配对的左括号配上对,得到的 (((()())))
就一定是一个合法括号序列。
而题目中的“无限循环”正帮我们实现了这个“搬”的过程。
证毕。
那么这题的任务就变成了“求出所有问号的填法中能使左右括号数目相等的方案数 \(\bmod\, 998244353\) 的值”。
由于左右括号数目之和等于 \(n\) 且左右括号数目相等,左右括号的数目一定都等于 \(\frac n 2\),同时如果 \(n\) 是奇数一定无法满足条件。
令已知的左括号数目为 \(l\),问号数目为 \(q\),求的就是在所有问号中填入 \(\frac n 2-l\) 个左括号的方案数,即 \(\binom{q}{\frac n 2-l}\)。
那么剩下的就是老生常谈的求组合数了,由于 \(998244353\) 是个质数,利用费马小定理求逆元就可以了。
代码太丑,略了。
标签:配对,相等,Luogu,P8007,括号,左右,序列,数目 From: https://www.cnblogs.com/untitled0/p/luogu-P8007.html