QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#718735#7509. 01treefzxWA 28ms94712kbC++146.6kb2024-11-06 21:19:202024-11-06 21:19:22

Judging History

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

  • [2024-11-06 21:19:22]
  • 评测
  • 测评结果：WA
  • 用时：28ms
  • 内存：94712kb
查看
  • [2024-11-06 21:19:20]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long 
#define pb push_back
using namespace std;
const int Mod=1e9+7;
const int INF=1e6+5;
int n,col[INF],fav[INF],ifav[INF];string s,t;
vector <int> e[INF];
int ksm(int x,int y) {
    int ba=x%Mod,ans=1;
    while (y) {
        if (y&1) ans=(ans*ba)%Mod;
        ba=(ba*ba)%Mod;y>>=1;
    }
    return ans;
}
void init() {
    fav[0]=1;int N=1e6;
    for (int i=1;i<=N;i++) fav[i]=fav[i-1]*i%Mod;
    ifav[N]=ksm(fav[N],Mod-2);
    for (int i=N-1;~i;i--) ifav[i]=ifav[i+1]*(i+1)%Mod;
}
int C(int x,int y) {
    if (x<y) return 0;
    return fav[x]*ifav[y]%Mod*ifav[x-y]%Mod;
}
void DFS(int x,int fa) {
    for (int v:e[x]) {
        if (v==fa) continue;
        col[v]=col[x]^1;
        DFS(v,x);
    }
}
int A[5],B[5];
int sz1[INF][5],sz2[INF][5],res;
int X,Y,Z;
struct P3{
	int x,y,z;
};
vector <P3> v3[INF],v4[INF];
void DFS2(int x,int fa) {
    for (int w=0;w<3;w++) sz1[x][w]=sz2[x][w]=0;
    if (s[x]=='?') sz1[x][0]++;
    else if (s[x]=='0') sz1[x][1]++;
    else sz1[x][2]++;

    if (t[x]=='?') sz2[x][0]++;
    else if (t[x]=='0') sz2[x][1]++;
    else sz2[x][2]++;
    for (int v:e[x]) {
        if (v==fa) continue;
        DFS2(v,x);
        // W<=B[1]-A[1]+T2
        // B[1]-A[1]-T1
        if (Y>=0) {
            res-=(sz1[v][0]+sz1[v][1]-sz2[v][1])*C(Z,Y);
            res%=Mod;res+=Mod;res%=Mod;
            res+=(sz1[v][0]+sz2[v][0])*C(Z-1,Y-1)%Mod;res%=Mod;
            // for (int W=0;W<Y;W++) {
            //     res+=C(sz1[v][0]+sz2[v][0]-1,W)%Mod
            //         *C(Z-sz2[v][0]-sz1[v][0],Y-1-W)%Mod*(sz1[v][0]+sz2[v][0]);
            //     res%=Mod;
            // }
        }
        v3[v].pb({min(Y,sz1[v][0]+sz1[v][1]-sz2[v][1]),
			sz1[v][0]+sz2[v][0],(sz1[v][0]+sz1[v][1]-sz2[v][1])*2});
        v4[v].pb({min(Y,sz1[v][0]+sz1[v][1]-sz2[v][1])-1,
			sz1[v][0]+sz2[v][0]-1,(sz1[v][0]+sz2[v][0])*-2});

//        v4[v].pb({min(Y,sz1[v][0]+sz1[v][1]-sz2[v][1])-1,sz1[v][0]+sz2[v][0]-1,-(sz1[v][0]+sz2[v][0])*2});
        
//        for (int W=0;W<=min(Y,sz1[v][0]+sz1[v][1]-sz2[v][1]);W++) {
//            res+=C(sz1[v][0]+sz2[v][0],W)%Mod
//                *C(Z-sz2[v][0]-sz1[v][0],Y-W)%Mod*(sz1[v][0]+sz1[v][1]-sz2[v][1])*2;
//            res%=Mod;
//        }

//        for (int W=0;W<=min(Y,sz1[v][0]+sz1[v][1]-sz2[v][1])-1;W++) {
//            res+=C(sz1[v][0]+sz2[v][0]-1,W)%Mod
//                *C(Z-1-sz2[v][0]-sz1[v][0]+1,Y-1-W)%Mod*(sz1[v][0]+sz2[v][0])*-2;
//            res%=Mod;
//        }
        for (int i=0;i<3;i++)
            sz1[x][i]+=sz1[v][i],
            sz2[x][i]+=sz2[v][i];
    }
}
void DFS3(int x,int fa) {
	for (int v:e[x]) {
		if (v==fa) continue;
		DFS3(v,x);
	}
	if (x==1) return ;
	int a7=v3[x][0].x,b7=v3[x][0].y,c7=v3[x][0].z;
	P3 Min;int F=0;
	for (int v:e[x]) {
		if (v==fa) continue;
		if (!F) Min=v3[v][0],F=1;
		else if (abs(Min.x-a7)+abs(Min.y-b7)>abs(v3[v][0].x-a7)+abs(v3[v][0].y-b7))
			Min=v3[v][0];
	}
	if (!F) {
		int Sum3=0;
		for (int W=0;W<=a7;W++) {
            Sum3+=C(b7,W)%Mod*C(Z-b7,Y-W)%Mod;
            Sum3%=Mod;
        }
        // C(b7+1,W)*C(Z-b7-1,Y-W)
//        cerr<<Sum3<<" "<<x<<" qwaqwq?\n";
        res+=c7*Sum3;res%=Mod;
        v3[x][0].z=Sum3;
	} else {
//		if (x==2)
//			cerr<<" "<<a7<<" "<<b7<<" "<<Min.x<<" "<<Min.y<<" ewotj\n";
		assert(Min.y<=b7);
//		assert(Min.x<=a7);
		int Sum3=Min.z;
//		
		while (Min.y<b7) {
			Min.y++;
			if (Min.y<=Min.x) {
				Sum3=0;
				for (int W=0;W<=Min.x;W++) {
		            Sum3+=C(Min.y,W)%Mod*C(Z-Min.y,Y-W)%Mod;
		            Sum3%=Mod;
		        }
//				Sum3=C(Z,Y);
			}
			else {
				Sum3=0;
				for (int W=0;W<=Min.x;W++) {
		            Sum3+=C(Min.y,W)%Mod*C(Z-Min.y,Y-W)%Mod;
		            Sum3%=Mod;
		        }
//				Sum3-=C(Min.y-1,Min.x)*C(Z-1-Min.y+1,Y-1-Min.x);
//				Sum3%=Mod,Sum3+=Mod,Sum3%=Mod;
			}
		}
		while (Min.x<a7) {
			Min.x++;
//			Sum3=0;
//			for (int W=0;W<=Min.x;W++) {
//	            Sum3+=C(Min.y,W)%Mod*C(Z-Min.y,Y-W)%Mod;
//	            Sum3%=Mod;
//	        }
			
			if (Y-Min.x>=0 && Z-Min.y>=0)
				Sum3+=C(Min.y,Min.x)%Mod*C(Z-Min.y,Y-Min.x)%Mod,Sum3%=Mod;
		}
		while (Min.x>a7) {
			Min.x--;
			Sum3=0;
			for (int W=0;W<=Min.x;W++) {
	            Sum3+=C(Min.y,W)%Mod*C(Z-Min.y,Y-W)%Mod;
	            Sum3%=Mod;
	        }
//			if (Y-Min.x-1>=0)
//				Sum3-=C(Min.y,Min.x+1)%Mod*C(Z-Min.y,Y-Min.x-1)%Mod;
		}
        res+=c7*Sum3;res%=Mod;
        v3[x][0].z=Sum3;
	}
}

void DFS4(int x,int fa) {
	for (int v:e[x]) {
		if (v==fa) continue;
		DFS4(v,x);
	}
	if (x==1) return ;
	int a7=v4[x][0].x,b7=v4[x][0].y,c7=v4[x][0].z;
	P3 Min;int F=0;
	for (int v:e[x]) {
		if (v==fa) continue;
		if (!F) Min=v4[v][0];
		else if (abs(Min.x-a7)+abs(Min.y-b7)>abs(v4[v][0].x-a7)+abs(v4[v][0].y-b7))
			Min=v4[v][0];
	}
	if (!F) {
		int Sum3=0;
		for (int W=0;W<=a7;W++) {
            Sum3+=C(b7,W)%Mod*C(Z-b7,Y-W)%Mod;
            Sum3%=Mod;
        }
//        cerr<<Sum3<<" "<<<<" qwerojqwero\n";
        // C(b7+1,W)*C(Z-b7-1,Y-W)
        res+=c7*Sum3;res%=Mod;
        v4[x][0].z=Sum3;
	} else {
//		cerr<<Min.x<<" "<<a7<<" qweroij\n";
		assert(Min.y<=b7);
		assert(Min.x<=a7);
		int Sum3=Min.z;
		while (Min.y<b7) {
			Min.y++;
			if (Min.y<=Min.x) Sum3=C(Z,Y);
			else Sum3-=C(Min.x,Min.y)*C(Z-1-Min.x,Y-1-Min.y),Sum3%=Mod,Sum3+=Mod,Sum3%=Mod;
		}
		while (Min.x<a7) {
			Min.x++;
			Sum3+=C(Min.y,Min.x)%Mod*C(Z-Min.y,Y-Min.x)%Mod;
		}
        res+=c7*Sum3;res%=Mod;
        v4[x][0].z=Sum3;
	}
}
void solve() {
    for (int w=0;w<=n+3;w++) 
		e[w].clear(),v3[w].clear(),v4[w].clear();
    cin>>n;res=0;
    for (int i=1;i<n;i++) {
        int x=0,y=0;
        cin>>x>>y;
        e[x].pb(y);
        e[y].pb(x);
    }
    for (int w=0;w<3;w++) A[w]=B[w]=0;
    DFS(1,0);cin>>s>>t;s=" "+s;t=" "+t;
    for (int i=1;i<=n;i++) {
        if (s[i]=='?') {A[0]++;continue;}
        if (col[i]==1) {
            if (s[i]=='0') s[i]='1';
            else s[i]='0';
        }
        if (s[i]=='0') A[1]++;
        else A[2]++;
    }
    for (int i=1;i<=n;i++) {
        if (t[i]=='?') {B[0]++;continue;}
        if (col[i]==1) {
            if (t[i]=='0') t[i]='1';
            else t[i]='0';
        }
        if (t[i]=='0') B[1]++;
        else B[2]++;
    }
    X=-B[1]+A[1]-B[0];
    Y=-B[1]+A[1]+A[0];
    Z=A[0]+B[0];
    DFS2(1,0);
	DFS3(1,0);
	Z--;Y--;DFS4(1,0);
    res%=Mod;res+=Mod;res%=Mod;
    cout<<res<<"\n";
}
signed main()
{
    ios::sync_with_stdio(false);
    int t=0;cin>>t;init();
    while (t--) solve();
    return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 19ms
memory: 94712kb

input:

3
2
1 2
00
11
3
1 2
2 3
???
???
3
1 2
2 3
??1
0?0

output:

1
16
1

result:

ok 3 number(s): "1 16 1"

Test #2:

score: -100
Wrong Answer
time: 28ms
memory: 94260kb

input:

1000
23
1 2
1 3
1 4
2 5
5 6
4 7
3 8
4 9
8 10
8 11
8 12
1 13
7 14
10 15
7 16
7 17
5 18
18 19
12 20
9 21
21 22
6 23
00?10?0000??1?00111?010
011??1?10?01?110?0??101
6
1 2
1 3
1 4
4 5
3 6
000?10
1???01
25
1 2
2 3
2 4
4 5
5 6
2 7
4 8
5 9
7 10
8 11
11 12
5 13
11 14
3 15
6 16
14 17
1 18
4 19
6 20
4 21
5 22...

output:

53545
24
11724
2228
162
14
711
28
550
1680
52
2
13
988
9480
2342
626416
0
71780
1
88
39207
19448
4
37395
9602
3253496
38057200
1066
3
303732
1608
281022
11718
170
78
15
1219376
29364
9092
7
0
2
7014
1942448
170371
75845
167217
16554
64
904
564290
14822
1127090
1758504
1227646
14833316
14954550
36055...

result:

wrong answer 236th numbers differ - expected: '17', found: '1'
English 繁體中文 简体中文

伺服器時間: 2024-12-03 02:46:43 | 開源專案