QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#227712#6623. Perfect MatchingswhsyhyyhTL 1ms10188kbC++144.2kb2023-10-27 21:52:312023-10-27 21:52:31

Judging History

你现在查看的是最新测评结果

  • [2023-10-27 21:52:31]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:10188kb
  • [2023-10-27 21:52:31]
  • 提交

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...

output:


result: