結果

問題 No.1873 Bracket Swapping
ユーザー hiikunZhiikunZ
提出日時 2022-03-11 23:31:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 381 ms / 2,000 ms
コード長 2,346 bytes
コンパイル時間 3,479 ms
コンパイル使用メモリ 230,376 KB
実行使用メモリ 78,208 KB
最終ジャッジ日時 2024-09-16 03:56:22
合計ジャッジ時間 7,825 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 40 ms
12,928 KB
testcase_04 AC 20 ms
7,168 KB
testcase_05 AC 17 ms
7,424 KB
testcase_06 AC 159 ms
40,704 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 286 ms
72,064 KB
testcase_09 AC 298 ms
78,080 KB
testcase_10 AC 228 ms
59,008 KB
testcase_11 AC 5 ms
5,376 KB
testcase_12 AC 125 ms
34,304 KB
testcase_13 AC 108 ms
28,928 KB
testcase_14 AC 281 ms
70,144 KB
testcase_15 AC 69 ms
19,328 KB
testcase_16 AC 5 ms
5,376 KB
testcase_17 AC 164 ms
47,616 KB
testcase_18 AC 5 ms
5,376 KB
testcase_19 AC 13 ms
6,272 KB
testcase_20 AC 251 ms
60,800 KB
testcase_21 AC 5 ms
5,376 KB
testcase_22 AC 25 ms
8,832 KB
testcase_23 AC 381 ms
78,208 KB
testcase_24 AC 268 ms
78,208 KB
testcase_25 AC 311 ms
78,208 KB
testcase_26 AC 162 ms
47,744 KB
testcase_27 AC 226 ms
66,304 KB
testcase_28 AC 94 ms
75,648 KB
testcase_29 AC 2 ms
5,376 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