QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#234575 | #7607. The Doubling Game 2 | zlt | ML | 8ms | 90448kb | C++14 | 2.2kb | 2023-11-01 19:26:24 | 2023-11-01 19:26:26 |
Judging History
answer
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 300100;
const ll mod = 1000000007;
ll n, h[maxn];
vector<int> G[maxn];
vector<ll> f[maxn], g[maxn], cf[2], cg[2];
void dfs(int u, int fa) {
if (fa != -1) {
G[u].erase(find(G[u].begin(), G[u].end(), fa));
}
for (int v : G[u]) {
dfs(v, u);
}
int o = 0;
vector<ll>(1, 1).swap(cf[0]);
vector<ll>(1, 0).swap(cg[0]);
sort(G[u].begin(), G[u].end(), [&](const int &x, const int &y) {
return f[x].size() < f[y].size();
});
for (int v : G[u]) {
o ^= 1;
vector<ll>(1 << (int)f[v].size()).swap(cf[o]);
vector<ll>(1 << (int)f[v].size()).swap(cg[o]);
for (int S = 0; S < (int)cf[o ^ 1].size(); ++S) {
cf[o][S] = (cf[o][S] + cf[o ^ 1][S] * h[v]) % mod;
cg[o][S] = (cg[o][S] + cg[o ^ 1][S] * h[v]) % mod;
for (int i = 0; i < (int)f[v].size(); ++i) {
if (S & (1 << i)) {
continue;
}
cf[o][S | (1 << i)] = (cf[o][S | (1 << i)] + cf[o ^ 1][S] * f[v][i]) % mod;
if (S > (1 << i)) {
cg[o][S | (1 << i)] = (cg[o][S | (1 << i)] + cg[o ^ 1][S] * f[v][i]) % mod;
} else {
cg[o][S | (1 << i)] = (cg[o][S | (1 << i)] + cf[o ^ 1][S] * g[v][i]) % mod;
}
}
}
}
int k = __lg((int)cf[o].size());
f[u] = g[u] = vector<ll>(k + 1);
for (int i = 0; i <= k; ++i) {
int S = (1 << i) - 1;
h[u] = (h[u] + cf[o][S] + cg[o][S]) % mod;
f[u][i] = (f[u][i] + cf[o][S]) % mod;
g[u][i] = (g[u][i] + cf[o][S]) % mod;
for (int j = 0; j <= i - 2; ++j) {
g[u][j] = (g[u][j] + cf[o][S ^ (1 << j)] + cg[o][S ^ (1 << j)]) % mod;
}
}
for (int o = 0; o <= 1; ++o) {
vector<ll>().swap(cf[o]);
vector<ll>().swap(cg[o]);
}
}
void solve() {
scanf("%lld", &n);
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
G[u].pb(v);
G[v].pb(u);
}
dfs(1, -1);
printf("%lld\n", h[1]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 26408kb
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: 26940kb
input:
1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 6ms
memory: 25764kb
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: 27144kb
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: 0
Accepted
time: 3ms
memory: 27188kb
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...
output:
37387055
result:
ok single line: '37387055'
Test #6:
score: 0
Accepted
time: 8ms
memory: 90448kb
input:
1024 340 598 1 851 245 819 414 736 996 316 300 284 924 407 532 557 362 178 1006 469 397 373 742 77 112 37 406 892 703 666 496 825 1002 100 875 856 263 975 227 6 288 389 661 437 160 626 833 770 912 837 405 628 466 686 45 629 59 13 163 991 1017 422 208 247 344 376 709 956 570 272 996 954 518 454 267 3...
output:
689180079
result:
ok single line: '689180079'
Test #7:
score: 0
Accepted
time: 6ms
memory: 33448kb
input:
2048 2046 1942 589 1449 1593 1983 936 414 387 184 1962 1237 1986 635 573 1619 1598 1109 458 836 1123 1563 1502 519 1467 347 1815 864 980 405 709 433 1682 211 1967 1915 1089 1902 564 211 128 1004 1568 315 293 494 1552 1772 1641 1157 431 1899 1334 1623 161 1870 885 1330 1863 502 1761 1643 692 1759 118...
output:
275839338
result:
ok single line: '275839338'
Test #8:
score: -100
Memory Limit Exceeded
input:
4096 2546 3568 3084 3426 1262 2128 1773 1455 425 3750 3444 3265 3099 464 3479 3651 639 1727 2486 2768 1165 1905 1847 2626 1335 3938 2550 1594 1520 1758 3771 2227 3486 60 381 383 1268 2829 1884 3468 3195 2892 983 31 584 2599 2811 1876 1875 3310 3184 2941 2893 202 1305 1926 1019 1639 3529 1998 2129 12...
output:
99235843