QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#778785#9476. 012 GridIllusionaryDominance#AC ✓219ms78676kbC++203.0kb2024-11-24 16:15:382024-11-24 16:15:39

Judging History

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

  • [2024-11-24 16:15:39]
  • 评测
  • 测评结果:AC
  • 用时:219ms
  • 内存:78676kb
  • [2024-11-24 16:15:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 8e5 + 10;
const ll MOD = 998244353;

ll fact[N], ifact[N];
ll ksm(ll x, ll y){
    ll re = 1;
    for (; y; y >>= 1){
        if(y & 1) re = re * x % MOD;
        x = x * x % MOD;
    }
    return re;
}

ll C(int n, int m){if(n < 0 || m < 0 || n < m)return 0; return fact[n] * ifact[m] % MOD * ifact[n - m] % MOD;}

const long long g = 3, _g = ksm(3, MOD - 2);
int n, m;
int R[N << 2];
int limit = 1, L;
void NTT(long long *A, int op)
{
	for (int i = 0; i < limit; ++ i) if(i < R[i]) swap(A[i], A[R[i]]);
	for (int len = 1; len < limit; len <<= 1)
	{
		long long X = ksm(op == 1 ? g : _g, (MOD - 1) / (len << 1));
		for (int i = 0; i < limit; i += (len << 1))
		{
			long long pw = 1;
			for (int j = 0; j < len; ++ j)
			{
				long long x = A[i + j], y = pw * A[i + j + len] % MOD;
				A[i + j] = (x + y) % MOD; A[i + j + len] = (x - y + MOD) % MOD;
				pw = pw * X % MOD;
			}
		}
	}
}
void mul(long long *A, long long *B, int n, int m)
{
	limit = 1, L = 0;
	memset(R, 0, sizeof(R));
	while(limit <= n + m)limit <<= 1, ++ L;
	for (int i = 0; i < limit; ++ i)R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1));
	NTT(A, 1);
	NTT(B, 1);
	for (int i = 0; i < limit; ++ i)
	(A[i] *= B[i]) %= MOD;
	NTT(A, 0);
	long long div = ksm(limit, MOD - 2);
	for (int i = 0; i <= n + m; ++ i) (A[i] *= div) %= MOD;
}

long long A[N << 2], B[N << 2];


ll calc(int n, int m) {return C(n + m - 2, n - 1);}
ll Calc(int n, int m) {return (calc(n - 1, m - 1) * calc(n - 1, m - 1) % MOD - calc(n - 2, m) * calc(n, m - 2) % MOD + MOD) % MOD;}

int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);

    fact[0] = 1;
    for (int i = 1; i < N; ++ i) fact[i] = fact[i - 1] * i % MOD;
    ifact[N - 1] = ksm(fact[N - 1], MOD - 2);
    for (int i = N - 2; ~i; -- i) ifact[i] = ifact[i + 1] * (i + 1) % MOD;

    int n, m;
    cin >> n >> m;
    ll ans = 0;

    
    // for (int i = 0; i <= n; ++ i)
    //     for (int j = 0; j <= m; ++ j)
    //         (ans += Calc(n - i + 1, m - j + 1) * (1 + (i != 0 || j != 0))) %= MOD;

	memset(A, 0, sizeof(A));
	memset(B, 0, sizeof(B));
    for (int i = 0; i <= n - 1; ++ i) A[i] = ifact[i] * ifact[i] % MOD;
    for (int i = 0; i <= m - 1; ++ i) B[i] = ifact[i] * ifact[i] % MOD;
    mul(A, B, n - 1, m - 1);
    for (int l = 0; l <= n + m - 2; ++ l) (ans += A[l] * fact[l] % MOD * fact[l]) %= MOD;
    
    
	memset(A, 0, sizeof(A));
	memset(B, 0, sizeof(B));
    for (int i = 1; i <= n - 1; ++ i) A[i] = ifact[i - 1] * ifact[i + 1] % MOD;
    for (int i = 1; i <= m - 1; ++ i) B[i] = ifact[i - 1] * ifact[i + 1] % MOD;
    mul(A, B, n - 1, m - 1);
    for (int l = 0; l <= n + m - 2; ++ l) (ans += MOD - A[l] * fact[l] % MOD * fact[l] % MOD) %= MOD;

    ans = (ans * 2 - Calc(n + 1, m + 1) + MOD) % MOD;

    for (int i = 2; i <= n - 1; ++ i) (ans += Calc(i, m + 1) * (n - i)) %= MOD;
    for (int i = 2; i <= m - 1; ++ i) (ans += Calc(n + 1, i) * (m - i)) %= MOD;

    cout << (ans + 2) % MOD;

}

详细

Test #1:

score: 100
Accepted
time: 17ms
memory: 78568kb

input:

2 2

output:

11

result:

ok "11"

Test #2:

score: 0
Accepted
time: 13ms
memory: 78592kb

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

score: 0
Accepted
time: 205ms
memory: 78536kb

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

score: 0
Accepted
time: 22ms
memory: 78592kb

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

score: 0
Accepted
time: 18ms
memory: 78628kb

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

score: 0
Accepted
time: 7ms
memory: 78620kb

input:

3 3

output:

64

result:

ok "64"

Test #7:

score: 0
Accepted
time: 18ms
memory: 78540kb

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

score: 0
Accepted
time: 18ms
memory: 78600kb

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

score: 0
Accepted
time: 14ms
memory: 78624kb

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

score: 0
Accepted
time: 11ms
memory: 78540kb

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

score: 0
Accepted
time: 3ms
memory: 78544kb

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

score: 0
Accepted
time: 11ms
memory: 78576kb

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

score: 0
Accepted
time: 17ms
memory: 78660kb

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

score: 0
Accepted
time: 19ms
memory: 78544kb

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

score: 0
Accepted
time: 11ms
memory: 78624kb

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

score: 0
Accepted
time: 13ms
memory: 78600kb

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

score: 0
Accepted
time: 23ms
memory: 78600kb

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

score: 0
Accepted
time: 17ms
memory: 78536kb

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

score: 0
Accepted
time: 21ms
memory: 78564kb

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

score: 0
Accepted
time: 19ms
memory: 78536kb

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

score: 0
Accepted
time: 22ms
memory: 78628kb

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

score: 0
Accepted
time: 22ms
memory: 78616kb

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

score: 0
Accepted
time: 17ms
memory: 78600kb

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

score: 0
Accepted
time: 219ms
memory: 78592kb

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 95ms
memory: 78628kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 100ms
memory: 78536kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

score: 0
Accepted
time: 54ms
memory: 78640kb

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

score: 0
Accepted
time: 206ms
memory: 78568kb

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

score: 0
Accepted
time: 100ms
memory: 78588kb

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

score: 0
Accepted
time: 111ms
memory: 78528kb

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

score: 0
Accepted
time: 103ms
memory: 78592kb

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

score: 0
Accepted
time: 101ms
memory: 78576kb

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 103ms
memory: 78616kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

score: 0
Accepted
time: 214ms
memory: 78600kb

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

score: 0
Accepted
time: 208ms
memory: 78576kb

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

score: 0
Accepted
time: 201ms
memory: 78592kb

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

score: 0
Accepted
time: 3ms
memory: 78600kb

input:

1 1

output:

3

result:

ok "3"

Test #38:

score: 0
Accepted
time: 53ms
memory: 78600kb

input:

1 100000

output:

8828237

result:

ok "8828237"

Test #39:

score: 0
Accepted
time: 53ms
memory: 78676kb

input:

100000 2

output:

263711286

result:

ok "263711286"

Test #40:

score: 0
Accepted
time: 12ms
memory: 78536kb

input:

50 50

output:

634767411

result:

ok "634767411"

Extra Test:

score: 0
Extra Test Passed