結果

問題 No.2503 Typical Path Counting Problem on a Grid
ユーザー pockynypockyny
提出日時 2024-10-18 03:07:34
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 455 ms / 2,000 ms
コード長 3,065 bytes
コンパイル時間 7,138 ms
コンパイル使用メモリ 118,592 KB
実行使用メモリ 42,656 KB
最終ジャッジ日時 2024-10-18 03:07:46
合計ジャッジ時間 7,216 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 67 ms
42,504 KB
testcase_01 AC 154 ms
42,496 KB
testcase_02 AC 129 ms
42,612 KB
testcase_03 AC 270 ms
42,432 KB
testcase_04 AC 432 ms
42,504 KB
testcase_05 AC 229 ms
42,656 KB
testcase_06 AC 436 ms
42,536 KB
testcase_07 AC 417 ms
42,468 KB
testcase_08 AC 418 ms
42,516 KB
testcase_09 AC 455 ms
42,492 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using mint = modint998244353;
typedef long long ll;
ll dp[110][110];
void bruteDp(int n,int m){
    int i,j,k;
    dp[0][0] = 1;
    for(i=0;i<=n + m;i++){
        for(j=0;j<=min(i,n);j++){
            if(i==j && !j) continue;
            ll sum1 = 0,sum2 = 0;
            for(k=0;k<=i - 1;k++){
                if(k<=n && (i - 1 - k)<=m) sum1 += dp[k][i - 1 - k];
            }
            for(k=0;k<=i - 2;k++){
                if(k<=n && (i - 2 - k)<=m) sum2 += dp[k][i - 2 - k];
            }
            dp[j][i - j] += sum1;
            if(j>=1 && i - j>=1) dp[j][i - j] += sum1;
            if(j>=1 && i - j>=1) dp[j][i - j] += sum2;
        }
    }
}

ll dp2[110];
void bruteDp2(int n,int m){
    int i;
    dp2[0] = 1; dp2[1] = 2;
    for(i=2;i<=n + m;i++){
        if(i<=n){
            dp2[i] = 2*i*dp2[i - 1] + (i - 1)*dp2[i - 2];
        }else if(i<=m){
            dp2[i] = (2*n + 1)*dp2[i - 1] + n*dp2[i - 2];
        }else{
            dp2[i] = 2*(n + m + 1 - i)*dp2[i - 1] + (n + m + 1 - i)*dp2[i - 2];
        }
    }
}

#include <vector>
#include <atcoder/convolution>
mint BostanMori(vector<mint> P,vector<mint> Q,ll N){
    while(N){
        vector<mint> _Q(Q.size());
        for(int i=0;i<Q.size();i++) _Q[i] = i&1 ? -Q[i] : Q[i];
        vector<mint> nP = convolution(P,_Q);
        vector<mint> nQ = convolution(Q,_Q);
        Q.resize(nQ.size()/2 + 1);
        for(int i=0;i<nQ.size();i+=2) Q[i/2] = nQ[i];
        if(N&1){
            P.resize(nP.size()/2);
            for(int i=1;i<nP.size();i+=2) P[i/2] = nP[i];
        }else{
            P.resize((nP.size() + 1)/2);
            for(int i=0;i<nP.size();i+=2) P[i/2] = nP[i];
        }
        N /= 2;
    }
    return P[0]/Q[0];
}

const int MX = 10000000;
mint f[MX + 10];
int main(){
    f[0] = 1; f[1] = 2;
    for(int i=2;i<=MX;i++) f[i] = 2*i*f[i - 1] + (i - 1)*f[i - 2];
    int t; cin >> t;
    while(t){
        t--;
        ll i,j,n,m; cin >> n >> m;
        if(n>m) swap(n,m);
        if(n==0){
            cout << 1 << "\n";
            continue;
        }
        // f[n - 1],f[n],f[n + 1],...,f[m - 1],f[m]という数列のf[m - 1]とf[m]を求める
        vector<mint> P = {f[n - 1],f[n] - f[n - 1]*(2*n + 1)};
        vector<mint> Q = {1,-2*n - 1,-n};
        mint fm = BostanMori(P,Q,m - n + 1);
        mint gm = BostanMori(P,Q,m - n);
        // f[m - 1]→f[m + 1] (=f[n - 1]),f[m]→f[m + 1] or f[m + 2](=f[n - 2])
        mint ans = gm*f[n - 1]*n + fm*f[n - 1]*2*n + (n>=2 ? fm*f[n - 2]*(n - 1) : 0);
        // bruteDp(n,m); bruteDp2(n,m);
        // for(i=0;i<=n + m;i++){
        //     int sum = 0;
        //     for(j=max(0,i - m);j<=min(i,n);j++){
        //         cout << dp[j][i - j] << " ";
        //         sum += dp[j][i - j];
        //     }
        //     cout << "sum == " << sum;
        //     cout << "\n";
        // }
        // for(i=0;i<=n + m;i++) cout << dp2[i] << " ";
        // cout << "\n";
        cout << ans.val() << "\n";
    }
}
0