QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#393009#6323. Range NEQGiga_Cronos#AC ✓373ms67796kbC++232.6kb2024-04-18 02:54:482024-04-18 02:54:48

Judging History

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

  • [2024-04-18 02:54:48]
  • 评测
  • 测评结果:AC
  • 用时:373ms
  • 内存:67796kb
  • [2024-04-18 02:54:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int    long long
#define fs     first
#define sc     second
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const ll mod = 998244353;
const ll MAXN = 1'000'003;

int qpow(int a, int e, int mo) {
	int ans = 1;
	for (; e; a = a * a % mo) {
		if (e & 1) {
			ans = ans * a % mo;
		}
		e /= 2;
	}
	return ans;
}

namespace ntt{
const int root=5;
int base=1;
vector<int> roots;

void ensure_base(int nbase){
	if(nbase<=base)return;
	roots.resize(nbase);
	for(int mh=base;mh<<1 <= nbase;mh<<=1){
		int wm=qpow(root,(mod-1)/(mh<<1),mod);
		roots[mh]=1;
		for(int i=1;i<mh;i++)
			roots[i+mh]=(ll)roots[i+mh-1]*wm%mod;
	}
	base=nbase;
}

void fft(int a[],int n,int sign){
	ensure_base(n);
	for(int i=1,j=0; i<n-1;i++){
		for(int k=n>>1;(j^=k)<k;k>>=1);
		if(i<j)swap(a[i],a[j]);
	}
	for(int m,mh=1;(m=mh<<1)<=n;mh=m)
		for(int i=0;i<n;i+=m)
			for(int j=i;j<i+mh;j++){
				int y=(ll)a[j+mh]*roots[j-i+mh]%mod;
				if((a[j+mh]=a[j]-y)<0)a[j+mh]+=mod;
				if((a[j]+=y)>=mod)a[j]-=mod;
			}
		if(sign<0){
			int inv=qpow(n,mod-2,mod);
			for(int i=0;i<n;i++)a[i]=a[i]*inv%mod;
			reverse(a+1,a+n);
		}
}


vector<int> convolve(vector<int> x, vector<int> y) {
	int n = x.size() + y.size() - 1, sz = 1;
	while(sz<n)sz<<=1;
	x.resize(sz);
	y.resize(sz);
	fft(x.data(),sz,+1);
	fft(y.data(),sz,+1);
	for(int i=0;i<sz;i++)
		x[i]=ll(x[i])*y[i]%mod;
	fft(x.data(),sz,-1);
	x.resize(n);
	return x;
}
}




vi Pow(vi A, int e) {
	vi ans = {1};
	for (; e; A = ntt::convolve(A, A)) {
		if (e & 1) {
			ans = ntt::convolve(ans, A);
		}
		e /= 2;
	}
	return ans;
}

int Fac[MAXN];
int IFac[MAXN];

int C(int a, int b) {
	if (b > a || b < 0)
		return 0;
	return Fac[a] * IFac[a - b] % mod * IFac[b] % mod;
}

int n, m;

void problem() {
	cin >> n >> m;
	vi A(m + 1);
	for (int i = 0; i <= m; i++) {
		A[i] = C(m, i) * IFac[m - i] % mod;
    }
	vi F = Pow(A, n);
	int ans = 0;
	for (int i = 0; i <= n * m; i++) {
		F[i] = F[i] * Fac[n * m - i] % mod;
		ans = (ans + (1 - 2 * (i & 1)) * F[i] + mod) % mod;
	}

	cout << ans * qpow(Fac[m], n, mod) % mod << "\n";
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Fac[0] = 1;
	for (int i = 1; i < MAXN; i++)
		Fac[i] = Fac[i - 1] * i % mod;
	IFac[MAXN - 1] = qpow(Fac[MAXN - 1], mod - 2, mod);
	for (int i = MAXN - 1; i > 0; i--)
		IFac[i - 1] = IFac[i] * i % mod;
	problem();

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 11ms
memory: 19500kb

input:

2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 6ms
memory: 19160kb

input:

5 1

output:

44

result:

ok 1 number(s): "44"

Test #3:

score: 0
Accepted
time: 15ms
memory: 20084kb

input:

167 91

output:

284830080

result:

ok 1 number(s): "284830080"

Test #4:

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

input:

2 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

2 3

output:

36

result:

ok 1 number(s): "36"

Test #6:

score: 0
Accepted
time: 10ms
memory: 19272kb

input:

2 4

output:

576

result:

ok 1 number(s): "576"

Test #7:

score: 0
Accepted
time: 10ms
memory: 19244kb

input:

3 1

output:

2

result:

ok 1 number(s): "2"

Test #8:

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

input:

3 2

output:

80

result:

ok 1 number(s): "80"

Test #9:

score: 0
Accepted
time: 10ms
memory: 19272kb

input:

3 3

output:

12096

result:

ok 1 number(s): "12096"

Test #10:

score: 0
Accepted
time: 6ms
memory: 19212kb

input:

3 4

output:

4783104

result:

ok 1 number(s): "4783104"

Test #11:

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

input:

4 1

output:

9

result:

ok 1 number(s): "9"

Test #12:

score: 0
Accepted
time: 10ms
memory: 19204kb

input:

4 2

output:

4752

result:

ok 1 number(s): "4752"

Test #13:

score: 0
Accepted
time: 10ms
memory: 19264kb

input:

4 3

output:

17927568

result:

ok 1 number(s): "17927568"

Test #14:

score: 0
Accepted
time: 10ms
memory: 19296kb

input:

4 4

output:

776703752

result:

ok 1 number(s): "776703752"

Test #15:

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

input:

5 2

output:

440192

result:

ok 1 number(s): "440192"

Test #16:

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

input:

5 3

output:

189125068

result:

ok 1 number(s): "189125068"

Test #17:

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

input:

5 4

output:

975434093

result:

ok 1 number(s): "975434093"

Test #18:

score: 0
Accepted
time: 363ms
memory: 67796kb

input:

1000 1000

output:

720037464

result:

ok 1 number(s): "720037464"

Test #19:

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

input:

72 42

output:

638177567

result:

ok 1 number(s): "638177567"

Test #20:

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

input:

15 19

output:

663050288

result:

ok 1 number(s): "663050288"

Test #21:

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

input:

68 89

output:

94365047

result:

ok 1 number(s): "94365047"

Test #22:

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

input:

92 37

output:

652605307

result:

ok 1 number(s): "652605307"

Test #23:

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

input:

61 87

output:

498277867

result:

ok 1 number(s): "498277867"

Test #24:

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

input:

81 40

output:

133095344

result:

ok 1 number(s): "133095344"

Test #25:

score: 0
Accepted
time: 10ms
memory: 19268kb

input:

7 91

output:

524164813

result:

ok 1 number(s): "524164813"

Test #26:

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

input:

31 18

output:

361233485

result:

ok 1 number(s): "361233485"

Test #27:

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

input:

74 54

output:

500686087

result:

ok 1 number(s): "500686087"

Test #28:

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

input:

32 2

output:

586504335

result:

ok 1 number(s): "586504335"

Test #29:

score: 0
Accepted
time: 232ms
memory: 63416kb

input:

656 718

output:

346764298

result:

ok 1 number(s): "346764298"

Test #30:

score: 0
Accepted
time: 76ms
memory: 30608kb

input:

254 689

output:

358078813

result:

ok 1 number(s): "358078813"

Test #31:

score: 0
Accepted
time: 240ms
memory: 62204kb

input:

713 674

output:

914437613

result:

ok 1 number(s): "914437613"

Test #32:

score: 0
Accepted
time: 47ms
memory: 29356kb

input:

136 698

output:

56687290

result:

ok 1 number(s): "56687290"

Test #33:

score: 0
Accepted
time: 67ms
memory: 29652kb

input:

369 401

output:

312325811

result:

ok 1 number(s): "312325811"

Test #34:

score: 0
Accepted
time: 34ms
memory: 24476kb

input:

280 204

output:

280012063

result:

ok 1 number(s): "280012063"

Test #35:

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

input:

904 225

output:

162909174

result:

ok 1 number(s): "162909174"

Test #36:

score: 0
Accepted
time: 347ms
memory: 63460kb

input:

855 928

output:

39885159

result:

ok 1 number(s): "39885159"

Test #37:

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

input:

503 365

output:

745115888

result:

ok 1 number(s): "745115888"

Test #38:

score: 0
Accepted
time: 318ms
memory: 63956kb

input:

646 996

output:

610925577

result:

ok 1 number(s): "610925577"

Test #39:

score: 0
Accepted
time: 373ms
memory: 66696kb

input:

990 918

output:

203469632

result:

ok 1 number(s): "203469632"

Test #40:

score: 0
Accepted
time: 365ms
memory: 65632kb

input:

961 949

output:

169566857

result:

ok 1 number(s): "169566857"

Test #41:

score: 0
Accepted
time: 351ms
memory: 65564kb

input:

946 932

output:

352423195

result:

ok 1 number(s): "352423195"

Test #42:

score: 0
Accepted
time: 358ms
memory: 65728kb

input:

903 981

output:

196309824

result:

ok 1 number(s): "196309824"

Test #43:

score: 0
Accepted
time: 359ms
memory: 65832kb

input:

916 988

output:

487208972

result:

ok 1 number(s): "487208972"

Test #44:

score: 0
Accepted
time: 367ms
memory: 66856kb

input:

982 982

output:

387421488

result:

ok 1 number(s): "387421488"

Test #45:

score: 0
Accepted
time: 371ms
memory: 65688kb

input:

955 911

output:

955637031

result:

ok 1 number(s): "955637031"

Test #46:

score: 0
Accepted
time: 362ms
memory: 65780kb

input:

906 999

output:

798469943

result:

ok 1 number(s): "798469943"

Test #47:

score: 0
Accepted
time: 358ms
memory: 66700kb

input:

982 975

output:

193506289

result:

ok 1 number(s): "193506289"

Test #48:

score: 0
Accepted
time: 371ms
memory: 65712kb

input:

921 991

output:

431202149

result:

ok 1 number(s): "431202149"