結果

問題 No.3403 Count 1210 Sequence
コンテスト
ユーザー yt142857
提出日時 2025-11-28 12:40:28
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 2,129 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,417 ms
コンパイル使用メモリ 275,744 KB
実行使用メモリ 27,840 KB
最終ジャッジ日時 2025-12-09 23:31:30
合計ジャッジ時間 7,515 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/*
mod = 998244353
query = int(input())
dp = []
for i in range(2026):
  dp.append([0]*2026)
dp[0][1] = 1
for i in range(2,2026):
  for j in range(2026):
    if j-1 >= 0 and j+1<2026:
      dp[j][i] = (dp[j-1][i-1]+dp[j+1][i-1])%mod
    elif j+1<2026:
      dp[j][i] = dp[j+1][i-1]
    else:
      dp[j][i] = dp[j-1][i-1]
for _ in range(query):
  n,a = map(int,input().split())
  ans = 0
  for i in range(1,2026):
    if a % i == 0:
      ans = (ans+dp[i][n])%mod
  print(ans)
*/

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const int LIM = 2026;
    const int MOD = 998244353;

    // dp[j][i] matches original: first index = position j (0..2025), second = step/time i (0..2025)
    static int dp[LIM][LIM];
    // initialize to 0 (static does it, but be explicit)
    for (int j = 0; j < LIM; ++j)
        for (int i = 0; i < LIM; ++i)
            dp[j][i] = 0;

    dp[0][1] = 1;

    for (int i = 2; i < LIM; ++i) {
        for (int j = 0; j < LIM; ++j) {
            if (j - 1 >= 0 && j + 1 < LIM) {
                dp[j][i] = ( (long long)dp[j-1][i-1] + dp[j+1][i-1] ) % MOD;
            } else if (j + 1 < LIM) {
                dp[j][i] = dp[j+1][i-1];
            } else {
                // j-1 >= 0 must hold here (this is the case j == LIM-1)
                dp[j][i] = dp[j-1][i-1];
            }
        }
    }

    int query;
    if (!(cin >> query)) return 0;
    while (query--) {
        int n;
        long long a;
        cin >> n >> a;
        // follow original logic: sum dp[i][n] for i = 1..2025 when a % i == 0
        long long ans = 0;
        if (n >= LIM) {
            // Python version would raise IndexError for out-of-range n.
            // In contest inputs n is guaranteed to be within bounds; handle safely by printing 0.
            cout << 0 << '\n';
            continue;
        }
        for (int i = 1; i < LIM; ++i) {
            if (a % i == 0) {
                ans += dp[i][n];
                if (ans >= MOD) ans -= MOD;
            }
        }
        cout << (ans % MOD) << '\n';
    }

    return 0;
}
0