考虑固定一种计算贡献的方式，从而构造组合意义。
问题接踵而至。如何计算 ( i , j ) (i,j) (i,j)在所有方案中产生贡献的次数？从内往外考虑，那么要求 [ l , i ] [l,i] [l,i]中的左括号和 [ j , r ] [j,r] [j,r]中的右括号数目相等，不难发现这个限制是充要的。又因为问的就是整个序列的权值，所以设 [ 1 , i ] [1,i] [1,i]中有 a a a个问号， [ j , n ] [j,n] [j,n]中有 b b b个问号，左右括号相差的数目为 k k k，那么方案数 ∑ i ≤ a ( a i ) ( b i − k ) = ∑ i ≤ a ( a a − i ) ( b i − k ) = ( a + b a − k ) \sum_{i\le a}\binom{a}{i}\binom{b}{i-k}=\sum_{i\le a}\binom{a}{a-i}\binom{b}{i-k}=\binom{a+b}{a-k} ∑i≤a(ia)(i−kb)=∑i≤a(a−ia)(i−kb)=(a−ka+b)，显然如果对组合数比较熟悉的话是不难推出这个式子的。注意， [ i , j ] [i,j] [i,j]这段序列长什么样子事实上并不影响答案。
怎么优化这个枚举过程呢？显然是固定左端点，唯一需要注意的细节是当左右两边的问号都被确定时，此时右端点的选取是唯一的，也就是说恰好对应一种方案，那么将等号改成不等号就有： ∑ i ≤ a ∑ j ≥ i − k ( b j ) ( a i ) \sum_{i\le a}\sum_{j\ge i-k}\binom{b}{j}\binom{a}{i} ∑i≤a∑j≥i−k(jb)(ia)，我们希望 j j j从 0 0 0开始枚举，因此不妨变一下形式： ∑ i ≤ a ∑ j ≥ 0 ( b i − k + j ) ( a a − i ) \sum_{i\le a}\sum_{j\ge 0}\binom{b}{i-k+j}\binom{a}{a-i} ∑i≤a∑j≥0(i−k+jb)(a−ia)，交换求和顺序就有： ∑ j ≥ 0 ∑ i ≤ a ( b i − k + j ) ( a a − i ) = ∑ j ≥ 0 ( a + b a − k + j ) \sum_{j\ge 0}\sum_{i\le a}\binom{b}{i-k+j}\binom{a}{a-i}=\sum_{j\ge 0}\binom{a+b}{a-k+j} ∑j≥0∑i≤a(i−k+jb)(a−ia)=∑j≥0(a−k+ja+b)，注意到 a + b a+b a+b是定值，于是就做完了。
复杂度 O ( n ) O(n) O(n)。
感觉组合数的运算还是比多项式要轻量级的。
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define db double
using namespace std;
const int mod=998244353;
const int N=1e6+5;
int n,m,K,sum1,sum2,sum3,a,b;
ll fac[N],inv[N],f[N],f2[N],res;
string s;
ll fpow(ll x,ll y=mod-2){ll z(1);for(y;y>>=1;){if(y&1)z=z*x%mod;x=x*x%mod;}return z;
}
void add(ll &x,ll y){x=(x+y)%mod;}
ll binom(int x,int y){if(x<0||y<0||x<y)return 0;return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void init(int n,int m){fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;inv[n]=fpow(fac[n]);for(int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;for(int i=m;i>=0;i--)f[i]=f[i+1],add(f[i],binom(m,i));for(int i=m-1;i>=0;i--)f2[i]=f2[i+1],add(f2[i],binom(m-1,i));
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>s,n=s.size();for(int i=0;i<n;i++)if(s[i]=='?')m++;init(n,m);for(int i=0;i<n;i++)sum1+=(s[i]==')');for(int i=0;i<n-1;i++){sum2+=(s[i]=='('),sum1-=(s[i]==')'),sum3+=(s[i]=='?');if(s[i]=='('){K=sum1-sum2;a=sum3,b=m-sum3;assert(a>=0),assert(b>=0);assert(a+b==m);add(res,f[max(0,a-K)]);}else if(s[i]=='?'){K=sum1-sum2-1;a=sum3-1,b=m-sum3;assert(a>=0),assert(b>=0);assert(a+b==m-1);add(res,f2[max(0,a-K)]);}}cout<<res;
}
