QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213436#6323. Range NEQkjhhjkiTL 36ms11760kbC++143.1kb2023-10-14 14:14:302023-10-14 14:14:31

Judging History

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

  • [2023-10-14 14:14:31]
  • 评测
  • 测评结果:TL
  • 用时:36ms
  • 内存:11760kb
  • [2023-10-14 14:14:30]
  • 提交

answer

#include<bits/stdc++.h>
#define MAXN 2100006
using namespace std;
typedef unsigned long long _ll;
typedef unsigned int ui;

const ui P = 998244353, G = 3, Gi = 332748118;

inline char nr()
{
	static char buf[1<<22],*p1,*p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++;
}
ui read()
{
	ui x=0; char ch = nr();
	while(!isdigit(ch)) ch=nr(); 
	while(isdigit(ch)) { x=(_ll(x)<<3)+(x<<1)+(ch^48); ch=nr(); }
	return x;
}
string strread()
{
	string s; char ch = nr();
	while(!isdigit(ch)) ch=nr(); 
	while(isdigit(ch)) s.push_back(ch), ch=nr();
	return s;
}
ui limit, inv, w[MAXN];
ui qpow(ui x, ui n)
{
    ui res = 1;
    while(n)
    {
        if(n&1)  res=1ll*res*x%P;
        n >>= 1; x=1ll*x*x%P;
    }
    return res;
}
void init(ui n)
{
    limit = 2;
    while(limit <= n) limit <<= 1;
    for(ui i = 1; i < limit; i <<= 1)
    {
        ui wn = qpow(G, (P-1)/(i<<1));
        w[i] = 1;
        for(ui j = i+1; j < (i<<1); ++j)
            w[j] = 1ll*w[j-1]*wn%P;
    }
    inv = qpow(limit, P-2);	
}
void NTT(ui a[])
{   
    for(ui mid = limit>>1; mid >= 1; mid >>= 1)
    {
        for(ui j = 0; j < limit; j += mid<<1)
        {
            for(ui k = j, s = mid; k < j+mid; ++k, ++s)
            {
                ui x = a[k], y = a[k+mid];
                a[k] = x+y>P?x+y-P:x+y;
                a[k+mid] = 1ll*(x<y?P+x-y:x-y)*w[s]%P;
            }
        }
    }
}
void INTT(ui a[])
{
    for(ui mid = 1; mid < limit; mid <<= 1)
    {
        for(ui j = 0; j < limit; j += mid<<1)
        {
            for(ui k = j, s = mid; k < j+mid; ++k, ++s)
            {
                ui x = a[k], y = (1ll * w[s] * a[k+mid])%P;
                a[k] = x+y>P?x+y-P:x+y;
                a[k+mid] = x<y?P+x-y:x-y;
            }
        }
    }
    reverse(a+1, a+limit);
    for(ui i = 0; i < limit; ++i)
        a[i] = 1ll*a[i]*inv%P;
}
void poly_qpow(ui n, ui k, ui a[], ui res[])
{
	init(n<<1); res[0] = 1;
	if(k == P)
	{
		res[0] = a[0];
		return; 
	}
	while(k)
	{
		NTT(a); 
		if(k&1)
		{
			NTT(res);
			for(ui i = 0; i < limit; ++i)
				res[i] = 1ll*res[i]*a[i]%P;
			INTT(res);
			fill(res+n, res+limit, 0);
		}
		for(ui i = 0; i < limit; ++i)
			a[i] = 1ll*a[i]*a[i]%P;
		INTT(a);
		fill(a+n, a+limit, 0);
		k >>= 1;
	}
}

ui n, m, k, inv2, a0, ans, a[MAXN], b[MAXN];
ui fac[MAXN], fac_inv[MAXN];
string s;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	n = read(); m = read(); fac[0] = 1;
	for(ui i = 1; i <= n*m; ++i) 
		fac[i] = 1ll*fac[i-1]*i%P;
	fac_inv[n*m] = qpow(fac[n*m], P-2);
	for(int i = n*m; i >= 1; --i) 
		fac_inv[i-1] = 1ll*fac_inv[i]*i%P;
	for(int i = 0; i <= m; ++i)
	{
		a[i] = 1ll*fac[m]*fac_inv[i]%P*fac_inv[m-i]%P*fac_inv[m-i]%P;
		if(i&1) a[i] = P-a[i];
	}
	if(a[0] != 0 && a[0] != 1)
	{
		inv2 = qpow(a[0], P-2); a0 = a[0];
		for(ui i = 0; i <= m; ++i) a[i] = 1ll*a[i]*inv2%P;
	}
	else inv2 = 1, a0 = 1;
	poly_qpow(n*m+1,n,a,b); a0 = qpow(a0,k);
	for(ui i = 0; i <= n*m; ++i) ans = (ans + 1ll*b[i]*a0%P*fac[n*m-i]%P)%P;
	cout << ans;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11672kb

input:

2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

5 1

output:

44

result:

ok 1 number(s): "44"

Test #3:

score: 0
Accepted
time: 36ms
memory: 11760kb

input:

167 91

output:

284830080

result:

ok 1 number(s): "284830080"

Test #4:

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

input:

2 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

2 3

output:

36

result:

ok 1 number(s): "36"

Test #6:

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

input:

2 4

output:

576

result:

ok 1 number(s): "576"

Test #7:

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

input:

3 1

output:

2

result:

ok 1 number(s): "2"

Test #8:

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

input:

3 2

output:

80

result:

ok 1 number(s): "80"

Test #9:

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

input:

3 3

output:

12096

result:

ok 1 number(s): "12096"

Test #10:

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

input:

3 4

output:

4783104

result:

ok 1 number(s): "4783104"

Test #11:

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

input:

4 1

output:

9

result:

ok 1 number(s): "9"

Test #12:

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

input:

4 2

output:

4752

result:

ok 1 number(s): "4752"

Test #13:

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

input:

4 3

output:

17927568

result:

ok 1 number(s): "17927568"

Test #14:

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

input:

4 4

output:

776703752

result:

ok 1 number(s): "776703752"

Test #15:

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

input:

5 2

output:

440192

result:

ok 1 number(s): "440192"

Test #16:

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

input:

5 3

output:

189125068

result:

ok 1 number(s): "189125068"

Test #17:

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

input:

5 4

output:

975434093

result:

ok 1 number(s): "975434093"

Test #18:

score: -100
Time Limit Exceeded

input:

1000 1000

output:


result: