Codeforces

Luogu

分析

考虑枚举一个分界点，如果左边的 ( 和右边的 ) 相等，那么深度就是左边的 ( 数。

设 $l$ 为左边的 ( 数、$f$ 为左边的 ? 数、$r$ 为右边的 ) 数、$g$ 为右边的 ? 数，枚举深度，方案数为
$$
\sum_{i=0}^f (l+i){f\choose i}{g\choose l+i-r}
$$
把 $l,i$ 拆开，带 $l$ 的项：
$$
\begin{aligned}
&l\sum_{i=0}^f{f\choose i}{g\choose l+i-r}\\
=&l\sum_{i=0}^f{f\choose i}{g\choose g-l-i+r}\\
=&l{f+g\choose g-l+r}
\end{aligned}
$$
带 $i$ 的项：
$$
\begin{aligned}
&\sum_{i=0}^fi{f\choose i}{g\choose l+i-r}\\
=&f\sum_{i=0}^f{f-1\choose i-1}{g\choose y-l-i+r}\\
=&f{f-1+g\choose y-l+r-1}
\end{aligned}
$$
时间复杂度 $\mathcal{O}(n)$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;
const int mod=998244353;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n; char s[N];
int l[N],r[N],f[N],g[N];
int fac[N],ifac[N];

int C(int n,int m) {
    if (n<m||n<0||m<0) return 0;
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

int main() {
    scanf("%s",s+1),n=strlen(s+1);
    for (int i=1;i<=n;++i) l[i]=l[i-1]+(s[i]=='('),f[i]=f[i-1]+(s[i]=='?');
    for (int i=n;i>=1;--i) r[i]=r[i+1]+(s[i]==')'),g[i]=g[i+1]+(s[i]=='?');
    fac[0]=1;
    for (int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for (int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
    int ans=0;
    for (int i=1;i<n;++i) {
        ans=(ans+1ll*l[i]*C(f[i]+g[i+1],g[i+1]+r[i+1]-l[i]))%mod;
        ans=(ans+1ll*f[i]*C(f[i]+g[i+1]-1,g[i+1]-l[i]+r[i+1]-1))%mod;
    }
    printf("%d\n",ans);
    return 0;
}