QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#369232 | #6323. Range NEQ | Vengeful_Spirit# | RE | 39ms | 26796kb | C++17 | 3.7kb | 2024-03-27 22:19:59 | 2024-03-27 22:20:01 |
Judging History
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<<20|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: 26428kb
input:
2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 26128kb
input:
5 1
output:
44
result:
ok 1 number(s): "44"
Test #3:
score: 0
Accepted
time: 39ms
memory: 26796kb
input:
167 91
output:
284830080
result:
ok 1 number(s): "284830080"
Test #4:
score: 0
Accepted
time: 0ms
memory: 26200kb
input:
2 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 2ms
memory: 26148kb
input:
2 3
output:
36
result:
ok 1 number(s): "36"
Test #6:
score: 0
Accepted
time: 0ms
memory: 26368kb
input:
2 4
output:
576
result:
ok 1 number(s): "576"
Test #7:
score: 0
Accepted
time: 0ms
memory: 26088kb
input:
3 1
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: 0
Accepted
time: 0ms
memory: 26424kb
input:
3 2
output:
80
result:
ok 1 number(s): "80"
Test #9:
score: 0
Accepted
time: 0ms
memory: 26188kb
input:
3 3
output:
12096
result:
ok 1 number(s): "12096"
Test #10:
score: 0
Accepted
time: 0ms
memory: 26128kb
input:
3 4
output:
4783104
result:
ok 1 number(s): "4783104"
Test #11:
score: 0
Accepted
time: 2ms
memory: 26128kb
input:
4 1
output:
9
result:
ok 1 number(s): "9"
Test #12:
score: 0
Accepted
time: 0ms
memory: 26172kb
input:
4 2
output:
4752
result:
ok 1 number(s): "4752"
Test #13:
score: 0
Accepted
time: 0ms
memory: 26092kb
input:
4 3
output:
17927568
result:
ok 1 number(s): "17927568"
Test #14:
score: 0
Accepted
time: 0ms
memory: 26436kb
input:
4 4
output:
776703752
result:
ok 1 number(s): "776703752"
Test #15:
score: 0
Accepted
time: 0ms
memory: 26088kb
input:
5 2
output:
440192
result:
ok 1 number(s): "440192"
Test #16:
score: 0
Accepted
time: 0ms
memory: 26092kb
input:
5 3
output:
189125068
result:
ok 1 number(s): "189125068"
Test #17:
score: 0
Accepted
time: 0ms
memory: 26088kb
input:
5 4
output:
975434093
result:
ok 1 number(s): "975434093"
Test #18:
score: -100
Runtime Error
input:
1000 1000