QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#207351#6325. Peaceful ResultsFamiglistmoWA 1619ms90036kbC++143.6kb2023-10-08 14:40:092023-10-08 14:40:10

Judging History

你现在查看的是最新测评结果

  • [2023-10-08 14:40:10]
  • 评测
  • 测评结果:WA
  • 用时:1619ms
  • 内存:90036kb
  • [2023-10-08 14:40:09]
  • 提交

answer

#include<bits/stdc++.h>
#define eps 1e-6
using namespace std;
const int mod = 998244353;
const int N = 3e7 + 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];
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: 0ms
memory: 13732kb

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: 1ms
memory: 5484kb

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: 374ms
memory: 31944kb

input:

333333
111111 111111 111111
111111 111111 111111
111111 111111 111111

output:

383902959

result:

ok 1 number(s): "383902959"

Test #4:

score: 0
Accepted
time: 1619ms
memory: 90036kb

input:

1500000
500000 500000 500000
500000 500000 500000
500000 500000 500000

output:

355543262

result:

ok 1 number(s): "355543262"

Test #5:

score: 0
Accepted
time: 1606ms
memory: 88468kb

input:

1499999
499999 499999 500001
499999 499999 500001
499999 499999 500001

output:

934301164

result:

ok 1 number(s): "934301164"

Test #6:

score: 0
Accepted
time: 1618ms
memory: 88784kb

input:

1500000
1 0 1499999
1499999 1 0
0 1499999 1

output:

1500000

result:

ok 1 number(s): "1500000"

Test #7:

score: 0
Accepted
time: 1610ms
memory: 87552kb

input:

1499999
0 749999 750000
750000 0 749999
749999 750000 0

output:

713966599

result:

ok 1 number(s): "713966599"

Test #8:

score: 0
Accepted
time: 2ms
memory: 13868kb

input:

1
1 0 0
0 0 1
0 1 0

output:

1

result:

ok 1 number(s): "1"

Test #9:

score: 0
Accepted
time: 0ms
memory: 13876kb

input:

1
0 1 0
0 1 0
0 1 0

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 1ms
memory: 5436kb

input:

1
0 0 1
1 0 0
1 0 0

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 1619ms
memory: 88844kb

input:

1499999
500000 500000 499999
499999 499999 500001
499999 499999 500001

output:

617065435

result:

ok 1 number(s): "617065435"

Test #12:

score: 0
Accepted
time: 2ms
memory: 13848kb

input:

2
1 1 0
0 0 2
0 0 2

output:

0

result:

ok 1 number(s): "0"

Test #13:

score: 0
Accepted
time: 1616ms
memory: 88376kb

input:

1500000
500000 500001 499999
499999 500000 500001
499999 500000 500001

output:

925862004

result:

ok 1 number(s): "925862004"

Test #14:

score: 0
Accepted
time: 759ms
memory: 49324kb

input:

629197
210878 201408 216911
145293 266423 217481
194751 220179 214267

output:

447295633

result:

ok 1 number(s): "447295633"

Test #15:

score: 0
Accepted
time: 755ms
memory: 48484kb

input:

579097
200209 204257 174631
149110 148890 281097
138034 263752 177311

output:

71830925

result:

ok 1 number(s): "71830925"

Test #16:

score: 0
Accepted
time: 370ms
memory: 29424kb

input:

354224
100316 63899 190009
69306 123829 161089
140523 76088 137613

output:

44852283

result:

ok 1 number(s): "44852283"

Test #17:

score: 0
Accepted
time: 1594ms
memory: 85852kb

input:

1229851
383009 323934 522908
551226 311238 367387
547622 353128 329101

output:

39721313

result:

ok 1 number(s): "39721313"

Test #18:

score: 0
Accepted
time: 765ms
memory: 51376kb

input:

858452
195309 312080 351063
384805 51797 421850
200466 301164 356822

output:

506491992

result:

ok 1 number(s): "506491992"

Test #19:

score: 0
Accepted
time: 1611ms
memory: 89352kb

input:

1424218
661653 323895 438670
467846 488045 468327
369769 343207 711242

output:

782021141

result:

ok 1 number(s): "782021141"

Test #20:

score: 0
Accepted
time: 1590ms
memory: 83856kb

input:

1079733
333391 427895 318447
579853 153924 345956
406031 300755 372947

output:

111229812

result:

ok 1 number(s): "111229812"

Test #21:

score: 0
Accepted
time: 753ms
memory: 47332kb

input:

572270
168517 197624 206129
238722 154914 178634
192692 145891 233687

output:

93444378

result:

ok 1 number(s): "93444378"

Test #22:

score: -100
Wrong Answer
time: 371ms
memory: 33844kb

input:

470911
95201 196020 179690
143795 173744 153372
142604 154489 173818

output:

319520902

result:

wrong answer 1st numbers differ - expected: '629148200', found: '319520902'