結果

問題 No.2877 Gunegune Hyperion
ユーザー karinohitokarinohito
提出日時 2024-09-06 23:04:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,963 ms / 6,000 ms
コード長 1,396 bytes
コンパイル時間 4,046 ms
コンパイル使用メモリ 254,064 KB
実行使用メモリ 46,696 KB
最終ジャッジ日時 2024-09-06 23:05:50
合計ジャッジ時間 39,312 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 5 ms
6,816 KB
testcase_03 AC 393 ms
14,148 KB
testcase_04 AC 428 ms
14,356 KB
testcase_05 AC 946 ms
24,748 KB
testcase_06 AC 1,032 ms
24,380 KB
testcase_07 AC 1,013 ms
24,296 KB
testcase_08 AC 987 ms
26,296 KB
testcase_09 AC 860 ms
25,812 KB
testcase_10 AC 1,825 ms
42,572 KB
testcase_11 AC 851 ms
24,560 KB
testcase_12 AC 187 ms
8,728 KB
testcase_13 AC 412 ms
14,408 KB
testcase_14 AC 203 ms
8,780 KB
testcase_15 AC 869 ms
24,880 KB
testcase_16 AC 1,898 ms
43,468 KB
testcase_17 AC 1,863 ms
43,776 KB
testcase_18 AC 394 ms
14,140 KB
testcase_19 AC 484 ms
14,084 KB
testcase_20 AC 26 ms
6,944 KB
testcase_21 AC 1,808 ms
43,996 KB
testcase_22 AC 929 ms
24,516 KB
testcase_23 AC 1,867 ms
44,236 KB
testcase_24 AC 1,843 ms
44,136 KB
testcase_25 AC 1,944 ms
46,404 KB
testcase_26 AC 429 ms
14,604 KB
testcase_27 AC 960 ms
25,736 KB
testcase_28 AC 1,959 ms
46,692 KB
testcase_29 AC 1,942 ms
46,572 KB
testcase_30 AC 1,950 ms
46,568 KB
testcase_31 AC 1,963 ms
46,696 KB
testcase_32 AC 1,959 ms
46,564 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/modint>
#include<atcoder/convolution>
using namespace atcoder;
using mint=modint998244353;
using namespace std;
using ll=long long;

using poly=vector<mint>;
void add(poly &A,poly B){
    if(A.size()<B.size())A.resize(B.size());
    for(int i=0;i<B.size();i++)A[i]+=B[i];
    return;
}

vector<vector<poly>> mul(vector<vector<poly>> &A,vector<vector<poly>> B){
    ll N=A.size();
    vector<vector<poly>> R(N,vector<poly>(N,{0}));
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                add(R[i][j],convolution(A[i][k],B[k][j]));
            }
        }
    }
    return R;
}

int main() {
    ll N,H;
    cin>>N>>H;
    mint iv2=mint(2).inv();
    mint iv3=mint(3).inv();
    mint iv5=mint(5).inv();
    vector<vector<poly>> A={
        {{iv2},{iv3},{0}},
        {{0,iv2},{0,iv3},{0,iv3*2}},
        {{0},{0,iv3},{0,iv3}}
    };
    vector<vector<poly>> E={
        {{1},{0},{0}},
        {{0},{1},{0}},
        {{0},{0},{1}}
    };
    N--;
    while(N>0){
        if(N%2)E=mul(E,A);
        A=mul(A,A);
        N/=2;
    }
    poly AN={0};
    vector<poly> T={{iv5*2},{0,iv5*2},{0,iv5}};
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            add(AN,convolution(T[j],E[i][j]));
        }
    }
    mint an=0;
    for(int h=H;h<ll(AN.size());h++)an+=AN[h];
    cout<<an.val()<<endl;
    
}
0