CF1264D2 Beautiful Bracket Sequence (hard version)

发表于 | 评论数： | 阅读次数：
本文字数： 2.6k | 阅读时长 ≈ 2 分钟

CF1264D2 Beautiful Bracket Sequence (hard version)

传送门

洛谷

题意描述

This is the hard version of this problem. The only difference is the limit of $n$ the length of the input string. In this version, $1 \leq n \leq 10^6$.

Let’s define a correct bracket sequence and its depth as follow:

An empty string is a correct bracket sequence with depth $0$.
If “s” is a correct bracket sequence with depth $d$ then “(s)” is a correct bracket sequence with depth $d + 1$.
If “s” and “t” are both correct bracket sequences then their concatenation “st” is a correct bracket sequence with depth equal to the maximum depth of $s$ and $t$.
For a (not necessarily correct) bracket sequence $s$, we define its depth as the maximum depth of any correct bracket sequence induced by removing some characters from $s$ (possibly zero). For example: the bracket sequence $s = $”())(())” has depth $2$, because by removing the third character we obtain a correct bracket sequence “()(())” with depth $2$.

Given a string $a$ consists of only characters ‘(‘, ‘)’ and ‘?’. Consider all (not necessarily correct) bracket sequences obtained by replacing all characters ‘?’ in $a$ by either ‘(‘ or ‘)’. Calculate the sum of all the depths of all these bracket sequences. As this number can be large, find it modulo $998244353$.

Hacks in this problem can be done only if easy and hard versions of this problem was solved.

题意翻译

菜鸡Gluttony英语不好…

输入输出格式

输入格式：

The only line contains a non-empty string consist of only ‘(‘, ‘)’ and ‘?’. The length of the string is at most $10^6$.

输出格式：

Print the answer modulo $998244353$ in a single line.

输入输出样例

输入样例#1：

??

输出样例#1：

1

输入样例#2：

(?(?))

输出样例#2：

9

输入样例#3：

2 2
0 0

输出样例#3：

500000003

输入样例#4：

9 4
0 11 12 9 20 7 8 18 2

输出样例#4：

169316356

说明

【样例解释1】

In the first test case, we can obtain $4$ bracket sequences by replacing all characters ‘?’ with either ‘(‘ or ‘)’:

“((“. Its depth is $0$;
“))”. Its depth is $0$;
“)(“. Its depth is $0$;
“()”. Its depth is $1$.

So, the answer is $1 = 0 + 0 + 0 + 1$.

【样例解释2】

In the second test case, we can obtain $4$ bracket sequences by replacing all characters ‘?’ with either ‘(‘ or ‘)’:

“(((())”. Its depth is $2$;
“()()))”. Its depth is $2$;
“((()))”. Its depth is $3$;
“()(())”. Its depth is $2$.

So, the answer is $9 = 2 + 2 + 3 + 2$.

分析

考虑最优解的一种构造方法，对于从左往右每一个左括号，能找到从右往左能找到没有匹配的右括号就匹配，否则就不匹配，这个显然正确，因为这样做不会使答案更劣。
那么这个括号序列的深度就是匹配的左括号数。
我们接着考虑对于第$i$个左括号，如果它被匹配，那么它之前所有的左括号也一定被匹配了，否则与它匹配的右括号应该给在它之前且没有被匹配的左括号，也就是说，这个左括号被匹配的条件是在它右边的右括号数大于等于它和它左边的左括号数。
我们设$a$表示它和它左边的左括号数，$b$表示它右边的右括号数，$c$表示它左边的问号数，$d$表示它右边的问号数。
那么一个左括号的贡献就是：

因为由二项式定理可知以下式子成立：

即：

那么贡献就可以化简为：

发现$c+d$只有$2$个取值，所以复杂度为$O(n)$。

参考资料

chemthan 的题解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define maxn 1000010
const int p=998244353;
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
int n,a,b,c,d,ans;
char str[maxn];
map<int,vector<int>>C;
int add(int x,int y)
{
	return (x+y)%p;
}
int sub(int x,int y)
{
	return (x-y+p)%p;
}
int mul(int x,int y)
{
	return 1ll*x*y%p;
}
int fpow(int x,int y)
{
	int res=1;
	while(y)
	{
		if(y&1)
			res=mul(res,x);
		x=mul(x,x);
		y>>=1;
	}
	return res;
}
int calc(int a,int b,int c,int d)
{
	int x=b+d-a;
	if(x<0)
		return 0;
	int k=c+d;
	if(k<x)
		x=k;
	if(C.count(k))
		return C[k][x];
	auto& f=C[k];
	f.resize(k+1);
	int w=1,s=0;
	for(int i=0;i<=k;i++)
	{
		s=add(s,w);
		f[i]=s;
		w=mul(w,mul(k-i,fpow(i+1,p-2)));
	}
	return f[x];
}
int main()
{
	scanf("%s",str+1);
	n=strlen(str+1);
	for(int i=1;i<=n;i++)
	{
		if(str[i]==')')
			b+=1;
		if(str[i]=='?')
			d+=1;
	}
	for(int i=1;i<=n;i++)
	{
		if(str[i]=='(')
			a+=1;
		if(str[i]==')')
			b-=1;
		if(str[i]=='?')
			c+=1,d-=1;
		if(str[i]=='(')
			ans=add(ans,calc(a,b,c,d));
		if(str[i]=='?')
		{
			a+=1;
			c-=1;
			ans=add(ans,calc(a,b,c,d));
			a-=1;
			c+=1;
		}
	}
	printf("%d\n",ans);
    return 0;
}