QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#308105 | #7974. 染色 | yyyyxh | 100 ✓ | 163ms | 43448kb | C++23 | 2.7kb | 2024-01-19 15:50:39 | 2024-01-19 15:50:39 |
Judging History
answer
#include <cstdio>
#include <vector>
#include <algorithm>
#define ALL(vc) (vc).begin(),(vc).end()
using namespace std;
const int N=1000003,P=998244353;
typedef long long ll;
typedef vector<int> vi;
int n,m,k;
int rev[1<<20],cw[1<<20|1];
int ilen,len,bit;
inline void inc(int &x,int v){if((x+=v)>=P) x-=P;}
inline void dec(int &x,int v){if((x-=v)<0) x+=P;}
int qp(int a,int b=P-2){
int res=1;
while(b){
if(b&1) res=(ll)res*a%P;
a=(ll)a*a%P;b>>=1;
}
return res;
}
void init(int _len){
len=1;bit=-1;
while(len<_len) len<<=1,++bit;
int w=qp(3,(P-1)>>(bit+1));
cw[len]=cw[0]=1;
for(int i=1;i<len;++i){
rev[i]=(rev[i>>1]>>1)|((i&1)<<bit);
cw[i]=(ll)cw[i-1]*w%P;
}
ilen=qp(len);
}
struct poly{
vi f;
poly(int Len):f(Len){}
poly(initializer_list<int> Init):f(Init){}
void NTT(){
f.resize(len,0);
for(int i=0;i<len;++i) if(i<rev[i]) swap(f[i],f[rev[i]]);
for(int i=1,tt=len>>1;i<len;i<<=1,tt>>=1)
for(int j=0;j<len;j+=(i<<1))
for(int k=j,t=0;k<(j|i);++k,t+=tt){
int x=f[k],y=(ll)f[k|i]*cw[t]%P;
if((f[k]=x+y)>=P) f[k]-=P;
if((f[k|i]=x-y)<0) f[k|i]+=P;
}
}
void INTT(){
for(int i=0;i<len;++i) if(i<rev[i]) swap(f[i],f[rev[i]]);
for(int i=1,tt=len>>1;i<len;i<<=1,tt>>=1)
for(int j=0;j<len;j+=(i<<1))
for(int k=j,t=len;k<(j|i);++k,t-=tt){
int x=f[k],y=(ll)f[k|i]*cw[t]%P;
if((f[k]=x+y)>=P) f[k]-=P;
if((f[k|i]=x-y)<0) f[k|i]+=P;
}
for(int i=0;i<len;++i) f[i]=(ll)f[i]*ilen%P;
while(!f.empty()&&!f.back()) f.pop_back();
}
};
int fac[N],fiv[N];
int C(int n,int k){return (ll)fac[n]*fiv[k]%P*fiv[n-k]%P;}
int a[N],pw[N],res[N];
int main(){
// freopen("paint.in","r",stdin);
// freopen("paint.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
int lim=n*m;
fac[0]=1;
for(int i=1;i<=lim;++i) fac[i]=(ll)fac[i-1]*i%P;
fiv[lim]=qp(fac[lim]);
for(int i=lim;i;--i) fiv[i-1]=(ll)fiv[i]*i%P;
pw[0]=1;
for(int i=1;i<=lim;++i) inc(pw[i]=pw[i-1],pw[i-1]);
for(int i=0;i<=n;++i)
for(int j=0;j<=m;++j){
int pos=i*j+(n-i)*(m-j);
if((i^j)&1){
a[pos]=(a[pos]-(ll)C(n,i)*C(m,j))%P;
if(a[pos]<0) a[pos]+=P;
}
else a[pos]=(a[pos]+(ll)C(n,i)*C(m,j))%P;
}
poly F(lim+1),G(lim+1);
init(lim<<1|1);
for(int i=0;i<=lim;++i) F.f[i]=(ll)fac[i]*a[i]%P;
for(int i=0;i<=lim;++i)
if(i&1) G.f[i]=P-fiv[i];
else G.f[i]=fiv[i];
reverse(ALL(G.f));
F.NTT();G.NTT();
poly H(len);
for(int i=0;i<len;++i) H.f[i]=(ll)F.f[i]*G.f[i]%P;
H.INTT();
int Hlen=H.f.size();
for(int i=lim;i<Hlen;++i) res[lim+lim-i]=(ll)H.f[i]*fiv[i-lim]%P*pw[i-lim]%P;
int ans=0;
for(int i=k;i<=lim;++i) ans=(ans+(ll)C(i,k)*res[i])%P;
ans=(ll)ans*qp(2,P-1-n-m)%P;
if(ans&&(n&1)) ans=P-ans;
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 0ms
memory: 11980kb
input:
3 5 7
output:
105
result:
ok single line: '105'
Test #2:
score: 5
Accepted
time: 2ms
memory: 12236kb
input:
4 4 8
output:
144
result:
ok single line: '144'
Test #3:
score: 5
Accepted
time: 0ms
memory: 12068kb
input:
9 7 53
output:
11271960
result:
ok single line: '11271960'
Test #4:
score: 5
Accepted
time: 2ms
memory: 12012kb
input:
10 10 60
output:
711797984
result:
ok single line: '711797984'
Test #5:
score: 5
Accepted
time: 3ms
memory: 12488kb
input:
50 100 100
output:
684521374
result:
ok single line: '684521374'
Test #6:
score: 5
Accepted
time: 0ms
memory: 12228kb
input:
69 69 99
output:
205514286
result:
ok single line: '205514286'
Test #7:
score: 5
Accepted
time: 3ms
memory: 12204kb
input:
500 10 3232
output:
571588252
result:
ok single line: '571588252'
Test #8:
score: 5
Accepted
time: 3ms
memory: 12460kb
input:
70 70 4800
output:
851456413
result:
ok single line: '851456413'
Test #9:
score: 5
Accepted
time: 23ms
memory: 16292kb
input:
100 1000 50000
output:
437541409
result:
ok single line: '437541409'
Test #10:
score: 5
Accepted
time: 24ms
memory: 20128kb
input:
316 316 4238
output:
753478761
result:
ok single line: '753478761'
Test #11:
score: 5
Accepted
time: 24ms
memory: 22084kb
input:
201 479 30001
output:
594408179
result:
ok single line: '594408179'
Test #12:
score: 5
Accepted
time: 154ms
memory: 41124kb
input:
706 706 706
output:
835727049
result:
ok single line: '835727049'
Test #13:
score: 5
Accepted
time: 157ms
memory: 41208kb
input:
2023 233 2023
output:
801992885
result:
ok single line: '801992885'
Test #14:
score: 5
Accepted
time: 43ms
memory: 27616kb
input:
402 402 1000
output:
940937548
result:
ok single line: '940937548'
Test #15:
score: 5
Accepted
time: 40ms
memory: 25828kb
input:
707 333 999
output:
732112489
result:
ok single line: '732112489'
Test #16:
score: 5
Accepted
time: 152ms
memory: 40428kb
input:
600 600 18000
output:
579276872
result:
ok single line: '579276872'
Test #17:
score: 5
Accepted
time: 153ms
memory: 40748kb
input:
389 1047 40001
output:
186903191
result:
ok single line: '186903191'
Test #18:
score: 5
Accepted
time: 159ms
memory: 43448kb
input:
707 707 42837
output:
468460621
result:
ok single line: '468460621'
Test #19:
score: 5
Accepted
time: 163ms
memory: 41112kb
input:
100 5000 32346
output:
460579847
result:
ok single line: '460579847'
Test #20:
score: 5
Accepted
time: 48ms
memory: 28260kb
input:
501 501 251001
output:
1
result:
ok single line: '1'