【PKUWC2018】随机游走

2018-12-25 20:45:55

### 题目描述

$1\leq n\leq 18$

$1\leq Q\leq 5000$

$1\leq k\leq n$

### 题解

$E(\max(S)) = \sum_{T \subseteq S} (-1)^{\mid T \mid + 1}E(\min(T))$

$$f_u=1+\frac{1}{deg_u}\sum_{u \to v} f_v$$

$$\sum_{T \subseteq S} (-1)^{\mid T \mid + 1} g_{T}$$

### 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 20, mod = 998244353;

vector<int> g[N];

int n, q, x; ll ans[1 << N], deginv[N];

ll pw(ll a, ll b) {
ll r = 1;
for( ; b ; b >>= 1, a = a * a % mod)
if(b & 1)
r = r * a % mod;
return r;
}

struct T {
ll a, b;
// f[u] = a*f[fa]+b
T(ll a = 0, ll b = 0): a(a), b(b) {}
T operator + (T t) {
return (T) { (a + t.a) % mod, (b + t.b) % mod };
}
} f[1 << N][N];

void dfs(int u, int fa, T *f, int S) {
if(S & (1 << (u - 1))) return ;
T sum;
for(int v: g[u]) {
if(v == fa) continue;
dfs(v, u, f, S);
sum = sum + f[v];
}
ll tmp = pw(1 - deginv[u] * sum.a % mod, mod - 2);
f[u].a = deginv[u] * tmp % mod;
f[u].b = (1 + sum.b * deginv[u] % mod) * tmp % mod;
}

int cnt[1 << 20];

int main() {
ios :: sync_with_stdio(0);
cin >> n >> q >> x;
for(int i = 1, u, v ; i < n ; ++ i)
cin >> u >> v,
g[u].push_back(v),
g[v].push_back(u);
for(int i = 1 ; i <= n ; ++ i)
deginv[i] = pw(g[i].size(), mod - 2);
for(int s = 0 ; s < (1 << n) ; ++ s)
cnt[s] = cnt[s >> 1] + (s & 1);
for(int s = 1 ; s < (1 << n) ; ++ s)
dfs(x, 0, f[s], s),
ans[s] = (cnt[s] & 1 ? 1 : -1) * f[s][x].b % mod;
for(int i = 1 ; i <= n ; ++ i)
for(int s = 0 ; s < (1 << n) ; ++ s)
if(s & (1 << (i - 1)))
(ans[s] += ans[s - (1 << (i - 1))]) %= mod;
for(int i = 1 ; i <= q ; ++ i) {
int k, x = 0, y; cin >> k;
for(int j = 1 ; j <= k ; ++ j)
cin >> y,
x |= 1 << (y - 1);
cout << (ans[x] % mod + mod) % mod << endl;
}
}
• star
首页