結果

問題 No.1873 Bracket Swapping
ユーザー hiikunZhiikunZ
提出日時 2022-03-11 23:31:37
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 444 ms / 2,000 ms
コード長 2,346 bytes
コンパイル時間 15,060 ms
コンパイル使用メモリ 291,528 KB
最終ジャッジ日時 2025-01-28 09:08:31
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
//#include<atcoder/all>
//using namespace atcoder;
using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
constexpr ll MAX = 2000000000000000000;
constexpr ld PI = 3.14159265358979;
constexpr ll MOD = 998244353;//2024948111;
ld dotorad(ld K){return PI * K / 180.0;}
ld radtodo(ld K){return K * 180.0 / PI;}
mt19937 mt;
void randinit(){srand((unsigned)time(NULL));mt = mt19937(rand());}
using mat = vector<vector<ll>>;
mat mul_mat(mat a,mat b){
    ll n = a.size();
    mat c(n,vector<ll>(n,0));
    for(ll i = 0;i < n;i++){
        for(ll j = 0;j < n;j++){
            for(ll k = 0;k < n;k++){
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    return c;
}
mat pow_mat(mat a,ll b){
    ll n = a.size();
    mat r(n,vector<ll>(n,0)),p = a;
    for(ll i = 0;i < n;i++) r[i][i] = 1;
    while(b > 0){
        if(b & 1){
            r = mul_mat(r,p);
        }
        b /= 2;
        p = mul_mat(p,p);
    }
    return r;
}
int main(){
    string S;
    ll K;
    cin >> S >> K;
    ll N = (ll)S.size() / 2;
    vector<vector<vector<ll>>> DP(N * 2 + 10,vector<vector<ll>>(N * 2 + 10,vector<ll>(N * 2 + 10,0)));
    DP[0][0][0] = 1;
    for(ll i = 0;i < N * 2;i++){
        for(ll j = 0;j <= N * 2;j++){
            for(ll k = 0;k <= N * 2;k++){
                DP[i + 1][j + 1][k + (S[i] == '(')] += DP[i][j][k];
                DP[i + 1][j + 1][k + (S[i] == '(')] %= MOD;
                if(j != 0){
                    DP[i + 1][j - 1][k + (S[i] == ')')] += DP[i][j][k];
                    DP[i + 1][j - 1][k + (S[i] == ')')] %= MOD;
                }
            }
        }
    }
    mat M(N + 10,vector<ll>(N + 10,0));
    //2i個一致
    for(ll i = 0;i <= N;i++){
        M[i][i] += N * (N - 1) / 2 * 2 + i * (N - i) * 2;
        M[i][i] %= MOD;
        if(i != 0){
            M[i][i - 1] += i * i;
            M[i][i - 1] %= MOD;
        }
        if(i != N){
            M[i][i + 1] += (N - i) * (N - i);
            M[i][i + 1] %= MOD;
        }
    }
    mat a = pow_mat(M,K);
    ll ans = 0;
    for(ll i = 0;i <= N;i++){
        ans += a[i][N] * DP[N * 2][0][i * 2];
        ans %= MOD;
    }
    cout << ans << endl;
}
0