P6478 [NOI Online # 2 提高組] 游戲
熾熱體驗
二項式反演食用指南
\[f(n)=\sum_{i=n}^m( _i ^n)g(i)?g(n)=∑_{i=n}^m(?1)^{i?n}(_i^n)f(i) \]這就是二項式反演的基本格式
\[f(n)=\sum\limits_{i=n}^m{i\choose n}\sum\limits_{j=i}^m(-1)^{j-i}{j\choose i}f(j) $$\]=\sum\limits_{i=n}m\sum\limits_{j=i}m(-1)^{j-i}{i\choose n}{j\choose i}f(j)
\[\]=\sum\limits_{j=n}mf(j)\sum\limits_{i=n}j(-1)^{j-i}{i\choose n}{j\choose i}
\[\]=\sum\limits_{j=n}^m{j\choose n}f(j)\sum\limits_{i=n}^j{j-n\choose j-i}(-1)^{j-i}
\[\]=\sum\limits_{j=n}^m{j\choose n}f(j)\sum\limits_{t=0}^{j-n}{j-n\choose t}(-1){t}1{j-n-t}
\[\]=\sum\limits_{j=n}^m{j\choose n}f(j)(1-1)^{j-n}
\[\]=\sum\limits_{j=n}^m{j\choose n}f(j)[j=n]
\[\]={n\choose n}f(n)
\[\]=f(n)
\[ ~~我們現在可以熟練運用二項式反演了~~ ## 題目決議： **[P6478 [NOI Online #2 提高組] 游戲 - 洛谷](https://www.luogu.com.cn/problem/P6478)** 我們記 “恰好有 k 次非平局” 的方案數是 $g(k)$ ，“$ \ge k$ 次非平局” 的方案數是 $f(k)$，發現這是一個二項式反演的形式， 所以我們可以先把$f(k)$ dp 求，再反演$g(k)$ ### dp設計： 令 $f(i,j)$ 表示 i 的子樹中出現 $\ge \space j$ 次非平的方案數 考慮轉移： 1. 子樹內轉移 2. 考慮i點本身的貢獻 對于情況1，我們可以： \]f(i,j)=\prod_{\sum_{k \in son_i}j_k =j}f(k,j_k)
\[ 然后考慮情況2， 我們直接考慮對于點 $i$ ，僅僅可以和子樹中的 **異色點** ($d(i)$)組成關系，所以我們可以，得到推導式: \]f(i,j) \lhd \sum_{k=son_i} f (k,j-1) \times d(i-j)
\[ ### 二項式反演： 是不是非常清晰，我們可以發現對于每個 $g(k)$ ，對 $f$ 的貢獻有: \]g(k) \lhd f(i (\le k) ) \times C{_k ^i}
\[ 所以可以套式子: \]f(n)=\sum_{i=n}^m( _i n)g(i)?g(n)=∑_{i=n}m(?1){i?n}(_in)f(i)
\[ 然后就可以愉快的AC了， ```c #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.uj5u.com/houduan/329969.html
標籤：C++
下一篇：Golang通脈之指標