結果

問題 No.3403 Count 1210 Sequence
コンテスト
ユーザー applejam
提出日時 2025-12-10 02:00:12
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 963 ms / 2,000 ms
コード長 1,352 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,408 ms
コンパイル使用メモリ 576,636 KB
実行使用メモリ 25,272 KB
最終ジャッジ日時 2025-12-10 02:00:56
合計ジャッジ時間 33,781 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vmi = vector<mint>;
using vvmi = vector<vmi>;
using vvvmi = vector<vvmi>;
#define all(a) (a).begin(), (a).end()
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
vmi kaijo(2050, mint(1));
vmi iv(2050, mint(1));
vvi vy(205000);

mint nck(int a, int b){
    return kaijo[a]*iv[b]*iv[a-b];
}
void solve(){
    int n, a; cin >> n >> a;
    if(n == 2){
        cout << 1 << endl;
        return;
    }
    mint ans = 0;
    for(auto i : vy[a]){
        int c = a/i, u = n-1-c;
        if(u % 2 != 0)continue;

        int k = u/2;
        if(k < 0 || k >= n)continue;
        
        ans += nck(n-1, k) - nck(n-1, n-2-k-c);
    }cout << ans.val() <<endl;

}

int main(){
    rep2(i, 2, 2050){
        kaijo[i] = kaijo[i-1]*mint(i);
        iv[i] = kaijo[i].inv();
    }

    rep2(i, 1, 205000){
        for(int j = i; j <= 205000; j += i)vy[j].push_back(i);
    }

    int t; cin >> t;
    while(t--)solve();
    return 0;
}
0