QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#534735 | #6323. Range NEQ | ucup-team1525# | AC ✓ | 1694ms | 147124kb | C++17 | 4.4kb | 2024-08-27 15:42:51 | 2024-08-27 15:42:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
const int mod=998244353;
const int N=1<<22;
using arr=int[N+5];
int add(int x,int y){ return (x+=y)>=mod?x-mod:x; }
int sub(int x,int y){ return (x-=y)<0?x+mod:x; }
int red(int &x){ return x+=(x>>31)&mod; }
int ksm(ll x,int tp,int s=1){
for(;tp;x=x*x%mod,tp>>=1) if(tp&1) s=x*s%mod;
return s;
}
arr fac,ifac,inv;
void prep(){
fac[0]=ifac[0]=1;
for(int i=1;i<=N;i++) fac[i]=1ll*fac[i-1]*i%mod;
ifac[N]=ksm(fac[N],mod-2);
for(int i=N;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod;
for(int i=1;i<=N;i++) inv[i]=1ll*ifac[i]*fac[i-1]%mod;
}
int C(int n,int m){
return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
namespace poly{
int L,iv;
arr w,rev;
arr pa,pb;
#define szf sizeof(int)
void cl(arr a){ memset(a,0,L*szf); }
void r_prep(){
int L=N>>1;
int val=ksm(3,(mod-1)/N);
w[L]=1;
for(int i=1;i<L;i++) w[i+L]=1ll*w[i+L-1]*val%mod;
for(int i=L-1;i;i--) w[i]=w[i<<1];
}
void pre_n(int n){
L=1; while(L<n) L<<=1;
iv=mod-(mod-1)/L;
for(int i=1;i<L;i++) rev[i]=(rev[i>>1]>>1)|(i&1?L>>1:0);
}
void FFT(arr t,bool ok=1){
int x,y;
for(int i=1;i<L;i++)
if(i<rev[i]) swap(t[i],t[rev[i]]);
for(int i=1;i<L;i<<=1)
for(int j=0;j<L;j+=i<<1)
for(int l=0;l<i;l++){
x=t[j+l],y=1ll*t[i+j+l]*w[i+l]%mod;
t[i+j+l]=sub(x,y),t[j+l]=add(x,y);
}
if(!ok){
reverse(t+1,t+L);
for(int i=0;i<L;i++) t[i]=1ll*t[i]*iv%mod;
}
}
void NTT(arr a){ FFT(a); }
void INTT(arr a){ FFT(a,0); }
void NTT(arr a,arr b){ memcpy(b,a,L*szf); FFT(b); }
void INTT(arr a,arr b){ memcpy(b,a,L*szf); FFT(b,0); }
void Mult(arr a,arr b,arr c,int n){
pre_n(n);
NTT(a,pa); NTT(b,pb);
for(int i=0;i<L;i++)
c[i]=1ll*pa[i]*pb[i]%mod;
INTT(c);
fill(c+n,c+L,0);
cl(pa); cl(pb);
}
void Inv(arr a,arr b,int n){
int i,j,l;
pre_n(n); l=L;
cl(b); *b=ksm(*a,mod-2);
for(i=2;i<=l;i<<=1){
pre_n(i);
NTT(a,pa); NTT(b,pb);
for(j=0;j<i;j++) pa[j]=1ll*pa[j]*pb[j]%mod;
INTT(pa); fill(pa,pa+(i>>1),0); NTT(pa);
for(j=0;j<i;j++) pa[j]=1ll*(mod-pa[j])*pb[j]%mod;
INTT(pa); j=i>>1;
memcpy(b+j,pa+j,j*szf);
}
fill(b+n,b+l,0);
cl(pa); cl(pb);
}
void Inv2(arr a,arr b,arr c,int n){
static arr d;
Inv(a,d,n);
Mult(b,d,c,n*2);
fill(c+n,c+2*n,0);
cl(d);
}
void diff(arr t,int n){
for(int i=1;i<n;i++)
t[i-1]=1ll*i*t[i]%mod;
t[n-1]=0;
}
void inte(arr t,int n){
for(int i=n-1;i;i--)
t[i]=1ll*t[i-1]*inv[i]%mod;
t[0]=0;
}
void Ln(arr a,arr b,int n){
pre_n(n); cl(b);
memcpy(b,a,n*szf);
diff(b,n);
Inv2(a,b,b,n);
inte(b,n);
}
void Exp(arr a,arr b,int n){
static arr e;
int i,j,l;
pre_n(n);l=L;
cl(b); *b=1;
for(i=2;i<=l;i<<=1){
Ln(b,e,i);
for(j=0;j<i;j++) e[j]=sub(a[j],e[j]);
Mult(e,b,e,i); j=i>>1;
memcpy(b+j,e+j,j*szf);
}
fill(b+n,b+l,0);
cl(e);
}
}
namespace Get_val{
using namespace poly;
arr G[20],F[20];
void pre_g(int k,int l,int p,arr vx){
int *g=G[k]+p;
if(!k){
g[0]=1; g[1]=sub(0,vx[l]);
return;
}
int L=1<<k;
pre_g(k-1,l,p,vx); pre_g(k-1,l+L/2,p+L,vx);
Mult(G[k-1]+p,G[k-1]+p+L,g,L);
g[L]=sub(g[0],1); g[0]=1;
}
void solve(int k,int l,int p,arr ans){
int *f=F[k]+p;
if(!k){
ans[l]=f[0];
return;
}
int L=1<<k;
int *fl=F[k-1]+p,*fr=F[k-1]+p+L;
int *gl=G[k-1]+p,*gr=G[k-1]+p+L;
static arr vf;
pre_n(L);
NTT(f,vf);
reverse(gl+1,gl+L); NTT(gl);
reverse(gr+1,gr+L); NTT(gr);
for(int i=0;i<L;i++){
fl[i]=1ll*vf[i]*gr[i]%mod;
fr[i]=1ll*vf[i]*gl[i]%mod;
}
INTT(fl); fill(fl+L/2,fl+L,0);
INTT(fr); fill(fr+L/2,fr+L,0);
solve(k-1,l,p,ans);
solve(k-1,l+L/2,p+L,ans);
}
void work(int n,int m,arr f,arr vx,arr vy){
int up=(int)log2(max(n,m)-1)+1;
pre_g(up,1,0,vx);
int *st=F[up];
static arr ig;
int L=1<<up+1;
Inv(G[up],ig,L/2);
reverse(ig+1,ig+L);
Mult(f,ig,st,L);
fill(st+L/2,st+L,0);
solve(up,1,0,vy);
}
}
int n,m;
arr f,g;
int main(){
prep();
poly::r_prep();
scanf("%d %d",&n,&m);
for(int i=0;i<=m;i++){
f[i]=1ll*C(m,i)*fac[m]%mod*ifac[m-i]%mod;
if(i&1) f[i]=mod-f[i];
}
poly::Ln(f,g,n*m+1);
for(int i=0;i<=n*m;i++) g[i]=1ll*g[i]*n%mod;
memset(f,0,sizeof f);
poly::Exp(g,f,n*m+1);
int ans=0;
for(int i=0;i<=n*m;i++)
ans=(ans+1ll*fac[n*m-i]*f[i])%mod;
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 50ms
memory: 98084kb
input:
2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 47ms
memory: 98092kb
input:
5 1
output:
44
result:
ok 1 number(s): "44"
Test #3:
score: 0
Accepted
time: 61ms
memory: 98412kb
input:
167 91
output:
284830080
result:
ok 1 number(s): "284830080"
Test #4:
score: 0
Accepted
time: 51ms
memory: 98096kb
input:
2 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 46ms
memory: 98004kb
input:
2 3
output:
36
result:
ok 1 number(s): "36"
Test #6:
score: 0
Accepted
time: 53ms
memory: 98080kb
input:
2 4
output:
576
result:
ok 1 number(s): "576"
Test #7:
score: 0
Accepted
time: 43ms
memory: 97964kb
input:
3 1
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: 0
Accepted
time: 45ms
memory: 97972kb
input:
3 2
output:
80
result:
ok 1 number(s): "80"
Test #9:
score: 0
Accepted
time: 50ms
memory: 98096kb
input:
3 3
output:
12096
result:
ok 1 number(s): "12096"
Test #10:
score: 0
Accepted
time: 53ms
memory: 98152kb
input:
3 4
output:
4783104
result:
ok 1 number(s): "4783104"
Test #11:
score: 0
Accepted
time: 53ms
memory: 98012kb
input:
4 1
output:
9
result:
ok 1 number(s): "9"
Test #12:
score: 0
Accepted
time: 54ms
memory: 97976kb
input:
4 2
output:
4752
result:
ok 1 number(s): "4752"
Test #13:
score: 0
Accepted
time: 47ms
memory: 97968kb
input:
4 3
output:
17927568
result:
ok 1 number(s): "17927568"
Test #14:
score: 0
Accepted
time: 49ms
memory: 98152kb
input:
4 4
output:
776703752
result:
ok 1 number(s): "776703752"
Test #15:
score: 0
Accepted
time: 53ms
memory: 98152kb
input:
5 2
output:
440192
result:
ok 1 number(s): "440192"
Test #16:
score: 0
Accepted
time: 42ms
memory: 98152kb
input:
5 3
output:
189125068
result:
ok 1 number(s): "189125068"
Test #17:
score: 0
Accepted
time: 53ms
memory: 98156kb
input:
5 4
output:
975434093
result:
ok 1 number(s): "975434093"
Test #18:
score: 0
Accepted
time: 1694ms
memory: 146384kb
input:
1000 1000
output:
720037464
result:
ok 1 number(s): "720037464"
Test #19:
score: 0
Accepted
time: 46ms
memory: 98072kb
input:
72 42
output:
638177567
result:
ok 1 number(s): "638177567"
Test #20:
score: 0
Accepted
time: 42ms
memory: 98080kb
input:
15 19
output:
663050288
result:
ok 1 number(s): "663050288"
Test #21:
score: 0
Accepted
time: 52ms
memory: 98140kb
input:
68 89
output:
94365047
result:
ok 1 number(s): "94365047"
Test #22:
score: 0
Accepted
time: 57ms
memory: 98076kb
input:
92 37
output:
652605307
result:
ok 1 number(s): "652605307"
Test #23:
score: 0
Accepted
time: 48ms
memory: 98140kb
input:
61 87
output:
498277867
result:
ok 1 number(s): "498277867"
Test #24:
score: 0
Accepted
time: 49ms
memory: 98128kb
input:
81 40
output:
133095344
result:
ok 1 number(s): "133095344"
Test #25:
score: 0
Accepted
time: 59ms
memory: 98172kb
input:
7 91
output:
524164813
result:
ok 1 number(s): "524164813"
Test #26:
score: 0
Accepted
time: 39ms
memory: 98024kb
input:
31 18
output:
361233485
result:
ok 1 number(s): "361233485"
Test #27:
score: 0
Accepted
time: 45ms
memory: 98148kb
input:
74 54
output:
500686087
result:
ok 1 number(s): "500686087"
Test #28:
score: 0
Accepted
time: 47ms
memory: 97960kb
input:
32 2
output:
586504335
result:
ok 1 number(s): "586504335"
Test #29:
score: 0
Accepted
time: 780ms
memory: 122128kb
input:
656 718
output:
346764298
result:
ok 1 number(s): "346764298"
Test #30:
score: 0
Accepted
time: 365ms
memory: 110984kb
input:
254 689
output:
358078813
result:
ok 1 number(s): "358078813"
Test #31:
score: 0
Accepted
time: 795ms
memory: 122064kb
input:
713 674
output:
914437613
result:
ok 1 number(s): "914437613"
Test #32:
score: 0
Accepted
time: 197ms
memory: 100060kb
input:
136 698
output:
56687290
result:
ok 1 number(s): "56687290"
Test #33:
score: 0
Accepted
time: 364ms
memory: 108476kb
input:
369 401
output:
312325811
result:
ok 1 number(s): "312325811"
Test #34:
score: 0
Accepted
time: 117ms
memory: 105456kb
input:
280 204
output:
280012063
result:
ok 1 number(s): "280012063"
Test #35:
score: 0
Accepted
time: 367ms
memory: 109244kb
input:
904 225
output:
162909174
result:
ok 1 number(s): "162909174"
Test #36:
score: 0
Accepted
time: 1689ms
memory: 145764kb
input:
855 928
output:
39885159
result:
ok 1 number(s): "39885159"
Test #37:
score: 0
Accepted
time: 369ms
memory: 110724kb
input:
503 365
output:
745115888
result:
ok 1 number(s): "745115888"
Test #38:
score: 0
Accepted
time: 1663ms
memory: 146736kb
input:
646 996
output:
610925577
result:
ok 1 number(s): "610925577"
Test #39:
score: 0
Accepted
time: 1682ms
memory: 147024kb
input:
990 918
output:
203469632
result:
ok 1 number(s): "203469632"
Test #40:
score: 0
Accepted
time: 1680ms
memory: 146644kb
input:
961 949
output:
169566857
result:
ok 1 number(s): "169566857"
Test #41:
score: 0
Accepted
time: 1686ms
memory: 147028kb
input:
946 932
output:
352423195
result:
ok 1 number(s): "352423195"
Test #42:
score: 0
Accepted
time: 1676ms
memory: 146364kb
input:
903 981
output:
196309824
result:
ok 1 number(s): "196309824"
Test #43:
score: 0
Accepted
time: 1683ms
memory: 146856kb
input:
916 988
output:
487208972
result:
ok 1 number(s): "487208972"
Test #44:
score: 0
Accepted
time: 1679ms
memory: 146812kb
input:
982 982
output:
387421488
result:
ok 1 number(s): "387421488"
Test #45:
score: 0
Accepted
time: 1679ms
memory: 146056kb
input:
955 911
output:
955637031
result:
ok 1 number(s): "955637031"
Test #46:
score: 0
Accepted
time: 1678ms
memory: 146484kb
input:
906 999
output:
798469943
result:
ok 1 number(s): "798469943"
Test #47:
score: 0
Accepted
time: 1683ms
memory: 147124kb
input:
982 975
output:
193506289
result:
ok 1 number(s): "193506289"
Test #48:
score: 0
Accepted
time: 1685ms
memory: 146848kb
input:
921 991
output:
431202149
result:
ok 1 number(s): "431202149"