Contest Duration: - (local time) (160 minutes) Back to Home

Submission #16602678

Source Code Expand

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;
}

```

#### Submission Info

Submission Time 2020-09-10 02:51:26+0900 C - GP 2 Shibuyap C++ (GCC 9.2.1) 900 2587 Byte AC 790 ms 100444 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
 AC × 4
 AC × 26
Set Name Test Cases
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
Case Name Status Exec Time Memory
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