QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369237#6323. Range NEQVengeful_Spirit#TL 39ms26548kbC++173.7kb2024-03-27 22:20:522024-03-27 22:21:01

Judging History

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

  • [2024-03-27 22:21:01]
  • 评测
  • 测评结果:TL
  • 用时:39ms
  • 内存:26548kb
  • [2024-03-27 22:20:52]
  • 提交

answer

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
#define ll long long
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define reg 
const int N=1<<21|5,P=998244353,g=3,invg=332748118;
int Mul(int x, int y) { return 1ll * x * y % P; }
int Add(int x, int y) { return (x+y)%P; }
#define ri int i
int _[N],pos[N];
int fpow(int x,int m){int r=1;for(;m;m>>=1,x=Mul(x,x))if(m&1)r=Mul(r,x);return r;}
void der(int *a,int *b,int n){for(ri=0;i<n-1;++i) b[i]=Mul(i+1,a[i+1]);b[n-1]=0;}
void inte(int *a,int *b,int n)
{
	ri;for(_[1]=i=1;i<n;++i,_[i]=Mul(_[P%i],P-P/i));
	for(i=n-1;i;--i)b[i]=Mul(a[i-1],_[i]);b[0]=0;
}
void init(int len)
{
	reg int i;
	for(i=0;i<len;++i) pos[i]=(pos[i>>1]>>1)|((i&1)*(len>>1));
}
void NTT(int *a,int n,int type)
{
	int i,j,k,w,wn,X,Y;
	for(i=0;i<n;++i) if(i<pos[i]) swap(a[i],a[pos[i]]);
	for(i=1;i<n;i<<=1)
	{
		wn=fpow(type>0?g:invg,(P-1)/(i<<1));
		for(j=0;j<n;j+=i<<1)for(w=1,k=0;k<i;++k,w=Mul(w,wn))
		{
			X=a[j+k],Y=Mul(w,a[j+k+i]);
			a[j+k]=(X+Y)%P;a[j+k+i]=(X-Y+P)%P;
		}
	}
	reg int invn=fpow(n,P-2);
	if(type==-1)for(i=0;i<n;++i)a[i]=Mul(a[i],invn);
}
void Comb(int *a,int *b,int *c,int n)
{
	static int A[N],B[N],len;
	for(len=1;len<(n<<1);len<<=1);
	memcpy(A,a,sizeof(int[n]));memcpy(B,b,sizeof(int[n]));
	memset(A+n,0,sizeof(int[len-n]));memset(B+n,0,sizeof(int[len-n]));
	reg int i;init(len);NTT(A,len,1);NTT(B,len,1);
	for(i=0;i<len;++i) c[i]=Mul(A[i],B[i]);NTT(c,len,-1);
	memset(c+n,0,sizeof(int[len-n]));
}
void _I(int *A,int *b,int n)
{
	if(n==1) return(void)(b[0]=fpow(A[0],P-2));
	int t=(n+1)>>1;_I(A,b,t);
	static int a[N],len;
	for(len=1;len<(n<<1);len<<=1);
	memcpy(a,A,sizeof(int[n]));memset(a+n,0,sizeof(int[len-n]));
	memset(b+t,0,sizeof(int[len-t]));init(len);
	reg int i;NTT(a,len,1);NTT(b,len,1);
	for(i=0;i<len;++i)b[i]=(Mul(2ll,b[i])-Mul(a[i],Mul(b[i],b[i]))+P)%P;
	NTT(b,len,-1);memset(b+n,0,sizeof(int[len-n]));
}
void Inv(int *A,int *b,int n)
{
	static int a[N];
	memcpy(a,A,sizeof(int[n]));
	_I(a,b,n);
}
void ln(int *A,int *B,int n)
{
	static int a[N],da[N];
	memcpy(a,A,sizeof(int[n]));memcpy(da,A,sizeof(int[n]));
	Inv(a,a,n);der(da,da,n);Comb(da,a,B,n);inte(B,B,n);
}
void _e(int *a,int *b,int n)
{
	if(n==1)return(void)(b[0]=1);
	int t=(n+1)>>1;_e(a,b,t);
	static int xxx[N];
	ln(b,xxx,n);reg int i;
	for(i=0;i<n;++i)xxx[i]=(-xxx[i]+a[i]+P)%P;
	xxx[0]=(xxx[0]+1)%P;
	Comb(b,xxx,b,n);
}
void exp(int *A,int *b,int n)
{
	static int a[N];
	memcpy(a,A,sizeof(int[n]));
	_e(a,b,n);
}
int a[N], b[N], c[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int i, N, M;
    cin >> N >> M;
    const int mod = 998244353;
    
    vector<int> fac((N*M)+1), inv((N*M)+1);
    for(inv[0]=fac[0]=fac[1]=inv[1]=1,i=2;i<=(N*M);++i)
        fac[i]=Mul(fac[i-1], i), inv[i]=Mul(inv[mod%i],mod-mod/i);
    for(i=2;i<=(N*M);++i) inv[i]=Mul(inv[i-1],inv[i]);
    for(i=0;i<=M;++i) a[i]=Mul(inv[i], Mul(inv[M-i], inv[M-i]));
    int __0 = a[0], __1 = fpow(__0, mod-2);
    for(i=0;i<=M;++i) a[i]=Mul(a[i], __1);
    // for(i=0;i<=N*M;++i) cerr << a[i] << "\n"; cerr << "\n";
    // a=qpow(a, N);
    ln(a, b, N*M+1);
    for(i=0;i<N*M+1;++i) b[i]=Mul(b[i], N);
    exp(b, c, N*M+1); 
    int ans=0, fMN=fpow(fac[M], N), ifMN = fpow(fMN, mod-2);
    for(i=0;i<N*M+1;++i) c[i]=Mul(c[i], ifMN);

    // for(i=0;i<=N*M;++i) cerr << c[i] << " "; cerr << "\n";

    for(int i=0;i<=N*M;++i)
    {
        int v=Mul(fac[N*M-i], Mul(c[i], fMN));
        if(i&1) ans=Add(ans, mod-v);
        else ans=Add(ans, v);
        // cerr << v << "\n";
        // cout << ans << "\n";
        // cout<<ans<<"\n";
    }
    cout << ans << "\n";

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

5 1

output:

44

result:

ok 1 number(s): "44"

Test #3:

score: 0
Accepted
time: 39ms
memory: 26548kb

input:

167 91

output:

284830080

result:

ok 1 number(s): "284830080"

Test #4:

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

input:

2 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

2 3

output:

36

result:

ok 1 number(s): "36"

Test #6:

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

input:

2 4

output:

576

result:

ok 1 number(s): "576"

Test #7:

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

input:

3 1

output:

2

result:

ok 1 number(s): "2"

Test #8:

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

input:

3 2

output:

80

result:

ok 1 number(s): "80"

Test #9:

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

input:

3 3

output:

12096

result:

ok 1 number(s): "12096"

Test #10:

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

input:

3 4

output:

4783104

result:

ok 1 number(s): "4783104"

Test #11:

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

input:

4 1

output:

9

result:

ok 1 number(s): "9"

Test #12:

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

input:

4 2

output:

4752

result:

ok 1 number(s): "4752"

Test #13:

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

input:

4 3

output:

17927568

result:

ok 1 number(s): "17927568"

Test #14:

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

input:

4 4

output:

776703752

result:

ok 1 number(s): "776703752"

Test #15:

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

input:

5 2

output:

440192

result:

ok 1 number(s): "440192"

Test #16:

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

input:

5 3

output:

189125068

result:

ok 1 number(s): "189125068"

Test #17:

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

input:

5 4

output:

975434093

result:

ok 1 number(s): "975434093"

Test #18:

score: -100
Time Limit Exceeded

input:

1000 1000

output:


result: