結果

問題 No.3099 Parentheses Decomposition
ユーザー ococonomy1
提出日時 2025-04-11 21:25:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 583 ms / 2,000 ms
コード長 5,493 bytes
コンパイル時間 2,218 ms
コンパイル使用メモリ 197,140 KB
実行使用メモリ 238,140 KB
最終ジャッジ日時 2025-04-11 21:25:27
合計ジャッジ時間 15,520 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pli = pair<ll,int>;
#define TEST cerr << "TEST" << endl
#define AMARI 998244353
//#define AMARI 1000000007
#define el '\n'
#define El '\n'
#define YESNO(x) ((x) ? "Yes" : "No")
#define YES YESNO(true)
#define NO YESNO(false)
#define REV_PRIORITY_QUEUE(tp) priority_queue<tp,vector<tp>,greater<tp>>
#define NO_ANS(x) {cout << (x) << '\n'; return;}
template <typename T>
void inline VEC_UNIQ(vector<T> &v){
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    return;
}

class ococo_combination{
private:
    long long N,P;
    vector<long long> kaizyou,gyakugen,gyakugen_kaizyou;
    long long pn = -1,pk = -1;
    ll sum_ans = 0;
public:
    //デフォルトで調べられる最大値が 1e7 になっている。TL/ML がヤバかったら小さくするも良し、クソでか二項係数が要求されたら大きくするも良し。
    ococo_combination(long long p = 998244353,long long n = 10000000){
        n++;
        N = n; P = p;
        kaizyou.resize(n);
        gyakugen.resize(n);
        gyakugen_kaizyou.resize(n);
        kaizyou[0] = kaizyou[1] = 1;
        gyakugen[0] = gyakugen[1] = 1;
        gyakugen_kaizyou[0] = gyakugen_kaizyou[1] = 1;
        for(int i = 2; i < n; i++){
            kaizyou[i] = kaizyou[i - 1] * i % p;
            gyakugen[i] = p - gyakugen[p % i] * (p / i) % p;
            gyakugen_kaizyou[i] = gyakugen_kaizyou[i - 1] * gyakugen[i] % p;
        }
    }
    long long binom(int n,int k){
        if(n < k || n < 0 || k < 0)return 0LL;
        long long ans = kaizyou[n];
        long long temp = gyakugen_kaizyou[n - k];
        temp *= gyakugen_kaizyou[k]; temp %= P;
        ans *= temp; ans %= P;
        return ans;
    }

    //1 * 2 * ... * n(mod P) を返す。当然 n は N 以下であることを要求する。
    long long factorial(int n){
        assert(n < N);
        if(n < 0)return 0LL;
        return kaizyou[n];
    }

    //binom(n,0) + binom(n,1) + ... + binom(n,k) を返す。
    //計算量は少し特殊で、1回目は O(K)、2回目以降は前回の呼び出しを (pn,pk) としたとき O(abs(n - pn) + abs(k - pk))
    //Mo の順番で入れることで N*sqrt(Q) とかで全部の答えを得られる。また、良い感じにスライドする場合はみなし O(1) とかになったりもする。
    //これを呼び出すとき、 P >= 3 でないといけない(2で割る操作があるため)
    //まだ verify してないので注意！
    long long sum(int n,int k){
        if(pn == -1 || abs(n - pn) + abs(k - pk) >= k){
            sum_ans = 0;
            for(int i = 0; i <= k; i++){
                sum_ans += binom(n,i);
                if(sum_ans >= P)sum_ans -= P;
            }
            pn = n; pk = k;
            return sum_ans;
        }
        while(n > pn){
            sum_ans = 2LL * sum_ans - binom(pn,pk);
            if(sum_ans < 0)sum_ans += P;
            if(sum_ans >= P)sum_ans -= P;
            pn++;
        }
        while(n < pn){
            ll temp = sum_ans + binom(pn - 1,pk);
            if(temp % 2)temp += P;
            sum_ans = temp / 2;
            pn--;
        }
        while(k < pk){
            sum_ans -= binom(pn,pk);
            if(sum_ans < 0)sum_ans += P;
            pk--;
        }
        while(k > pk){
            pk++;
            sum_ans += binom(pn,pk);
            if(sum_ans >= P)sum_ans -= P;
        }
        return sum_ans;
    }
    //n番目のカタラン数を呼び出す。n は 2*N 以下を要求するので注意
    long long catalan(int n){
        ll ans = kaizyou[2 * n];
        ans *= gyakugen_kaizyou[n + 1]; ans %= P;
        ans *= gyakugen_kaizyou[n]; ans %= P;
        return ans;
    }
};
    

#define MULTI_TEST_CASE false
void solve(void){
    //問題を見たらまず「この問題設定から言えること」をいっぱい言う
    //一個回答に繋がりそうな解法が見えても、実装や細かい詰めに時間がかかりそうなら別の方針を考えてみる
    //ある程度考察しても全然取っ掛かりが見えないときは実験をしてみる
    //よりシンプルな問題に言い換えられたら、言い換えた先の問題を自然言語ではっきりと書く
    //複数の解法のアイデアを思いついた時は全部メモしておく
    //g++ -D_GLIBCXX_DEBUG -Wall -O2 a.cpp -o o
    int n;
    cin >> n;
    string s;
    cin >> s;
    if(n == 2){
        //00 or 11
        cout << 2 << el;
        return;
    }

    ococo_combination comb;

    if(s[1] == '('){
        //A
        ll ans = 0LL;
        for(int i = 0; i <= n / 2; i++){
            //左半分からi個、右半分からi個 1を選ぶ
            ll temp = comb.binom(n / 2,i);
            temp *= temp; temp %= AMARI;
            ans += temp; if(ans >= AMARI)ans -= AMARI;
        }
        cout << ans << el;
        return;
    }
    ll ans = 1LL;
    for(int i = 0; i < n / 2; i++){
        ans *= 2LL;
        ans %= AMARI;
    }
    cout << ans << el;
    return;
}

void calc(void){
    return;
}

signed main(void){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    calc();
    int t = 1;
    if(MULTI_TEST_CASE)cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
0