結果

問題 No.1873 Bracket Swapping
ユーザー hiikunZhiikunZ
提出日時 2022-03-11 23:31:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 406 ms / 2,000 ms
コード長 2,346 bytes
コンパイル時間 3,889 ms
コンパイル使用メモリ 229,004 KB
実行使用メモリ 78,204 KB
最終ジャッジ日時 2023-10-14 08:49:38
合計ジャッジ時間 8,961 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 47 ms
12,728 KB
testcase_04 AC 22 ms
7,252 KB
testcase_05 AC 21 ms
7,180 KB
testcase_06 AC 179 ms
40,528 KB
testcase_07 AC 2 ms
4,352 KB
testcase_08 AC 321 ms
71,992 KB
testcase_09 AC 327 ms
78,064 KB
testcase_10 AC 250 ms
58,848 KB
testcase_11 AC 4 ms
4,352 KB
testcase_12 AC 141 ms
34,564 KB
testcase_13 AC 116 ms
28,840 KB
testcase_14 AC 316 ms
69,892 KB
testcase_15 AC 78 ms
19,088 KB
testcase_16 AC 4 ms
4,352 KB
testcase_17 AC 180 ms
47,700 KB
testcase_18 AC 6 ms
4,352 KB
testcase_19 AC 15 ms
6,272 KB
testcase_20 AC 273 ms
60,652 KB
testcase_21 AC 5 ms
4,348 KB
testcase_22 AC 28 ms
8,720 KB
testcase_23 AC 406 ms
77,900 KB
testcase_24 AC 304 ms
78,004 KB
testcase_25 AC 336 ms
78,204 KB
testcase_26 AC 178 ms
47,648 KB
testcase_27 AC 253 ms
66,228 KB
testcase_28 AC 99 ms
75,328 KB
testcase_29 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

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