QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#282663 | #7607. The Doubling Game 2 | light_ink_dots# | WA | 0ms | 17668kb | C++20 | 2.0kb | 2023-12-12 18:29:59 | 2023-12-12 18:29:59 |
Judging History
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'