QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#207348 | #6325. Peaceful Results | Famiglistmo | RE | 371ms | 29624kb | C++14 | 3.6kb | 2023-10-08 14:39:06 | 2023-10-08 14:39:06 |
Judging History
answer
#include<bits/stdc++.h>
#define eps 1e-6
using namespace std;
const int mod = 998244353;
const int N = 4e6 + 5;
template <typename A> int mul(A x) {return x; }
template <typename A, typename ...B> int mul(A x, B ...args) { return 1ll * x * mul(args ...) % mod; }
template <typename T> inline void read (T &t) {
t = 0; char f = 0, ch = getchar();
while(ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
while(ch <= '9' && ch >= '0') t = t * 10 + ch - 48, ch = getchar();
t = (f ? -t : t);
}
template <typename T, typename... Args>
inline void read (T& t, Args&... args) { read(t); read(args...); }
int ksm(int a, int b) {
int res = 1;
while(b > 0) {
if(b & 1) res = mul(res, a);
a = mul(a, a), b >>= 1;
}
return res;
}
double a[7][8] = {
0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 1, 0, 1, 0, 0,
0, 0, 1, 0, 1, 0, 1, 0,
0, 1, 0, 0,-1,-1, 1, 0,
0, 0, 1, 1,-1,-1, 0, 0,
0, 1, 0,-1, 1, 0,-1, 0,
0, 0, 1,-1, 0, 1,-1, 0
};
int y[7];
int f[N], g[N], h[N], fac[N], ifac[N];
int n, AR, AP, AS, BR, BP, BS, CR, CP, CS;
int rev[N << 2];
int rt = 3, invg = ksm(3, mod - 2), len, bit;
void ntt(int *f, int op) {
for(int i = 0; i < len; ++ i)
if(i < rev[i]) swap(f[i], f[rev[i]]);
for(int i = 2; i <= len; i <<= 1) {
int base = ksm(op == 1 ? rt : invg, (mod - 1) / i);
for(int j = 0, p = i >> 1; j < len; j += i)
for(int k = 0, pw = 1; k < p; ++ k, pw = mul(pw, base)) {
int x = f[j + k], y = mul(pw, f[j + k + p]);
f[j + k] = (x + y) % mod;
f[j + k + p] = (x - y + mod) % mod;
}
}
if(op == -1)
for(int i = 0, iv = ksm(len, mod - 2); i < len; ++ i)
f[i] = mul(f[i], iv);
}
void work(int *f, int *g) {
ntt(f, 1), ntt(g, 1);
for(int i = 0; i < len; ++ i)
f[i] = mul(f[i], g[i]);
ntt(f, -1);
}
signed main() {
read(n, AR, AP, AS, BR, BP, BS, CR, CP, CS);
a[1][7] = AP - AR, a[2][7] = AS - AR;
a[3][7] = BP - BR, a[4][7] = BS - BR;
a[5][7] = CP - CR, a[6][7] = CS - CR;
for(int i = 1; i <= 6; ++ i) {
int p = i;
for(int j = i + 1; j <= 6; ++ j)
if(fabs(a[j][i]) > fabs(a[p][i]))
p = j;
for(int j = i; j <= 7; ++ j)
swap(a[i][j], a[p][j]);
if(fabs(a[i][i]) < eps) return puts("0"), 0;
for(int j = 1; j <= 6; ++ j) if(i ^ j){
double rate = a[j][i] / a[i][i];
for(int k = i; k <= 7; ++ k)
a[j][k] -= a[i][k] * rate;
}
}
int s = 0;
for(int i = 1; i <= 6; ++ i) {
double cur = a[i][7] / a[i][i];
if(fabs(cur - (int)cur) > eps) return puts("0"), 0;
y[i] = (int)cur;
s += y[i];
}
for(int i = fac[0] = 1; i <= n; ++ i) fac[i] = mul(fac[i - 1], i);
ifac[n] = ksm(fac[n], mod - 2);
for(int i = n - 1; i >= 0; -- i) ifac[i] = mul(ifac[i + 1], i + 1);
for(int i = max({0, -y[1], -y[2]}); i <= min({n, n - y[1], n - y[2]}); ++ i)
f[i] = mul(ifac[i], ifac[i + y[1]], ifac[i + y[2]]);
for(int i = max({0, -y[3], -y[4]}); i <= min({n, n - y[3], n - y[4]}); ++ i)
g[i] = mul(ifac[i], ifac[i + y[3]], ifac[i + y[4]]);
for(int i = max({0, -y[5], -y[6]}); i <= min({n, n - y[5], n - y[6]}); ++ i)
h[i] = mul(ifac[i], ifac[i + y[5]], ifac[i + y[6]]);
len = 1, bit = 0;
while(len <= (n << 1)) len <<= 1, ++ bit;
for(int i = 1; i < len; ++ i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bit - 1);
work(f, g), work(f, h);
printf("%d\n", mul(fac[n], f[AR]));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 14120kb
input:
2 2 0 0 1 1 0 1 0 1
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5644kb
input:
3 0 1 2 3 0 0 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 371ms
memory: 29624kb
input:
333333 111111 111111 111111 111111 111111 111111 111111 111111 111111
output:
383902959
result:
ok 1 number(s): "383902959"
Test #4:
score: -100
Runtime Error
input:
1500000 500000 500000 500000 500000 500000 500000 500000 500000 500000