MCOI-03

洛谷11月月赛

哇靠之前写了啊怎么没了我也会丢博文???

做法不是很显然,和李队考场上推了好久

我想到显然的是我们要算每个开头到最后的所有时括号栈大小即为答案

于是我蒙圈了,好像 $n^2$

突然发现这个好像可以算贡献,就是每个一个括号对于每个时刻的贡献

因为一个括号和谁匹配其实命运已经确定了

于是会发现我们能算贡献就能拓展算k级和了

比方说左括号,在位置i,匹配的在位置j(j>i)

考虑插板,第一个右端点一定要插在i~j之间,而之后的可以随便插,左端点可以随便插

方案数为 $\binom{i+k-1}{k}*(\binom{n-i+k}{k}-\binom{n-j+k}{k})$


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e6+1;
const int P = 998244353;
int n, k;
char s[MAXN];
int st[MAXN], bel[MAXN];
ll fac[MAXN], ifac[MAXN];
inline ll C(int n, int m) {return fac[n] * ifac[m] % P * ifac[n - m] % P;}
inline void solve() {
	int tp = 0;
	for(int i = 1; i <= n; ++i) {
		if(s[i] == '(')st[++tp] = i;
		else if(s[i] == ')') {
			if(tp) {
				bel[st[tp]] = i,bel[i] = st[tp],--tp;
			} else
				bel[i] = 0;
		}
	}
	for(int i = 1; i <= tp; ++i)bel[st[i]] = n + 1;
	ll ans = 0;
	for(int i = 1; i <= n; ++i) {
		if(s[i] == '(')
			ans = (ans + 1ll * (C(n - i + k, k) - C(n - bel[i] + k, k) + P) % P * C(i + k - 1, k) % P) % P;
		 else 
			ans = (ans + 1ll * (C(i + k - 1, k) - C(bel[i] + k - 1, k) + P) % P * C(n - i + k, k) % P) % P;
	}
	printf("%lld\n", ans);
	return ;
}

inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {if(y & 1)ans = ans * x % P;x = x * x % P;y >>= 1;}
	return ans;
}
inline void init() {
	fac[0] = 1,ifac[1] = 1,ifac[0] = 1;
	for(int i = 1; i <= n + k; ++i)fac[i] = fac[i - 1] * i % P;
	ifac[n + k] = ksm(fac[n + k], P - 2);
	for(int i = n + k - 1; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
	return ;
}
int main() {
	scanf("%d%d", &n, &k);
	scanf("%s", s + 1);
	init();	solve();
	return 0;
}

给出一种可行的构造方案吧....

你会发现我们有一个类似于摩尔投票法的东西,即如果一个数和另一个数相斥,我们就把他们丢进一个que里面,然后如果出现了相吸的,我们就拿出两个扔进序列,然后继续这个操作

不难发现,构造到最后我们一定满足相邻相吸,但是que可能不为空

也就是说我们剩下的还是要加进去,但是他们显然本身是相排斥的,也就是说他们一定是最可能出现次数大于一半的!

又因为我们构造的序列其实相邻的数不同,所以有一个性质是能插进去的数最多

因为肯定一开始有些摩尔投票的牺牲品啊,他们二者中的位置如果能插入当然就插了....

也就是说,我们如果这样做下去还是不行,说明我们确实有个大于n/2的

也就无解了,否则构造出的就是一个合法解

就是至少k个子串他们能够构成的最长公共后缀和所有可能的公共后缀种类

显然我们不用管后缀前缀,先建立SAM

然后一个区间串相当于在SAM节点上的一个节点上

于是我们把它挂上去

然后就考虑计算一个节点的贡献

然后线段树合并搞出所有标记之后再差分计算本质不同的子串贡献就好了....

这个可以用线段树二分完成那个最大值的差分,回答询问的时候前缀最大值差分即可

种类也同理,就是二分找到最早满足k个的时间....

夏晓光(loveJY)的博客

烟大(内部)ACM赛题解