Article From:https://www.cnblogs.com/zjp-shadow/p/9123748.html

Written in front of this question: some of the questions on the Internet do not mention how the coefficient is pushed to TAT.
(Not everyone is so amazing. I’m good at cooking.
AndLOJ The code is all the same. The coefficient can’t see what it is, TAT.
Later, I did HDU 4035. Finally, I would like to thank brother eagle for his help!!!

  • Theme: #2542. “PKUWC 2018” random walk

  • The answer:

The original model seems to be that I don’t have that violent DP… Is the expectation of the point that the direct statistical point is last passed, that is, the expectation of the point where the point is concentrated to the maximum of all the point steps. (perhaps the Gauss elimination of the column equation may seem to be no point)

But we think about transforming it (because the original CLJ question is also asking for this).Maximum inversion (MinMax repulsion) The expectation of converting to a minimum can be calculated.

Maximum inversion (also calledMinMaxRepulsion ) :

\[\displaystyle \max\{S\}=\sum_{T\subseteq S}(-1)^{|T|-1}\min\{T\}\]

among\(S\) It’s a complete set,\(T\) It is a subset of it, and there is this magic theorem.

Proof (from DOFY’s big blog):

Set maximum value\(x \in S\) ,Then structural mapping\(f(T) \to x \in T~?~T−x:T+x\) , That is, there is\(x\) Get rid of it, don’t add it. So when\(T\) Not to be empty and\({x}\) At the time,\(T\) and\(f(T)\) Because there is only one difference, the minimum value is the same, and the size of the set is only a difference.\(1\) ,It cancels (one mapping) because the empty set does not have a minimum value, so the last thing is left.\(\{x\}\) Contribution.

Then with this, we only need to seek the least number of points through the point set.

Suppose we have a set at the moment\(S\) , We use it\(f(u)\) Represent from\(u\) Start, first visit\(S\) The expected step of the middle node.

So we have some obvious ways:

  1. \(u \in S:\)

    \[f(u)=0\]

  2. \(u \not \in S:\)

    order\(d[u]\) by\(u\) The number of degrees on a tree (even the number of edges),\(\mathrm{ch}[u]\) by\(u\) Son,\(\mathrm{fa}[u]\) by\(u\) Father.

    \[\displaystyle f(u)=[f(\mathrm{fa}[u])+1+\sum (f(\mathrm{ch[u]})+1)] \times \frac{1}{d[u]}\]

    \[\displaystyle =\frac{1}{d[u]}f(\mathrm{fa}[u])+\frac{1}{d[u]}\sum f(\mathrm{ch}[u])+1\]

It is easy to see that the answer to each point can only keep its father’s answer and a constant contribution.

( It can be understood that everything can be pushed back because that is not.\(u \in S\) The contribution of the leaves is only related to the father.

Suppose that it is\[f(u)=A_uf(\mathrm{fa}[u])+B_u\] as well as\(v = \mathrm{ch}[u]\)

So there is\[\displaystyle \sum f(\mathrm{ch[u]})=\sum f(v) = \sum(A_v f_u + B_v)\]

And that’s the return of this

\[\displaystyle (1-\frac{\sum A_v}{d[u]}) f(u) = \frac{1}{d[u]}f(\mathrm{fa}[u])+(1+\frac{B_v}{d[u]})\]

In addition to the past, you can get every recursion\(A,B\) Qwq

And then do it casually, complexity\(O((n+Q) \cdot 2^n)\) … In fact, the complexity behind is for each query enumeration subset.

In preprocessing, the complexity becomes\(O(n\cdot 2^n + 3^n)\) La

It seems to be easy to get off?

  • Code:
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {
    int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * fh;
}

void File() {
#ifdef zjp_shadow
    freopen ("2542.in", "r", stdin);
    freopen ("2542.out", "w", stdout);
#endif
}

typedef long long ll;
const int Mod = 998244353;

inline ll fpm(ll x, int power) {
    ll res = 1; x = (x % Mod + Mod) % Mod;
    for (; power; power >>= 1, (x *= x) %= Mod)
        if (power & 1) (res *= x) %= Mod;
    return res;
}

const int N = 20; 
int n, Q, rt, d[N];
vector<int> G[N]; ll A[N], B[N], invd[N];

void Dp(int u, int fa, int S) {
    if ((1 << (u - 1)) & S) { A[u] = B[u] = 0; return ; }

    ll totA = 0, totB = 0;
    for (int v : G[u]) if (v ^ fa)
        Dp(v, u, S), totA += A[v], totB += B[v];
    totA %= Mod, totB %= Mod;

    ll coef = fpm(Mod + 1 - totA * invd[u], Mod - 2);
    A[u] = invd[u] * coef % Mod;
    B[u] = (1 + totB * invd[u] % Mod) * coef % Mod;
}

ll Minv[1 << 18]; int bit[1 << 18];

int main () {
    File();

    n = read(); Q = read(); rt = read();
    For (i, 1, n - 1) {
        int u = read(), v = read();
        G[u].push_back(v); G[v].push_back(u);
        ++ d[u]; ++ d[v];
    }
    For (i, 1, n) invd[i] = fpm(d[i], Mod - 2);

    int maxsta = (1 << n) - 1;
    For (i, 0, maxsta) {
        Dp(rt, 0, i);
        Minv[i] = B[rt];
        bit[i] = bit[i >> 1] + (i & 1);
    }

    while (Q --) {
        int k = read(), sta = 0;
        while (k --) sta |= (1 << (read() - 1));
        ll ans = 0;
        for (int i = sta; i; i = (i - 1) & sta)
            ans += (bit[i] & 1 ? 1 : -1) * Minv[i];
        ans = (ans % Mod + Mod) % Mod;
        printf ("%lld\n", ans);
    }

    return 0;
}

Similar Posts:

Leave a Reply

Your email address will not be published. Required fields are marked *