QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#242057#7607. The Doubling Game 2Jryno1Compile Error//C++142.2kb2023-11-06 21:56:252023-11-06 21:56:26

Judging History

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

  • [2023-11-06 21:56:26]
  • 评测
  • [2023-11-06 21:56:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
//thanks for sinsop
#define int long long 
const int maxn=6e5+10,mod=1e9+7;
int n,lg[maxn],ans[maxn],siz[maxn];//ans:don't move
vector<int>UPF[maxn],DOWF[maxn];
//UPF:x -> fat  DOWF:fat -> x
vector<int>ed[maxn];
bool cmp(int x,int y){
	return siz[x]<siz[y];
}
void dfs(int x,int fat){
	vector<int>V;
	siz[x]=1;
	for(int i=0;i<ed[x].size();i++){
		int v=ed[x][i];
		if(v==fat)continue;
		dfs(v,x);
		siz[x]+=siz[v];
		V.push_back(v);
	}
	sort(V.begin(),V.end(),cmp);
	int sz=1;
	vector<int>UP(2),DOW(2);
	UP[0]=1;
	//UP:all sons go up(or don't); DOW:I went down
	for(auto v:V){
		if(v==fat)continue;
		vector<int>F(1<<UPF[v].size()+1),G(1<<UPF[v].size()+1);
		for(int S=0;S<sz;S++){
			//the son doesn't go up(or down) at all
			F[S]=(F[S]+UP[S]*ans[v]%mod)%mod;
			G[S]=(G[S]+DOW[S]*ans[v]%mod)%mod;
			//the son go up
			for(int k=0;k<UPF[v].size();k++){
				if((1<<k)&S)continue;
				F[S|(1<<k)]+=UPF[v][k]*UP[S]%mod;
				F[S|(1<<k)]%=mod;
				if(S>(1<<k)){
					G[S|(1<<k)]+=UPF[v][k]*DOW[S]%mod;//no effect(this one must go up)
					G[S|(1<<k)]%=mod;
				} else {
					G[S|(1<<k)]+=DOWF[v][k]*UP[S]%mod;//this one must go down
					G[S|(1<<k)]%=mod;
				}
			}
		}
		swap(F,UP),swap(G,DOW);
		sz=(1<<UPF[v].size());
		vector<int>().swap(F),vector<int>().swap(G);
	}
//	cout<<x<<" "<<sz<<endl;
	sz=lg[sz];
	UPF[x].resize(sz+1),DOWF[x].resize(sz+1);
	for(int i=0;i<=sz;i++){
		int S=(1<<i)-1;//full
//		cout<<"---"<<x<<" "<<S<<" "<<UP[S]<<endl;
		ans[x]+=UP[S],ans[x]%=mod;//not moving
		ans[x]+=DOW[S],ans[x]%=mod;
		UPF[x][i]+=UP[S],DOWF[x][i]+=UP[S];//mov
		UPF[x][i]%=mod,DOWF[x][i]%=mod;
		for(int j=0;j<=i-2;j++)DOWF[x][j]=(DOWF[x][j]+UP[S^(1<<j)]+DOW[S^(1<<j)])%mod;
	}
//	cout<<x<<" "<<ans[x]<<endl;
	while(!UPD[x].back()&&!DOWF[x].back())UPD[x].pop_back(),DOWF[x].pop_back()
}
signed main(){
	cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		ed[u].push_back(v),ed[v].push_back(u);
	}
//	lg[1]=1;
	for(int i=2;i<maxn;i++)lg[i]=lg[i>>1]+1;
	dfs(1,0);
	cout<<ans[1]<<endl;
	return 0;
}
/*
5
1 2
1 3
1 4
4 5
*/

详细

answer.code: In function ‘void dfs(long long int, long long int)’:
answer.code:66:16: error: ‘UPD’ was not declared in this scope; did you mean ‘UP’?
   66 |         while(!UPD[x].back()&&!DOWF[x].back())UPD[x].pop_back(),DOWF[x].pop_back()
      |                ^~~
      |                UP