結果

問題 No.1771 A DELETEQ
コンテスト
ユーザー pockyny
提出日時 2021-12-03 19:35:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,539 ms / 3,500 ms
コード長 1,123 bytes
コンパイル時間 713 ms
コンパイル使用メモリ 67,388 KB
最終ジャッジ日時 2025-01-26 03:11:03
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26 RE * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>

using namespace std;
typedef long long ll;
ll dp[4010][4010][2][2] = {},mod = 998244353;
int main(){
    int i,j,x,y; cin >> x >> y;
    if(x>4000 || y>4000) exit(1);
    dp[0][0][0][1] = dp[0][0][1][1] = 1;
    for(i=0;i<=x;i++){
        for(j=0;j<=y;j++){
            (dp[i + 1][j][0][0] += dp[i][j][0][0] + dp[i][j][0][1]) %= mod;
            (dp[i][j + 1][1][0] += dp[i][j][0][0] + dp[i][j][0][1]) %= mod;
            (dp[i][j + 1][1][1] += dp[i][j][0][0]) %= mod;
            (dp[i][j + 1][1][0] += dp[i][j][1][0] + dp[i][j][1][1]) %= mod;
            (dp[i + 1][j][0][0] += dp[i][j][1][0] + dp[i][j][1][1]) %= mod;
            (dp[i + 1][j][0][1] += dp[i][j][1][0]) %= mod;
        }
    }
    ll ans = 0;
    for(i=0;i<=min(x,y);i++) (ans += dp[x - i][y - i][0][0] + dp[x - i][y - i][0][1] + dp[x - i][y - i][1][0] + dp[x - i][y - i][1][1]) %= mod;
    (ans *= (mod + 1)/2) %= mod;
    cout << ans << endl;
    /*for(i=0;i<=min(x,y);i++){
        cout << dp[x - i][y - i][0][0] << " " << dp[x - i][y - i][0][1] << " " << dp[x - i][y - i][1][0] << " " << dp[x - i][y - i][1][1] << endl;
    }*/
}
0