提出 #16602678


ソースコード 拡げる

Copy
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for(int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

const int MAX = 3100000;
const int MOD = 998244353;
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

long long FINV(int n){
    if (n < 0) return 0;
    return finv[n];
}
ll sum[MAX];
// ax + by = gcd(a, b) となるような (x, y) を求める
// a と b は互いに素として ax + by = 1 となる (x, y) を求める
long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x); // 再帰
    y -= a / b * x;
    return d;
}


// 負の数に対応した mod
inline long long mod(long long a, long long m) {
    return (a % m + m) % m;
}


// 逆元計算 (a と m が互いに素であることが必要)
long long modinv(long long a, long long m) {
    long long x, y;
    extGCD(a, m, x, y);
    return mod(x, m); // x % m だが、x が負かもしれないので
}
int main() {
    COMinit();
    ll n, m;
    cin >> n >> m;

    ll ans = 0;

    sum[0] = 1;
    ll now = 1;
    srep(i,1,MAX){
        now = now * (n-2+i) % MOD * modinv(i,MOD) % MOD;
        sum[i] = sum[i-1] + now;
        sum[i] %= MOD;
    }

    int min_nm = min(n,m);

    rep(i,min_nm+1){ // 奇数の数
        if((3*m-i)%2==1) continue;
        ll num = (3*m-i)/2;
        ll tmp = COM(num+n-1,num) * COM(n,i) % MOD;
        ll tmp1 = 0;
        if(num-(m+1) >= 0) tmp1 = sum[num-(m+1)];
        tmp1 = tmp1 * COM(n-1,i) % MOD * n % MOD;
        ll tmp2 = 0;
        if(num-m >= 0) tmp2 = sum[num-m];
        tmp2 = tmp2 * COM(n-1,i-1) % MOD * n % MOD;
        tmp = tmp + MOD - tmp1 + MOD - tmp2;
        tmp %= MOD;
        ans += tmp;
        ans %= MOD;
    }

    cout << ans << endl;
    return 0;
}


提出情報

提出日時
問題 C - GP 2
ユーザ Shibuyap
言語 C++ (GCC 9.2.1)
得点 900
コード長 2587 Byte
結果 AC
実行時間 790 ms
メモリ 100444 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 900 / 900
結果
AC × 4
AC × 26
セット名 テストケース
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
ケース名 結果 実行時間 メモリ
01-01.txt AC 772 ms 100408 KB
01-02.txt AC 777 ms 100244 KB
01-03.txt AC 769 ms 100392 KB
01-04.txt AC 778 ms 100412 KB
01-05.txt AC 780 ms 100368 KB
01-06.txt AC 776 ms 100444 KB
01-07.txt AC 778 ms 100364 KB
01-08.txt AC 779 ms 100412 KB
01-09.txt AC 774 ms 100288 KB
01-10.txt AC 779 ms 100288 KB
01-11.txt AC 780 ms 100288 KB
01-12.txt AC 790 ms 100392 KB
01-13.txt AC 776 ms 100352 KB
01-14.txt AC 778 ms 100412 KB
01-15.txt AC 783 ms 100444 KB
01-16.txt AC 782 ms 100288 KB
01-17.txt AC 784 ms 100364 KB
01-18.txt AC 776 ms 100284 KB
01-19.txt AC 781 ms 100408 KB
01-20.txt AC 777 ms 100284 KB
01-21.txt AC 771 ms 100416 KB
01-22.txt AC 772 ms 100372 KB
sample-01.txt AC 775 ms 100248 KB
sample-02.txt AC 775 ms 100368 KB
sample-03.txt AC 777 ms 100364 KB
sample-04.txt AC 782 ms 100404 KB