QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#359475 | #7974. 染色 | zjy0001 | 100 ✓ | 54ms | 23092kb | C++17 | 4.1kb | 2024-03-20 18:15:29 | 2024-03-20 18:15:30 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
typedef vector<int> poly;
const int Mod=998244353,G=3,img=86583718,winv=932051910;// winv = 2^64 mod Mod
const int Lim=64,inv2=(Mod+1)/2,inv3=(Mod+1)/3,rinv=Mod-2;
const LL Mod2=(LL)Mod*Mod;
poly w0={1},W0;vector<poly>Tr;
inline int fadd(int x,const int&y){return (x+=y-2*Mod)>=0?x:x+2*Mod;}
inline int fsub(int x,const int&y){return (x-=y)>=0?x:x+2*Mod;}
inline int reduce(LL x){return (x+(LL)((uint)x*rinv)*Mod)>>32;}
inline int qpow(int x,int y,int z=1){
for(;y;(y>>=1)&&(x=(LL)x*x%Mod))if(y&1)z=(LL)z*x%Mod;return z;
}
inline int BSGS(int x){
unordered_map<int,int>mp;
int S=sqrtl(Mod)+1,j=1,q=1;
for(int i=0;i<S;++i,j=(LL)j*G%Mod)mp[(LL)j*x%Mod]=i;
for(int i=0;i<=S;++i,q=(LL)q*j%Mod)if(mp.count(q)&&i*S>=mp[q])return i*S-mp[q];
return -1;
}
inline poly Add(poly P,poly Q){
if(P.size()<Q.size())swap(P,Q);
for(int i=Q.size();i--;)(P[i]+=Q[i])>=Mod&&(P[i]-=Mod);
return P;
}
inline poly Sub(poly P,poly Q){
if(P.size()<Q.size())P.resize(Q.size());
for(int i=Q.size();i--;)(P[i]-=Q[i])<0&&(P[i]+=Mod);
return P;
}
template<int T>inline void dft(poly&P){
const int m=P.size(),n=m/T,n2=n/2;
int L=w0.size();
if(L*2<n)for(w0.resize(n2);L*2<n;L<<=1){
const int cr=qpow(G,Mod/(L<<2));
for(int i=0;i<L;++i)w0[i+L]=(LL)cr*w0[i]%Mod;
}
if(W0.size()<w0.size()){
const int pr=W0.size(),ed=w0.size();
W0.resize(ed);
for(int i=pr;i<ed;++i)W0[i]=reduce((LL)winv*w0[i]);
}
for(int k=n,st1,st2;st1=k*T,st2=st1>>1,k>1;k>>=1)
for(int i=0,ie=n/k;i<ie;++i)
for(int p=i*st1,pe=p+st2;p<pe;++p){
const int q=p+st2,z=reduce((LL)P[q]*W0[i]);
P[q]=fsub(P[p],z),P[p]=fadd(P[p],z);
}
for(int&i:P)i>=Mod&&(i-=Mod);
}
template<int T>inline void idft(poly&P){
const int m=P.size(),n=m/T,ni=qpow(n,Mod-2),n2=n/2;
poly rev(n);
for(int i=1;i<n;++i)rev[i]=(rev[i>>1]>>1)+(i&1)*n2;
for(int&i:P)i=(LL)i*ni%Mod;
for(int i=1;i<n;++i)if(i<rev[i])swap_ranges(P.begin()+T*i,P.begin()+T*(i+1),P.begin()+T*rev[i]);
for(int i=1;i<n2;++i)swap_ranges(P.begin()+T*i,P.begin()+T*(i+1),P.begin()+T*(n-i));
dft<T>(P);
for(int i=1;i<n;++i)if(i<rev[i])swap_ranges(P.begin()+T*i,P.begin()+T*(i+1),P.begin()+T*rev[i]);
}
template<int T>inline void mul_mod(poly&P,poly&Q){
const int m=P.size(),n=m/T;
dft<T>(P),dft<T>(Q);
for(int i=0;i<n;++i){
vector<uLL>ans(T<<1);
for(int j=0;j<T;++j){
for(int k=0;k<T;++k)
ans[j+k]+=(LL)P[i*T+j]*Q[i*T+k];
if(!((~j)&7))for(int k=j;k<j+T;++k)
if(ans[k]>=(Mod2<<3))ans[k]-=Mod2<<3;
}
const int c=((i&1)?Mod-w0[i>>1]:w0[i>>1]);
for(int j=T;j--;)P[i*T+j]=(ans[j]+ans[j+T]%Mod*c)%Mod;
}
idft<T>(P);
}
template<size_t... m>inline void solve(index_sequence<m...>,int n,poly&P,poly&Q){
static void (*ptrs[])(poly&,poly&)={&mul_mod<m+1>...};
ptrs[n-1](P,Q);
}
inline poly Mul(poly P,poly Q){
if(P.empty()||Q.empty())return poly();
int pn=P.size(),qn=Q.size(),rn=pn+qn-1,b=1;
while((Lim<<b)<rn)++b;
const int T=((rn-1)>>b)+1,m=T<<b;
P.resize(m),Q.resize(m);
solve(make_index_sequence<Lim>{},T,P,Q);
return P.resize(rn),P;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n,m,k,ans=0;
cin>>n>>m>>k;
poly frc(n*m+1),ivf(n*m+1);
frc[0]=1;
for(int i=1;i<=n*m;++i)frc[i]=1ll*frc[i-1]*i%Mod;
ivf[n*m]=qpow(frc[n*m],Mod-2);
for(int i=n*m;i;--i)ivf[i-1]=1ll*ivf[i]*i%Mod;
const auto binom=[&](const int&n,const int&m){
return n<m||m<0?0:1ll*frc[n]*ivf[m]%Mod*ivf[n-m]%Mod;
};
poly F(n*m+1),G(n*m+1);
for(int i=0;i<=n*m;++i){
if(k>=i)F[i]=1ll*(i&1?Mod-ivf[i]:ivf[i])*ivf[k-i]%Mod;
if(n*m>=i+k)G[i]=1ll*ivf[i]*ivf[n*m-k-i]%Mod;
}
F=Mul(F,G);
for(int x=0;x<=n;++x)
for(int y=0;y<=m;++y){
const int k=x*(m-y)+(n-x)*y;
assert(k>=0&&k<F.size());
ans=(ans+(x+y&1?Mod-1ll:1ll)*F[k]%Mod*frc[k]%Mod*frc[n*m-k]%Mod*binom(n,x)%Mod*binom(m,y))%Mod;
}
return cout<<qpow(inv2,n+m,ans),0;
}
詳細信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 3796kb
input:
3 5 7
output:
105
result:
ok single line: '105'
Test #2:
score: 5
Accepted
time: 0ms
memory: 4024kb
input:
4 4 8
output:
144
result:
ok single line: '144'
Test #3:
score: 5
Accepted
time: 0ms
memory: 3928kb
input:
9 7 53
output:
11271960
result:
ok single line: '11271960'
Test #4:
score: 5
Accepted
time: 0ms
memory: 3832kb
input:
10 10 60
output:
711797984
result:
ok single line: '711797984'
Test #5:
score: 5
Accepted
time: 0ms
memory: 4284kb
input:
50 100 100
output:
684521374
result:
ok single line: '684521374'
Test #6:
score: 5
Accepted
time: 0ms
memory: 4272kb
input:
69 69 99
output:
205514286
result:
ok single line: '205514286'
Test #7:
score: 5
Accepted
time: 1ms
memory: 3956kb
input:
500 10 3232
output:
571588252
result:
ok single line: '571588252'
Test #8:
score: 5
Accepted
time: 1ms
memory: 3992kb
input:
70 70 4800
output:
851456413
result:
ok single line: '851456413'
Test #9:
score: 5
Accepted
time: 10ms
memory: 7408kb
input:
100 1000 50000
output:
437541409
result:
ok single line: '437541409'
Test #10:
score: 5
Accepted
time: 10ms
memory: 7484kb
input:
316 316 4238
output:
753478761
result:
ok single line: '753478761'
Test #11:
score: 5
Accepted
time: 3ms
memory: 7280kb
input:
201 479 30001
output:
594408179
result:
ok single line: '594408179'
Test #12:
score: 5
Accepted
time: 46ms
memory: 22904kb
input:
706 706 706
output:
835727049
result:
ok single line: '835727049'
Test #13:
score: 5
Accepted
time: 47ms
memory: 21920kb
input:
2023 233 2023
output:
801992885
result:
ok single line: '801992885'
Test #14:
score: 5
Accepted
time: 17ms
memory: 9816kb
input:
402 402 1000
output:
940937548
result:
ok single line: '940937548'
Test #15:
score: 5
Accepted
time: 14ms
memory: 12796kb
input:
707 333 999
output:
732112489
result:
ok single line: '732112489'
Test #16:
score: 5
Accepted
time: 30ms
memory: 17644kb
input:
600 600 18000
output:
579276872
result:
ok single line: '579276872'
Test #17:
score: 5
Accepted
time: 35ms
memory: 19320kb
input:
389 1047 40001
output:
186903191
result:
ok single line: '186903191'
Test #18:
score: 5
Accepted
time: 54ms
memory: 23092kb
input:
707 707 42837
output:
468460621
result:
ok single line: '468460621'
Test #19:
score: 5
Accepted
time: 47ms
memory: 23092kb
input:
100 5000 32346
output:
460579847
result:
ok single line: '460579847'
Test #20:
score: 5
Accepted
time: 22ms
memory: 13344kb
input:
501 501 251001
output:
1
result:
ok single line: '1'