我的計數還是太差了……

這道題現在知道三種做法。

1. 直接DP

首先顯然需要min-max容斥（不知道請百度），不然很難算。

顯然對于大小相同的集合答案一樣，問題轉化為求 \(f_c\) 即 \(c\) 只鴿子最早有一只搞滿 \(k\) 個玉米的期望。

然后我就有了一種 \(f_{c,k}\) 表示 \(c\) 只，搞滿 \(k\) 顆，直接DP的想法，不知道能不能做。

這道題考慮期望即枚舉步數乘上概率 \(\sum_s s \times p(s)\) 比較難搞，但是因為是 \(s\) 次，所以不如考慮一個經典的trick，考慮小于 \(s\) 的，全部貢獻。

那么原式 \(\sum_s s \times p(s) = \sum_s p'(s)\)，其中 \(p'(s)\) 為大于 \(s\) 步的概率。

考慮 \(p'(s)\)，大于等于 \(s\) 步即 \(s\) 步以內里面沒有一個飽，枚舉里面吃了幾個。那么記 \(g_{c,s}\) 為銩了 \(s\) 個，有 \(c\) 只，沒有一個飽的概率。

\[p'(s) = \sum_i \binom{s}{i} g_{c,i} \left( \frac{n - c}{n} \right)^{s - i}\]

但是帶入計算答案的式子，計算一個 \(c\) 復雜度是 \(O(n^2k^2)\) 的，甚至還要算 \(n\) 個 \(c\)。

所以先考慮優化這個式子。第一個想法肯定是卷積。

帶上計算答案的式子，對于一個 \(c\)，有

\[f_c = \sum_{s = 0} g'(s) = \sum_{s = 0} \sum_i \binom{s}{i} g_{c,i} \left( \frac{n - c}{n} \right)^{s - i}\]

顯然可以換元，枚舉 \((s - i) + (i) = s\)，得到

\[f_c = \sum_i g_{c,i} \sum_j \binom{i + j}{i} \left( \frac{n - c}{n} \right)^{j}\]

顯然后者可以通過一些方法算到 \(O(\log n)\) 或者更低。即 \(x = \frac{n - c}{n}\)，然后就變成了 \(\left( \frac{1}{1-x} \right)^C\) 這一類的式子。

那么只要能快速計算 \(g_{c,s}\) 就能快速得到 \(f\)。

顯然 \(g\) 可以通過不斷加入一個點來轉移，枚舉多少步，就是一個組合數卷積（其實EGF可以推的啊）。

\[g_{c,s} = \sum_i \binom{s}{i} g_{c - 1, s - i} \left( \frac{1}{n} \right)^{i}\]

顯然表示成 EGF 可以暴力卷積。

復雜度 \(O(n^2 k (\log n + \log k))\)

目前懶得寫了。

2. 更好的做法

一個截然不同的做法，直接對題目做。如果把一個鴿子得到的前 \(k\) 個都當做有效的，那么有效的只有 \(nk\) 個。

所以枚舉每次有效插入之前多少個飽了的，記這個序列為 \(A\)，那么，每要得到一個有效的，期望步數就是加上 \(\frac{n}{rest}\)。

但是得到了這個玉米我們怎么知道哪個鴿子會不會飽啊

所以假設玉米扔到了一個等待序列中，等著被安排，直到我們要迅速撐飽一個鴿子的時候組合數取一下玉米，再在剩下的鴿子里欽定一個。注意最后一個玉米是已經確定好的，所以只要選 \(K - 1\) 個。

如果這樣做會出問題，在我們搞那個等待序列的時候，就已經多算貢獻了。注意到我們的期望步數是選可選集合中的一個，因此那個玉米自帶了從屬的鴿子，自然會多算。所以要乘上一個 \(\frac{1}{rest}\) 抵消掉這個貢獻，以實現加入等待序列。

于是考慮轉移，顯然狀態里記錄一下已經放的玉米和已經飽的鴿子個數就可以實現 \(O(1)\) 轉移，只要同時記錄方案數和期望即可。

復雜度 \(O(n^2k)\)。

在奇怪的地方上調了好久。拿階乘逆來當普通的逆了……

#include <bits/stdc++.h>const int mod = 998244353; typedef long long LL; int mul(int a, int b) { return (LL) a * b % mod; } void reduce(int & x) { x += x >> 31 & mod; } const int MAXN = 50010; int fac[MAXN], inv[MAXN]; int C(int a, int b) { return a < b ? 0 : (LL) fac[a] * inv[b] % mod * inv[a - b] % mod; }int f[51][MAXN], g[51][MAXN]; int n, K; int main() {fac[0] = fac[1] = inv[0] = inv[1] = 1;for (int i = 2; i != MAXN; ++i) {fac[i] = mul(fac[i - 1], i);inv[i] = mul(inv[mod % i], mod - mod / i);}for (int i = 2; i != MAXN; ++i)inv[i] = mul(inv[i - 1], inv[i]);std::cin >> n >> K; const int T = n * K;f[0][0] = 1;for (int j = 0; j < T; ++j)for (int i = 0; i < n; ++i) if (f[i][j]) {int c1 = mul(inv[n - i], fac[n - i - 1]), c2 = mul(c1, n);reduce(f[i][j + 1] += mul(f[i][j], c1) - mod);reduce(g[i][j + 1] += ((LL) f[i][j] * c2 % mod + g[i][j]) * c1 % mod - mod);c1 = mul(c1, C(j - i * K, K - 1));reduce(f[i + 1][j + 1] += mul(f[i][j], c1) - mod);reduce(g[i + 1][j + 1] += ((LL) f[i][j] * c2 % mod + g[i][j]) * c1 % mod - mod);}std::cout << mul(g[n][T], fac[n]) << std::endl;return 0; }

3. 最通用的做法

還是min-max容斥。但是求下面的期望我們可以直接生成函數。

我們記錄下放進欽定的 \(c\) 個鴿子，記有效的玉米為丟個這幾個欽定的鴿子的玉米。有效玉米構成了一個序列。顯然它們取到 \(s\) 個玉米的期望步數為 \(\frac{sn}{c}\)

對一個長度，實際上只需要求出有貢獻的方案數，以及總方案數。總方案數就是 \(\frac{1}{c^s}\)，即這個序列所有可能。

對于有貢獻的，可以采用指數型生成函數。我們欽定第一個吃飽的是 \(1\)，然后最后方案數只要乘上一個 \(c\)。

因為最后一顆是確定的，所以只需要知道第一只吃了 \(k - 1\) 個，其他的小于等于 \(k - 1\) 個的方案數。因為是排列，所以使用 EGF

\[ \frac{x^{k - 1}}{(k - 1)!} \left(1 + x + \frac{x^2}{2!} + \dots + \frac{x^{k - 1}}{(k - 1)!} \right)^{c - 1}\]

不阻止你們使用Poly Ln EXP，復雜度 \(O(n^2 k (\log n + \log k))\) 。但是為了優美，所以考慮使用推式子技巧。

左邊那項乘上特別簡單，那么只考慮右邊系數的計算。看樣子不太好做，所以直接上萬能的求導積分等操作，可以方便的求出遞推式。

\[ \begin{align} & \frac{\mathrmze8trgl8bvbq \left(1 + x + \frac{x^2}{2!} + \dots + \frac{x^{k}}{k!} \right)^c}{\mathrm{dx}} \\ = & c \times \left(1 + x + \frac{x^2}{2!} + \dots + \frac{x^{k}}{k!} \right)^{c - 1} \times \left(1 + x + \frac{x^2}{2!} + \dots + \frac{x^{k - 1}}{(k - 1)!} \right) \end{align} \]

然后積分一下。但是里面求的是一個卷積，那樣的話還是得用FFT。

當然可以優化了。定義

\[f(x) = \left(1 + x + \frac{x^2}{2!} + \dots + \frac{x^{k}}{k!} \right)\]

注意到 \(f'(x) = f(x) - \frac{x^{k}}{k!}\)，則

\[ \begin{align} & \frac{\mathrmze8trgl8bvbq f^c(x)}{\mathrm{dx}} \\ = & c f^{c-1}(x) \times (f(x) - \frac{x^{k}}{k!}) \\ = & c f^c(x) - \frac{x^{k}}{k!} f^{c-1}(x) \end{align} \]

對應一下系數，因為積分了，所以 \(x^{n - 1}\) 貢獻到 \(x^{n}\)，于是有了一個遞推式，顯然可以 \(O(1)\) 求出一項。

再結合上面講的，就 \(O(n^2 k)\) 過了此題。

轉載于:https://www.cnblogs.com/daklqw/p/11592740.html

總結

以上是生活随笔為你收集整理的【集训队作业2018】喂鸽子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。