QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#717113 | #7509. 01tree | fzx | TL | 79ms | 61636kb | C++14 | 2.5kb | 2024-11-06 16:57:19 | 2024-11-06 16:57:21 |
Judging History
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;
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
for (int W=0ll;W<=min(Y,sz1[v][0]+sz2[v][0]);W++) {
res+=C(sz1[v][0]+sz2[v][0],W)%Mod
*C(Z-sz2[v][0]-sz1[v][0],Y-W)%Mod*abs(sz1[v][0]-W+sz1[v][1]-sz2[v][1]);
res%=Mod;
}
for (int i=0;i<3;i++)
sz1[x][i]+=sz1[v][i],
sz2[x][i]+=sz2[v][i];
}
}
void solve() {
for (int w=0;w<=n+3;w++) e[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);
cout<<res<<"\n";
}
signed main()
{
ios::sync_with_stdio(false);
int t=0;cin>>t;init();
while (t--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 14ms
memory: 48612kb
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: 0
Accepted
time: 15ms
memory: 46628kb
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:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 11ms
memory: 46868kb
input:
1 3000 1 2 2 3 2 4 1 5 3 6 2 7 5 8 8 9 9 10 10 11 2 12 11 13 7 14 11 15 7 16 13 17 8 18 1 19 11 20 10 21 18 22 7 23 7 24 15 25 23 26 24 27 14 28 15 29 25 30 16 31 6 32 10 33 3 34 30 35 16 36 9 37 36 38 28 39 26 40 33 41 1 42 11 43 20 44 23 45 14 46 31 47 41 48 11 49 48 50 45 51 6 52 10 53 32 54 38 5...
output:
924036898
result:
ok 1 number(s): "924036898"
Test #4:
score: 0
Accepted
time: 12ms
memory: 46844kb
input:
1 3000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 2...
output:
429465738
result:
ok 1 number(s): "429465738"
Test #5:
score: 0
Accepted
time: 25ms
memory: 47544kb
input:
1 3000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...
output:
650625747
result:
ok 1 number(s): "650625747"
Test #6:
score: 0
Accepted
time: 79ms
memory: 60360kb
input:
1 100000 1 2 1 3 3 4 1 5 2 6 6 7 2 8 1 9 6 10 1 11 3 12 11 13 5 14 9 15 12 16 6 17 13 18 13 19 14 20 7 21 14 22 21 23 12 24 17 25 14 26 3 27 4 28 8 29 22 30 12 31 6 32 30 33 4 34 15 35 12 36 3 37 20 38 7 39 37 40 5 41 13 42 34 43 9 44 27 45 39 46 43 47 3 48 17 49 36 50 12 51 1 52 45 53 35 54 15 55 2...
output:
143309878
result:
ok 1 number(s): "143309878"
Test #7:
score: 0
Accepted
time: 62ms
memory: 61636kb
input:
1 100000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54...
output:
724432513
result:
ok 1 number(s): "724432513"
Test #8:
score: -100
Time Limit Exceeded
input:
1 100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...