結果

問題 No.2839 AND Constraint
コンテスト
ユーザー LyricalMaestro
提出日時 2025-07-20 01:36:27
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,332 bytes
コンパイル時間 475 ms
コンパイル使用メモリ 82,608 KB
実行使用メモリ 106,424 KB
最終ジャッジ日時 2025-07-20 01:36:33
合計ジャッジ時間 6,014 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 2 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2839

MOD = 998244353

def main():
    N, M = map(int, input().split())

    
    dp = [[[0, 0] for _ in range(M + 1)] for _ in range(N)]
    dp[0][0][0] = 1
    dp[0][1][1] = 1

    for i in range(1, N):
        dp_pre = [[0, 0] for _ in range(M + 1)]
        for m in range(M + 1):
            dp_pre[m][0] += dp[i - 1][m][0]
            dp_pre[m][0] %= MOD
            if m + 1 <= M:
                dp_pre[m + 1][1] += dp[i - 1][m][0]
                dp_pre[m + 1][1] %= MOD
            if m + 1 <= M:
                dp_pre[m + 1][1] += dp[i - 1][m][1]
                dp_pre[m + 1][1] %= MOD
        
        for m in range(M + 1):
            x = dp[i - 1][m]
            for n in range(M + 1):
                if m + n > M:
                    break
                dp[i][m + n][0] += (x[0] * dp_pre[n][0]) % MOD
                dp[i][m + n][0] %= MOD

                dp[i][m + n][1] += (x[1] * dp_pre[n][0]) % MOD
                dp[i][m + n][1] %= MOD

                dp[i][m + n][1] += (x[0] * dp_pre[n][1]) % MOD
                dp[i][m + n][1] %= MOD

                dp[i][m + n][1] += (x[1] * dp_pre[n][1]) % MOD
                dp[i][m + n][1] %= MOD

    answer = dp[-1][M][0] + dp[-1][M][1]
    answer %= MOD
    print(answer)




    



if __name__ == "__main__":
    main()
0