Submission #64376983

---

Source Code Expand

#include <bits/stdc++.h>
#pragma GCC target ("avx2,fma")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#define int long long
#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)
using namespace std;
int inf=1000000000000000007;
int mod=998244353;
int mod1=998244353;

#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif


const int N=10000007;

int fac[2*N];
int inv[2*N];
int P[2*N];
 
int pot(int x,int p) {int res=1;for(;p;p>>=1) {if(p&1) res=res*x%mod; x=x*x%mod;} return res;}
int npok(int n,int k)
{
    if(min(k,n)<0||k>n) return 0;
    return fac[n]*inv[k]%mod*inv[n-k]%mod;
}

int nx[500007];
int pref[500007];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    fac[0]=1,P[0]=1;
    for(int i=1;i<=n+3*k+7;i++)
    {
		fac[i]=fac[i-1]*i%mod;
		P[i]=P[i-1]*2%mod;
	}
    inv[n+3*k+7]=pot(fac[n+3*k+7],mod-2);
    for(int i=n+3*k+7-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    n-=k;
    string s;
    cin>>s;
    s='#'+s;
    vector<int>V;
    FOR(i,1,k)
    {
		if(s[i]==')'&&sz(V)>0)
		{
			nx[V.back()]=i;
			pref[V.back()]=1;
			V.pop_back();
		}
		else if(s[i]=='(') V.pb(i);
	}
	vector<int>W;
	FOR(i,1,k) pref[i]+=pref[i-1];
    FOR(i,1,k)
    {
		if(nx[i]>0)
		{
			if(pref[nx[i]]-pref[i-1]==1) W.pb(1);
			else W.pb(2);
			i=nx[i];
		}
	}
	int f=-1;
	FOR(i,0,sz(W)-1) if(f==-1&&W[i]==2) f=i;
	int ans=0,m=sz(W);
	if(f==-1)
	{
		FOR(x,0,n) ans=(ans+P[x]*npok(2*m-1+n-x,n-x))%mod;
	}
	else
	{
		ans=npok(2*(f+1)+m-f-1+n,n);
		ans=(ans+(m-f)*npok(2*(f+1)+m-f+n-1,n-1))%mod;
	}
    cout<<ans<<endl;
    
    return 0;
}

Submission Info

Judge Result