QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#658917#9476. 012 Griducup-team4474#AC ✓149ms19192kbC++205.3kb2024-10-19 17:56:052024-10-19 17:56:06

Judging History

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

  • [2024-10-19 17:56:06]
  • 评测
  • 测评结果:AC
  • 用时:149ms
  • 内存:19192kb
  • [2024-10-19 17:56:05]
  • 提交

answer

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

const int mod = 998244353;
const int N = 4e5 + 5;
int fac[N], ifac[N];
int inv(int x)
{
	int res = 1, y = mod - 2;
	while (y)
	{
		if (y & 1) res = 1ll * res * x % mod;
		x = 1ll * x * x % mod;
		y >>= 1;
	}
	return res;
}
int binom(int x, int y)
{
	if (x < 0 or y < 0 or x < y) return 0;
	return 1ll * fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
int cal(int x, int y)
{
	int ret = 1ll * binom(x + y - 2, x - 1) * binom(x + y - 2, y - 1) % mod;
	ret = (ret + mod - 1ll * binom(x + y - 2, x - 2) * binom(x + y - 2, y - 2) % mod) % mod;
	return ret;
}

const int P = 998244353;
using i64 = long long;
using Poly = vector<int>;
#define MUL(a, b) (i64(a) * (b) % P)
#define ADD(a, b) (((a) += (b)) >= P ? (a) -= P : 0)
#define SUB(a, b) (((a) -= (b)) < 0 ? (a) += P : 0)
Poly getInv(int L)
{
    Poly inv(L);
    inv[1] = 1;
    for (int i = 2; i < L; i++)
        inv[i] = MUL((P - P / i), inv[P % i]);
    return inv;
}
int POW(i64 a, int b = P - 2, i64 x = 1)
{
    for (; b; b >>= 1, a = a * a % P)
        if (b & 1)
            x = x * a % P;
    return x;
}
namespace NTT
{
    const int g = 3;
    Poly Omega(int L)
    {
        int wn = POW(g, P / L);
        Poly w(L);
        w[L >> 1] = 1;
        for (int i = L / 2 + 1; i < L; i++)
            w[i] = MUL(w[i - 1], wn);
        for (int i = L / 2 - 1; i >= 1; i--)
            w[i] = w[i << 1];
        return w;
    }
    auto W = Omega(1 << 20);
    void DIF(int *a, int n)
    {
        for (int k = n >> 1; k; k >>= 1)
            for (int i = 0, y; i < n; i += k << 1)
                for (int j = 0; j < k; j++)
                    y = a[i + j + k], a[i + j + k] = MUL(a[i + j] - y + P, W[k + j]), ADD(a[i + j], y);
    }
    void IDFT(int *a, int n)
    {
        for (int k = 1; k < n; k <<= 1)
            for (int i = 0, x, y; i < n; i += k << 1)
                for (int j = 0; j < k; j++)
                    x = a[i + j], y = MUL(a[i + j + k], W[k + j]),
                    a[i + j + k] = x - y < 0 ? x - y + P : x - y, ADD(a[i + j], y);
        int Inv = P - (P - 1) / n;
        for (int i = 0; i < n; i++)
            a[i] = MUL(a[i], Inv);
        reverse(a + 1, a + n);
    }
}
namespace Polynomial
{
    int norm(int n) { return 1 << (__lg(n - 1) + 1); }
    void norm(Poly &a)
    {
        if (!a.empty())
            a.resize(norm(a.size()), 0);
        else
            a = {0};
    }
    void DFT(Poly &a) { NTT::DIF(a.data(), a.size()); }
    void IDFT(Poly &a) { NTT::IDFT(a.data(), a.size()); }
    Poly &dot(Poly &a, Poly &b)
    {
        for (int i = 0; i < a.size(); i++)
            a[i] = MUL(a[i], b[i]);
        return a;
    }
    Poly operator*(Poly a, Poly b)
    {
        int n = a.size() + b.size() - 1, L = norm(n);
        if (a.size() <= 8 || b.size() <= 8)
        {
            Poly c(n);
            for (int i = 0; i < a.size(); i++)
                for (int j = 0; j < b.size(); j++)
                    c[i + j] = (c[i + j] + (i64)a[i] * b[j] % P) % P;
            return c;
        }
        a.resize(L), b.resize(L);
        DFT(a), DFT(b), dot(a, b), IDFT(a);
        return a.resize(n), a;
    }
}
using namespace Polynomial;

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	fac[0] = 1;
	for (int i = 1; i <= 400000; i++)
		fac[i] = 1ll * fac[i - 1] * i % mod;
	ifac[400000] = inv(fac[400000]);
	for (int i = 399999; i >= 0; i--)
		ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
	
	int n, m;
	cin >> n >> m;
	int ans = 2;
	for (int i = 1; i <= n; i++) ans = (ans + 1ll * (n - i + 1) * cal(i, m) % mod) % mod;
	for (int i = 1; i < m; i++) ans = (ans + 1ll * (m - i) * cal(n, i) % mod) % mod;
	
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j < m; j++) ans = (ans + cal(i, j)) % mod;
//	}
//	for (int i = 1; i < m; i++)
//	{
//		for (int j = 1; j < n; j++) ans = (ans + cal(j, i)) % mod;
//	}
{
	Poly f(n + 1), g(m);
	for (int i = 1; i <= n; i++) f[i] = 1ll * ifac[i - 1] * ifac[i - 1] % mod;
	for (int i = 1; i < m; i++) g[i] = 1ll * ifac[i - 1] * ifac[i - 1] % mod;
	auto h = f * g;
	int tmp = 0;
	for (int i = 2; i <= n + m - 1; i++) tmp = (tmp + 1ll * h[i] * fac[i - 2] % mod * fac[i - 2] % mod) % mod;
	ans = (ans + tmp) % mod;
	 
	f.assign(n + 1, 0);
	g.assign(m, 0);
	for (int i = 2; i <= n; i++) f[i] = 1ll * ifac[i - 2] * ifac[i] % mod;
	for (int i = 2; i < m; i++) g[i] = 1ll * ifac[i - 2] * ifac[i] % mod;
	h = f * g;
	tmp = 0;
	for (int i = 2; i <= n + m - 1; i++) tmp = (tmp + 1ll * h[i] * fac[i - 2] % mod * fac[i - 2] % mod) % mod;
	ans = (ans + mod - tmp) % mod;
}
{
	Poly f(n), g(m);
	for (int i = 1; i < n; i++) f[i] = 1ll * ifac[i - 1] * ifac[i - 1] % mod;
	for (int i = 1; i < m; i++) g[i] = 1ll * ifac[i - 1] * ifac[i - 1] % mod;
	auto h = f * g;
	int tmp = 0;
	for (int i = 2; i < n + m - 1; i++) tmp = (tmp + 1ll * h[i] * fac[i - 2] % mod * fac[i - 2] % mod) % mod;
	ans = (ans + tmp) % mod;
	 
	f.assign(n, 0);
	g.assign(m, 0);
	for (int i = 2; i < n; i++) f[i] = 1ll * ifac[i - 2] * ifac[i] % mod;
	for (int i = 2; i < m; i++) g[i] = 1ll * ifac[i - 2] * ifac[i] % mod;
	h = f * g;
	tmp = 0;
	for (int i = 2; i < n + m - 1; i++) tmp = (tmp + 1ll * h[i] * fac[i - 2] % mod * fac[i - 2] % mod) % mod;
	ans = (ans + mod - tmp) % mod;
}
	cout << ans << '\n';
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 10352kb

input:

2 2

output:

11

result:

ok "11"

Test #2:

score: 0
Accepted
time: 8ms
memory: 10420kb

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

score: 0
Accepted
time: 141ms
memory: 19192kb

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

score: 0
Accepted
time: 8ms
memory: 10412kb

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

score: 0
Accepted
time: 8ms
memory: 10340kb

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

score: 0
Accepted
time: 8ms
memory: 10336kb

input:

3 3

output:

64

result:

ok "64"

Test #7:

score: 0
Accepted
time: 8ms
memory: 10368kb

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

score: 0
Accepted
time: 4ms
memory: 10212kb

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

score: 0
Accepted
time: 8ms
memory: 10228kb

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

score: 0
Accepted
time: 5ms
memory: 10480kb

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

score: 0
Accepted
time: 4ms
memory: 10112kb

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

score: 0
Accepted
time: 8ms
memory: 10152kb

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

score: 0
Accepted
time: 8ms
memory: 10296kb

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

score: 0
Accepted
time: 8ms
memory: 10760kb

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

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

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

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

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

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

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

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

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

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

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

score: 0
Accepted
time: 9ms
memory: 10768kb

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

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

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

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

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

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

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

score: 0
Accepted
time: 146ms
memory: 18604kb

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 64ms
memory: 14448kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 70ms
memory: 14024kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

score: 0
Accepted
time: 43ms
memory: 12416kb

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

score: 0
Accepted
time: 138ms
memory: 18676kb

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

score: 0
Accepted
time: 78ms
memory: 15052kb

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

score: 0
Accepted
time: 75ms
memory: 14508kb

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

score: 0
Accepted
time: 63ms
memory: 14068kb

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

score: 0
Accepted
time: 71ms
memory: 14112kb

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 73ms
memory: 14812kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

score: 0
Accepted
time: 149ms
memory: 19156kb

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

score: 0
Accepted
time: 137ms
memory: 19172kb

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

score: 0
Accepted
time: 137ms
memory: 19164kb

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

score: 0
Accepted
time: 8ms
memory: 10204kb

input:

1 1

output:

3

result:

ok "3"

Test #38:

score: 0
Accepted
time: 9ms
memory: 11948kb

input:

1 100000

output:

8828237

result:

ok "8828237"

Test #39:

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

input:

100000 2

output:

263711286

result:

ok "263711286"

Test #40:

score: 0
Accepted
time: 5ms
memory: 10440kb

input:

50 50

output:

634767411

result:

ok "634767411"

Extra Test:

score: 0
Extra Test Passed