QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#534127 | #7607. The Doubling Game 2 | Poetry | WA | 0ms | 172372kb | C++23 | 6.2kb | 2024-08-26 21:01:53 | 2024-08-26 21:01:54 |
Judging History
answer
#include <bits/stdc++.h>
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
template<typename T>
T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a = a * a) {
if (b & 1) {
res = res * a;
}
}
return res;
}
template<const i64 P>
class ModInt {
public:
i64 x;
ModInt() : x{0} {}
ModInt(int n) : x{(n % getMod() + getMod()) % getMod()} {}
ModInt(i64 n) : x{(n % getMod() + getMod()) % getMod()} {}
static i64 Mod;
constexpr static void setMod(i64 _Mod) {
Mod = _Mod;
}
constexpr static i64 getMod() {
return P > 0 ? P : Mod;
}
constexpr ModInt &operator+=(const ModInt &k) & {
x = (x + k.x >= getMod() ? x + k.x - getMod() : x + k.x);
return *this;
}
constexpr ModInt &operator-=(const ModInt &k) & {
x = (x - k.x < 0 ? x - k.x + getMod() : x - k.x);
return *this;
}
constexpr ModInt &operator*=(const ModInt &k) & {
x = 1LL * x * k.x % getMod();
return *this;
}
friend constexpr ModInt operator+(ModInt lhs, const ModInt &rhs) {
return lhs += rhs;
}
friend constexpr ModInt operator-(ModInt lhs, const ModInt &rhs) {
return lhs -= rhs;
}
friend constexpr ModInt operator*(ModInt lhs, const ModInt &rhs) {
return lhs *= rhs;
}
friend constexpr ModInt operator/(ModInt lhs, const ModInt &rhs) {
return lhs /= rhs;
}
constexpr ModInt inv() {
return power(*this, getMod() - 2);
}
constexpr ModInt &operator/=(const ModInt &k) & {
return (*this) *= k.inv();
}
friend constexpr std::istream &operator>>(std::istream &is, ModInt &k) {
i64 val;
is >> val;
k = val;
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const ModInt &k) {
return os << k.x;
}
friend constexpr bool operator==(const ModInt &lhs, const ModInt &rhs) {
return lhs.x == rhs.x;
}
friend constexpr bool operator!=(const ModInt &lhs, const ModInt &rhs) {
return lhs.x != rhs.x;
}
constexpr bool operator!() {
return !x;
}
constexpr ModInt &operator++() & {
return (*this) += 1;
}
constexpr ModInt &operator++(int) & {
ModInt temp = *this;
(*this) += 1;
return temp;
}
constexpr ModInt &operator--() & {
return (*this) -= 1;
}
constexpr ModInt &operator--(int) & {
ModInt temp = *this;
(*this) -= 1;
return temp;
}
} ;
template<>
i64 ModInt<0>::Mod = 1E9 + 7;
constexpr int P = 1E9 + 7;
using Z = ModInt<P>;
struct Comb {
std::vector<Z> _inv, _invfac, _fac;
int n;
Comb() {
n = 0;
_inv.push_back(0);
_invfac.push_back(1);
_fac.push_back(1);
}
void Init(int m) {
if (m <= n) {
return ;
}
_inv.resize(m + 1);
_fac.resize(m + 1);
_invfac.resize(m + 1);
for (int i = n + 1; i <= m; ++i) {
_fac[i] = _fac[i - 1] * i;
}
_invfac[m] = _fac[m].inv();
for (int i = m; i > n; --i) {
_invfac[i - 1] = _invfac[i] * i;
_inv[i] = _invfac[i] * _fac[i - 1];
}
}
Z fac(int m) {
Init(2 * m);
return _fac[m];
}
Z inv(int m) {
Init(2 * m);
return _inv[m];
}
Z invfac(int m) {
Init(2 * m);
return _invfac[m];
}
Z binom(int n, int m) {
if (m < 0 || m > n) {
return 0;
} else {
return fac(n) * invfac(m) * invfac(n - m);
}
}
} comb;
constexpr int N = 3E5 + 5, K = 21;
int n, sz[N], lg[N];
std::vector<int> adj[N];
Z f[N][K], g[N][K], h[N];
Z pack[1 << K][2], roll[1 << K][2];
void dfs(int x, int fa) {
sz[x] = 1;
std::vector<int> sons;
for (auto v : adj[x]) if (v != fa) {
dfs(v, x);
sons.push_back(v);
sz[x] += sz[v];
}
sort(sons.begin(), sons.end(),
[](int x, int y) {
return sz[x] < sz[y];
}
);
if (sons.empty()) {
f[x][0] = g[x][0] = h[x] = 1;
return ;
}
pack[0][0] = 1;
int r = 0;
for (auto v : sons) {
int l = (v == sons.back() ? r + 1 : lg[sz[v]] + 1);
for (int mask = 0; mask < 1 << r; ++mask)
for (int t : {0, 1}) if (pack[mask][t].x) {
for (int i = 0; i < l; ++i) if (mask >> i & 1 ^ 1 && f[v][i].x) {
if (t && i > lg[mask]) {
continue;
}
roll[mask ^ 1 << i][t] += pack[mask][t] * f[v][i];
}
roll[mask][t] += pack[mask][t] * h[v];
if (!t) {
for (int i = lg[mask] + 1; i < l; ++i) if (g[v][i].x) {
roll[mask ^ 1 << i][1] += pack[mask][0] * g[v][i];
}
}
}
r = l;
for (int mask = 0; mask < 1 << r; ++mask) {
for (int t : {0, 1}) {
pack[mask][t] = roll[mask][t];
roll[mask][t] = 0;
}
}
}
for (int i = 0; i <= r; ++i) {
h[x] += pack[(1 << i) - 1][0] + (i ? pack[(1 << i) - 1][1] : 0);
f[x][i] = pack[(1 << i) - 1][0];
}
for (int i = 0; i <= r; ++i) {
for (int j = 0; j < i; ++j) {
g[x][j] += pack[((1 << i) - 1) ^ (1 << j)][0];
if (j + 1 < i) {
g[x][j] += pack[((1 << i) - 1) ^ (1 << j)][1];
}
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
lg[0] = -1;
for (int i = 2; i <= n; ++i) {
lg[i] = lg[i / 2] + 1;
}
for (int i = 1; i < n; ++i) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 0);
std::cout << h[1] << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 172372kb
input:
5 1 2 1 3 1 4 4 5
output:
19
result:
wrong answer 1st lines differ - expected: '21', found: '19'