题目描述
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.
输入格式
The only line contains a non-empty string consist of only '(', ')' and '?'. The length of the string is at most $ 10^6 $ .
考虑 \(O(n^2)\)
先尝试求出深度。一个括号序列我们最后一定可以把他删成 ((((....)))) 的形式，也就是在括号序列中找到一个位置 \(i\) , \(s_i=\)'(' 且 \(l\) 左边的左括号数量等于其右边的右括号数量。枚举这个 \(i\) 在哪。设 \(i\) 前面有 \(l_i\) 个左括号， \(p_i\) 个问号，后面有 \(r_i\) 个右括号，\(q_i\) 个问号。
\(\begin{aligned}
&\sum\limits_{i=1}^n\sum\limits_{j=0}^{p_i}(l_i+j)\binom{p_i}{j}\binom{q_i}{j+l_i-r_i}\\&=\sum\limits_{i=1}^nl_i\sum\limits_{j=0}^{p_i}\binom{p_i}{j}\binom{q_i}{q_i-j-l_i+r_i}+\sum\limits_{i=1}^n\sum\limits_{j=0}^{p_i}j\binom{p_i}{j}\binom{q_i}{q_i-j-l_i+r_i}\\&=l_i\binom{p_i+q_i}{q_i-l_i+r_i}+\sum\limits_{i=0}^{p_i}p_i\binom{p_i-1}{j-1}\binom{q_i}{q_i-j-l_i+r_i}
\\&=l_i\binom{p_i+q_i}{q_i-l_i+r_i}+p_i\binom{p_i+q_i-1}{q_i-l_i+r_i-1}
\end{aligned}\)
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5,P=998244353;
char s[N];
int l[N],p[N],r[N],q[N],jc[N],iv[N],inv[N],n,ans;
int C(int n,int m)
{
if(n<m||m<0)
return 0;
return jc[n]*1LL*iv[m]%P*iv[n-m]%P;
}
int main()
{
scanf("%s",s+1),n=strlen(s+1);
for(int i=1;s[i];i++)
{
l[i]=l[i-1]+(s[i]=='(');
p[i]=p[i-1]+(s[i]=='?');
}
for(int i=n;i;i--)
{
r[i]=r[i+1]+(s[i]==')');
q[i]=q[i+1]+(s[i]=='?');
}
jc[0]=jc[1]=iv[0]=iv[1]=inv[1]=1;
for(int i=2;i<N;i++)
{
jc[i]=1LL*jc[i-1]*i%P;
inv[i]=1LL*(P-P/i)*inv[P%i]%P;
iv[i]=1LL*iv[i-1]*inv[i]%P;
}
for(int i=1;i<=n;i++)
{
(ans+=(1LL*l[i]*C(p[n],q[i+1]-l[i]+r[i+1])+1LL*p[i]*C(p[n]-1,q[i+1]-l[i]+r[i+1]-1))%P)%=P;
}
printf("%d",ans);
}