QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#534127#7607. The Doubling Game 2PoetryWA 0ms172372kbC++236.2kb2024-08-26 21:01:532024-08-26 21:01:54

Judging History

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

  • [2024-08-26 21:01:54]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:172372kb
  • [2024-08-26 21:01:53]
  • 提交

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';
}

详细

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'