QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#227712 | #6623. Perfect Matchings | whsyhyyh | TL | 1ms | 10188kb | C++14 | 4.2kb | 2023-10-27 21:52:31 | 2023-10-27 21:52:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int M=4005;
const int P=998244353,G=3,G_i=332748118;
int n,tot;
int hd[M],to[M<<1],nx[M<<1];
void add(int u,int v) {
nx[++tot]=hd[u];
to[tot]=v;
hd[u]=tot;
}
int dp[2][M][M];
int Sz[M];
int A[M<<1],B[M<<1];
int C[M][M];
int F[M<<1];
int Mx=1,cnt,now,sw=1;
void Add(int &x,int y) {
x+=y;(x>=P)&&(x-=P);
}
int fpow(int a,int cnt) {
int res=1;
for(int i=cnt; i; i>>=1,a=1LL*a*a%P)if(i&1)res=1LL*res*a%P;
return res;
}
int pos[M<<1];
void NTT(int *a,int f) {
for(int i=0; i<Mx; ++i)if(i<pos[i])swap(a[pos[i]],a[i]);
for(int len=1; len<Mx; len<<=1) {
now=fpow(f?G:G_i,(P-1)/(len<<1));
for(int L=0; L<Mx; sw=1,L+=len<<1) {
for(int R=L; R<L+len; ++R,sw=1LL*sw*now%P) {
int xx=a[R],yy=1LL*a[R+len]*sw%P;
a[R]=xx+yy;(a[R]>=P)&&(a[R]-=P);
a[R+len]=xx-yy;(a[R+len]<0)&&(a[R+len]+=P);
}
}
}
}
int Sum[2][M<<1];
void Solve(int now,int Fa) {
dp[1][now][1]=1;Sz[now]=1;
for(int i=hd[now]; i; i=nx[i]) {
int To=to[i];
if(To==Fa)continue;
Solve(To,now);
// cout<<"To:"<<To<<" "<<endl;
int Minn=min(Sz[now],Sz[To]);
memset(Sum,0,sizeof Sum);
for(int k=0; k<=Minn; ++k) {
Mx=1;cnt=0;
while(Mx<=Sz[now]+Sz[To]-k*2)Mx<<=1,cnt++;
for(int j=0; j<Mx; ++j)pos[j]=(pos[j>>1]>>1)|((j&1)<<cnt-1);
for(int j=0; j<Mx; ++j)A[j]=B[j]=0;
for(int j=k; j<=Sz[now]; ++j)if(j)A[j-k]=1LL*dp[1][now][j]*C[j-1][k]%P;
for(int j=k; j<=Sz[To]; ++j)B[j-k]=1LL*(dp[1][To][j]+dp[0][To][j])*C[j][k]%P*F[k]%P;
NTT(A,1),NTT(B,1);
for(int j=0; j<Mx; ++j)A[j]=1LL*A[j]*B[j]%P;
NTT(A,0);
int inv_Mx=fpow(Mx,P-2);
for(int j=0; j<=Sz[now]+Sz[To]-k*2; ++j)Sum[1][j]=(Sum[1][j]+1LL*A[j]*inv_Mx)%P;
for(int j=0; j<Mx; ++j)A[j]=0;
for(int j=k; j<=Sz[now]; ++j)A[j-k]=1LL*dp[0][now][j]*C[j][k]%P;
NTT(A,1);
for(int j=0; j<Mx; ++j)A[j]=1LL*A[j]*B[j]%P;
NTT(A,0);
// if(To==3&&now==1)cout<<k<<"A[0]:"<<A[1]<<" "<<Sum[0][1]<<" "<<Sum[0][1]<<endl;
for(int j=0; j<=Sz[now]+Sz[To]-k*2; ++j)Sum[0][j]=(Sum[0][j]+1LL*A[j]*inv_Mx)%P;
// if(To==3&&now==1)cout<<k<<"A[0]:"<<A[1]<<" "<<Sum[0][1]<<" "<<Sum[0][1]<<endl;
// if(To==2&&k==1)cout<<Sum[0][0]<<" WWW"<<" "<<dp[0][1][1]<<" "<<dp[1][2][1]<<" "<<C[1][1]<<endl;
for(int j=0; j<Mx; ++j)A[j]=B[j]=0;
for(int j=k+1; j<=Sz[now]; ++j)A[j-k-1]=1LL*dp[1][now][j]*C[j-1][k]%P;
for(int j=k+1; j<=Sz[To]; ++j) {
B[j-k-1]=(1LL*dp[1][To][j]*(j-1)%P*C[j-1][k]%P*F[k]+1LL*dp[0][To][j]%P*C[j][k+1]%P*F[k+1])%P;
// if(now==2&&k==0&&j==2)cout<<"test:"<<1LL*dp[0][To][j]*j%P*C[j][k+1]%P*F[k+1]<<" "<<dp[0][To][j]<<" "<<B[1]<<endl;
}
// if(now==2)cout<<"A[0]:"<<A[0]<<" B[1]"<<B[1]<<" k:"<<k<<endl;
NTT(A,1),NTT(B,1);
for(int j=0; j<Mx; ++j)A[j]=1LL*A[j]*B[j]%P;
NTT(A,0);
// if(To==3&&now==1)cout<<k<<"A[0]:"<<A[1]<<" "<<Sum[0][1]<<" "<<Sum[0][1]<<endl;
for(int j=0; j<Mx; ++j)Sum[0][j]=(Sum[0][j]+1LL*A[j]*inv_Mx)%P;
// if(now==2)cout<<"k:"<<k<<" "<<Sum[0][1]<<endl;
// if(To==3&&now==1)cout<<k<<"A[0]:"<<A[1]<<" "<<Sum[0][1]<<" "<<Sum[0][1]<<endl;
}
for(int j=0; j<=Sz[now]+Sz[To]; ++j) dp[0][now][j]=Sum[0][j],dp[1][now][j]=Sum[1][j];
// if(now==1)cout<<dp[0][1][1]<<" ASDS"<<endl;
// if(To==3)cout<<"SADS"<<dp[0][now][1]<<" "<<endl;
Sz[now]+=Sz[To];
}
// cout<<now<<" "<<endl;
// for(int i=0; i<=Sz[now]; ++i)cout<<dp[1][now][i]<<" "<<" "<<dp[0][now][i]<<endl;
}
int main() {
// freopen("a.in","r",stdin);
scanf("%d",&n);
for(int i=1; i<n+n; ++i) {
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
F[0]=1;
for(int i=1; i<=n+n; ++i)F[i]=1LL*F[i-1]*i%P;
for(int i=0; i<=n+n; ++i) {
C[i][0]=1;
for(int j=1; j<=i; ++j) {
C[i][j]=C[i-1][j];
Add(C[i][j],C[i-1][j-1]);
}
}
Solve(1,0);
printf("%d",dp[0][1][0]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 8080kb
input:
2 1 2 1 3 3 4
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 9932kb
input:
3 1 2 2 3 3 4 4 5 5 6
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 1ms
memory: 10188kb
input:
10 2 1 3 2 4 2 5 3 6 3 7 5 8 4 9 3 10 5 11 3 12 9 13 11 14 8 15 5 16 1 17 4 18 1 19 11 20 19
output:
223263378
result:
ok 1 number(s): "223263378"
Test #4:
score: 0
Accepted
time: 1ms
memory: 8108kb
input:
10 2 1 3 1 4 1 5 1 6 5 7 3 8 7 9 3 10 2 11 3 12 5 13 12 14 10 15 11 16 10 17 4 18 14 19 4 20 4
output:
225215244
result:
ok 1 number(s): "225215244"
Test #5:
score: 0
Accepted
time: 0ms
memory: 10112kb
input:
10 2 1 3 1 4 3 5 3 6 5 7 3 8 5 9 3 10 8 11 2 12 1 13 11 14 2 15 3 16 3 17 2 18 11 19 10 20 3
output:
210104685
result:
ok 1 number(s): "210104685"
Test #6:
score: 0
Accepted
time: 1ms
memory: 8104kb
input:
10 2 1 3 2 4 3 5 1 6 2 7 5 8 2 9 3 10 2 11 10 12 7 13 12 14 2 15 2 16 15 17 2 18 6 19 15 20 8
output:
211263144
result:
ok 1 number(s): "211263144"
Test #7:
score: 0
Accepted
time: 0ms
memory: 8228kb
input:
10 2 1 3 2 4 3 5 2 6 2 7 1 8 7 9 3 10 8 11 5 12 6 13 11 14 8 15 1 16 13 17 2 18 14 19 11 20 12
output:
226024809
result:
ok 1 number(s): "226024809"
Test #8:
score: -100
Time Limit Exceeded
input:
1977 2 1 3 1 4 1 5 4 6 4 7 1 8 3 9 5 10 2 11 3 12 2 13 3 14 2 15 9 16 9 17 2 18 17 19 5 20 16 21 2 22 2 23 15 24 16 25 22 26 14 27 6 28 4 29 24 30 25 31 28 32 15 33 27 34 32 35 24 36 10 37 18 38 15 39 33 40 3 41 27 42 3 43 35 44 15 45 11 46 19 47 21 48 4 49 28 50 6 51 3 52 14 53 14 54 14 55 25 56 18...