QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#229487 | #7607. The Doubling Game 2 | yx20220802 | RE | 3ms | 15880kb | C++14 | 3.8kb | 2023-10-28 16:17:12 | 2023-10-28 16:17:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace IO_ER{
#define LL long long
#define db double
#define U unsigned
#define ULL U LL
#define In inline
#define Re register
#define f(a,b,i) for(int i=a,MAXN##i=b;i<=MAXN##i;i++)
#define ff(a,b,i) for(int i=a;i<b;i++)
#define f_(a,b,i) for(int i=a;i>=b;i--)
#define ff_(a,b,i) for(int i=a;i>b;i--)
typedef pair<LL,int> Pi;
int inf=0x3f3f3f3f;
int INF=0x7fffffff;
LL infll=0x3f3f3f3f3f3f3f3fll;
LL INFll=0x7fffffffffffffffll;
template<typename T>void read(T &x){
x=0;
int fl=0;
char ch=getchar();
while(ch<'0'||'9'<ch){
if(ch=='-')fl=1;
ch=getchar();
}
while('0'<=ch&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x=fl?-x:x;
}
template<typename T,typename ...Args>void read(T &x,Args &...args){
read(x);
read(args...);
}
}
using namespace IO_ER;
#define N 300050
#define mod 1000000007
template<typename T>In T mul(const T &a,const T &b){return 1ll*a*b%mod;}
template<typename T,typename ...Args>In T mul(const T &a,const T &b,const Args &...args){return mul(a,mul(b,args...));}
template<typename T>In T add(const T &a,const T &b){return a+b>=mod?a+b-mod:a+b;}
template<typename T,typename ...Args>In T add(const T &a,const T &b,const Args &...args){return add(a,add(b,args...));}
template<typename T>In void cadd(T &a,const T &b){a+=b;a>=mod?a-=mod:1;}
template<typename T,typename ...Args>In void cadd(T &a,const T &b,const Args &...args){cadd(a,b);cadd(a,args...);}
typedef vector<int> Vi;
typedef vector<array<int,2> > Vai;
int n;
Vi e[N];
int sz[N];
In bool cmp(int x,int y){return sz[x]<sz[y];}
int dp[N][20][2];
int sum[N];
In void dfs(int u,int fa){
sz[u]=1;
if(fa)e[u].erase(find(e[u].begin(),e[u].end(),fa));
for(auto v:e[u]){
dfs(v,u);
sz[u]+=sz[v];
}
sort(e[u].begin(),e[u].end(),cmp);
Vi g(4),h(4);
g[0]=1;
int lim=0;
for(auto v:e[u]){
if(v==e[u].back())lim++;
else lim=__lg(sz[v]);
int mx=(1<<(lim+2))-1;
g.resize(mx+2);
h.resize(mx+2);
f(0,mx,s)h[s]=mul(g[s],sum[v]);
f(0,lim+2,j){
if(!dp[v][j][0])continue;
f(0,mx,s){
if(s>>j&1)continue;
cadd(h[s|(1<<j)],mul(g[s],dp[v][j][0]));
}
}
swap(g,h);
}
f(0,lim+2,i){
dp[u][i][0]=g[(1<<i)-1];
cadd(sum[u],dp[u][i][0]);
ff(0,i,j)cadd(dp[u][j][1],g[(1<<i)-(1<<j)-1]);
}
Vai gg(4);
Vai hh(4);
gg[0][0]=1;
lim=0;
for(auto v:e[u]){
if(v==e[u].back())lim++;
else lim=__lg(sz[v]);
int mx=(1<<(lim+2))-1;
gg.resize(mx+2);
hh.resize(mx+2);
f(0,mx,s){
hh[s][0]=mul(gg[s][0],sum[v]);
hh[s][1]=mul(gg[s][1],sum[v]);
}
f(0,lim+2,j){
if(dp[v][j][0]){
f(0,mx,s){
if(s>>j&1)continue;
cadd(hh[s|(1<<j)][0],mul(gg[s][0],dp[v][j][0]));
if((1<<j)<s)cadd(hh[s|(1<<j)][1],mul(gg[s][1],dp[v][j][0]));
}
}
if(dp[v][j][1]){
f(0,(1<<j)-1,s){
cadd(hh[s^(1<<j)][1],mul(gg[s][0],dp[v][j][1]));
}
}
}
swap(gg,hh);
}
f(0,lim+2,i){
cadd(sum[u],gg[(1<<i)-1][1]);
ff(0,i-1,j)cadd(dp[u][j][1],gg[(1<<i)-(1<<j)-1][1]);
}
}
int main(){
read(n);
int u,v;
ff(1,n,i){
read(u,v);
e[u].emplace_back(v);
e[v].emplace_back(u);
}
dfs(1,0);
printf("%d",sum[1]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 13532kb
input:
5 1 2 1 3 1 4 4 5
output:
21
result:
ok single line: '21'
Test #2:
score: 0
Accepted
time: 0ms
memory: 15880kb
input:
1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 3ms
memory: 13704kb
input:
128 11 32 116 81 65 4 117 47 5 81 104 30 61 8 82 59 95 20 92 29 29 127 97 39 123 33 59 128 115 33 83 67 74 16 77 33 64 73 124 123 8 127 61 51 101 122 35 90 119 116 112 27 81 93 109 123 54 1 119 100 116 16 65 47 67 27 22 105 76 87 36 39 27 96 72 31 91 123 21 105 118 12 110 48 121 72 14 115 24 16 106 ...
output:
508800953
result:
ok single line: '508800953'
Test #4:
score: 0
Accepted
time: 0ms
memory: 13360kb
input:
256 53 177 57 242 74 90 107 104 209 169 132 70 152 142 71 168 143 99 91 130 202 140 49 165 209 193 209 137 159 188 247 48 49 21 20 208 155 185 120 231 83 87 37 84 143 18 106 8 114 79 191 158 208 256 133 252 215 92 199 108 166 168 39 217 85 69 204 139 100 75 111 6 230 198 79 130 26 155 155 38 55 81 1...
output:
999869740
result:
ok single line: '999869740'
Test #5:
score: -100
Runtime Error
input:
512 507 193 168 152 48 369 273 170 101 349 160 261 438 197 446 224 125 264 210 131 272 218 361 85 226 119 57 33 229 89 37 317 130 417 30 470 435 300 499 417 132 260 196 430 119 117 157 260 207 151 368 277 188 371 214 330 484 228 96 94 97 442 251 461 443 248 163 207 306 147 346 90 457 112 436 222 364...