QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#282663#7607. The Doubling Game 2light_ink_dots#WA 0ms17668kbC++202.0kb2023-12-12 18:29:592023-12-12 18:29:59

Judging History

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

  • [2023-12-12 18:29:59]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:17668kb
  • [2023-12-12 18:29:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn=300005,maxk=20,mod=1000000007;
int n;
int f[maxn<<1],g[maxk][maxn<<1],nf[maxn<<1],ng[maxk][maxn<<1],T[maxn],F[maxn][maxk],G[maxn][maxk],H[maxn];
vector<int>v[maxn];
inline void inc(int &x,int y){
	x+=y;
	if(x>=mod)
		x-=mod;
}
inline int cmp(int a,int b){
	return T[a]<T[b];
}
void dfs(int x,int last){
	vector<int>s;
	for(int i=0;i<v[x].size();i++){
		int y=v[x][i];
		if(y==last)
			continue;
		dfs(y,x),s.emplace_back(y);
	}
	v[x].swap(s),sort(v[x].begin(),v[x].end(),cmp);
	while(T[x]<v[x].size()&&T[v[x][T[x]]]>=T[x])
		T[x]++;
	for(int i=0;i<(1<<T[x]+1);i++){
		f[i]=0;
		for(int j=0;j<=T[x];j++)
			g[i][j]=0;
	}
	f[0]=1;
	for(int u=0;u<v[x].size();u++){
		int y=v[x][u],S=1<<(T[y]+1);
		for(int i=0;i<S;i++)
			if(f[i]){
				inc(nf[i],1ll*f[i]*H[y]%mod);
				for(int j=0;j<=T[y];j++)
					if(((i>>j)&1)==0)
						inc(nf[i|(1<<j)],1ll*f[i]*F[y][j]%mod);
				for(int j=0;j<=T[y];j++)
					inc(ng[j][i],1ll*f[i]*G[y][j]%mod);
			}
		for(int i=0;i<=T[y];i++)
			for(int j=0;j<(1<<i);j++)
				if(g[i][j]){
					inc(ng[i][j],1ll*g[i][j]*H[y]%mod);
					for(int k=0;k<i;k++)
						if(((j>>k)&1)==0)
							inc(ng[i][j|(1<<k)],1ll*g[i][j]*F[y][k]%mod);
				}
		for(int i=0;i<S;i++){
			f[i]=nf[i],nf[i]=0;
			for(int j=0;j<=T[y];j++)
				g[i][j]=ng[i][j],ng[i][j]=0;
		}
	}
	for(int i=0;i<=T[x]+1;i++)
		for(int j=0;j<(1<<(min(T[x],i)+1));j++){
			if(__builtin_popcount(j)==i)
				inc(F[x][i],f[j]),inc(H[x],g[i][j]);
			else if(__builtin_popcount(j)==i-1){
				int nxt=__builtin_ctz(((1<<i)-1)^j);
				inc(G[x][nxt],f[j]),inc(g[x][nxt],g[i][j]);
			}
		}
	for(int i=0;i<=T[x];i++)
		inc(H[x],F[x][i]);
//	printf("x=%d H[x]=%d T[x]=%d\n",x,H[x],T[x]);
//	for(int i=0;i<=T[x];i++)
//		printf("i=%d F=%d G=%d\n",i,F[x][i],G[x][i]);
}
int main(){
	scanf("%d",&n);
	for(int i=1,x,y;i<n;i++)
		scanf("%d%d",&x,&y),v[x].emplace_back(y),v[y].emplace_back(x);
	dfs(1,0);
	printf("%d\n",H[1]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 17668kb

input:

5
1 2
1 3
1 4
4 5

output:

20

result:

wrong answer 1st lines differ - expected: '21', found: '20'