-
Notifications
You must be signed in to change notification settings - Fork 87
/
065-03.cpp
70 lines (59 loc) · 1.74 KB
/
065-03.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <atcoder/all>
#include <iostream>
#include <vector>
using namespace std;
long long mod = 998244353;
long long fact[1 << 19], inv[1 << 19];
long long modpow(long long a, long long b, long long m) {
long long p = 1, q = a;
for (int i = 0; i < 32; i++) {
if ((b & (1LL << i)) != 0LL) {
p *= q; p %= m;
}
q *= q; q %= m;
}
return p;
}
long long Div(long long a, long long b, long long m) {
return (a * modpow(b, m - 2, m)) % m;
}
long long ncr(long long n, long long r) {
if (n < r || r < 0) return 0;
return (fact[n] * inv[r] % mod) * inv[n - r] % mod;
}
void init() {
fact[0] = 1LL;
for (int i = 1; i <= 500000; i++) fact[i] = (1LL * i * fact[i - 1]) % mod;
for (int i = 0; i <= 500000; i++) inv[i] = Div(1, fact[i], mod);
}
long long R, G, B, K;
long long X, Y, Z;
long long ar[1 << 19], ag[1 << 19], ab[1 << 19];
int main() {
init();
// Step #1. 入力
cin >> R >> G >> B >> K;
cin >> X >> Y >> Z;
// Step #2. 前処理
long long R_left = K - Y, R_right = R;
long long G_left = K - Z, G_right = G;
long long B_left = K - X, B_right = B;
for (int i = 0; i <= R; i++) ar[i] = ncr(R, i);
for (int i = 0; i <= G; i++) ag[i] = ncr(G, i);
for (int i = 0; i <= B; i++) ab[i] = ncr(B, i);
// Step #3. FFT
vector<long long> p1(R + 1, 0), p2(G + 1, 0), p3;
for (int i = R_left; i <= R_right; i++) p1[i] = ar[i];
for (int i = G_left; i <= G_right; i++) p2[i] = ag[i];
p3 = atcoder::convolution(p1, p2);
// Step #4. 答えを求める
long long Answer = 0;
for (int i = B_left; i <= B_right; i++) {
long long ret1 = 0, ret2 = ab[i];
if (0 <= K - i && K - i <= (int)p3.size()) ret1 = p3[K - i];
Answer += ret1 * ret2;
Answer %= mod;
}
cout << Answer << endl;
return 0;
}