这就是二项式反演的基本格式
我们现在可以熟练运用二项式反演了
P6478 [NOI Online #2 提高组] 游戏 - 洛谷
我们记 “恰好有 k 次非平局” 的方案数是 \(g(k)\) ,“$ \ge k$ 次非平局” 的方案数是 \(f(k)\),发现这是一个二项式反演的形式。
所以我们可以先把\(f(k)\) dp 求,再反演\(g(k)\)
令 \(f(i,j)\) 表示 i 的子树中出现 \(\ge \space j\) 次非平的方案数
考虑转移:
对于情况1,我们可以:
然后考虑情况2,
我们直接考虑对于点 \(i\) ,仅仅可以和子树中的 异色点 (\(d(i)\))组成关系,所以我们可以,得到推导式:
是不是非常清晰,我们可以发现对于每个 \(g(k)\) ,对 \(f\) 的贡献有:
所以可以套式子:
然后就可以愉快的AC了。
#include <bits/stdc++.h>
#define ll long long
#define fd(i, a, b) for (ll i = a; i >= b; i--)
#define r(i, a) for (ll i = fir[a]; i; i = e[i].nex)
#define file(a) freopen(#a ".in", "r", stdin);freopen(#a ".out", "w", stdout);
#define il inline
#define gc getchar()
#define f(i, a, b) for (ll i = a; i <= b; i++)
using namespace std;
const ll maxn = 5e3 + 10, p = 998244353;
il ll read() {
ll x = 0, f = 1;
char ch = gc;
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = gc;
}
while (ch >= '0' && ch <= '9') x = (x * 10) + (ch ^ 48), ch = gc; /*q;*/
return x * f;
}
vector<ll> e[maxn];
ll f[maxn][maxn];
il void add(ll a, ll b) { e[a].push_back(b); }
bool bel[maxn];
ll g[maxn], n, m;
ll a[maxn], b[maxn], siz[maxn], iv[maxn], ji[maxn];
ll t[maxn];
il void ad(ll &a, ll b) { a = (a + b >= p) ? (a + b) % p : a + b; }
il void ce(ll &a, ll b) { a = (a * b >= p) ? (a * b) % p : a * b; }
il void dfs(ll x, ll fa) {
// cout<<"x="<<x<<" fa="<<fa<<endl;
a[x] = (bel[x] ^ 1), b[x] = (ll)bel[x], siz[x] = 1;
f[x][0] = 1;
f(i, 0, (ll)e[x].size() - 1) {
ll v = e[x][i];
// cout<<v<<endl;
if (v == fa) continue;
dfs(v, x);
f(i, 0, siz[v] + siz[x]) t[i] = 0;
f(i, 0, min(m, siz[x])) {
if (!f[x][i]) continue;
f(j, 0, min(m - i, siz[v])) {
if (!f[v][j]) continue;
ad(t[i + j], f[x][i] * f[v][j] % p);
}
}
f(i, 0, siz[v] + siz[x]) f[x][i] = t[i];
a[x] += a[v], b[x] += b[v], siz[x] += siz[v];
}
ll num = bel[x] ? a[x] : b[x];
// swap(a[x],b[x]);
// cout<<x<<" "<<a[x]<<" "<<b[x]<<" "<<bel[x]<<endl;
// cout<<x<<" ";f(i,0,m) cout<<f[x][i]<<" ";cout<<endl;
fd(i, min(a[x], b[x]), 1) ad(f[x][i], f[x][i - 1] * (num - i + 1) % p);
}
ll c[maxn][maxn];
int main() {
file(a);
ji[0] = 1;
f(i, 1, maxn - 10) ji[i] = ji[i - 1] * i % p;
f(i, 0, maxn - 10) c[i][0] = 1;
f(i, 1, maxn - 10) f(j, 1, i) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % p;
// cout<<c[5][3]<<endl;
n = read(), m = n >> 1;
f(i, 1, n) {
char ch = gc;
while(ch!='0'&&ch!='1') ch=gc;
if (ch == '1') bel[i] = 1;
}
f(i, 2, n) {
ll a = read(), b = read();
add(a, b);
add(b, a);
}
dfs(1, 1);
// f(j,0,m) cout<<f[1][j]<<endl;
f(j, 0, m + 1) ce(f[1][j], ji[m - j]);
f(i, 0, m) {
ll ans = 0;
f(j, i, m) ad(ans,(c[j][i] * (((j - i) & 1) ? p - 1 : 1) % p * f[1][j] % p));
printf("%lld\n", ans);
}
}
转载自: https://www.cnblogs.com/jcyf1987/p/15434919.html