CF1516E. Baby Ehab Plays with Permutations

Solution

因為組合水平不行所以只弄出來一個$O(k^4)$的做法（雖然隨便改改可能就$O(k^3\log k)$或者$O(k^3)$了）而且因為沒想清楚而自閉了很久，從而導致摸yu時間被閹割。

首先大概有個顯然的性質：設一個任意的操作方案形成的最終序列為$a_1,a_2...a_n$，把$i$和$a_i$連邊，會形成若干個環，有個顯然的結論是到達該狀態的最少操作次數是所有環長度減一的和，而一個任意方案可以表示為最少操作方案加上若干無用操作，顯然無用操作個數為偶數（由逆序對個數奇偶性可得），因此我們只需要計算最少$i$步能到達的狀態個數$An{s}_i$，再讓$An{s}_i^{\prime }={\sum }_{k=0}^{?\frac{i}{2}?}An{s}_{i?2k}$即為最終的答案。

因此我們要對每一個$i$，求出最少$i$步能到達的狀態個數。

這就相當于取若干個環，使得所有環的長度減一的和為$i$，也就類似于做一個完全背包，取$j$個數形成環的方案數就是環排列個數$(j?1)!$，因此枚舉枚舉環長$i$，枚舉該種環的個數$p$，再枚舉環包含的點數$j$和操作次數$k$，可得：
$$f_{j,k}=\sum _p{f}_{j?ip,k?(i?1)p}(i?1{)}^p(\genfrac{}{}{0ex}{}{j}{ip}\left)\prod _{t=0}^{p?1}\right(\genfrac{}{}{0ex}{}{ip?it?1}{i?1})$$

$$An{s}_i=\sum _j{f}_{j,i}\left(\genfrac{}{}{0ex}{}{n}{j}\right)$$

預處理一些東西即可計算。

Code

int fac[405], Inv[405], C[405][405], f[405][205], Ans[405], tmp[405][205], inv[405], Mul[405]; int quick_pow(int x, int y) {int ret = 1;for (; y ; y >>= 1) {if (y & 1) ret = 1ll * ret * x % mods;x = 1ll * x * x % mods;}return ret; } signed main() { #ifndef ONLINE_JUDGEfreopen("a.in", "r", stdin); #endifint n, k;read(n), read(k);fac[0] = inv[0] = Inv[0] = 1;for (int i = 1; i <= k + k ; ++ i) Inv[i] = quick_pow(i, mods - 2);for (int i = 1; i <= k + k ; ++ i) fac[i] = 1ll * fac[i - 1] * i % mods, inv[i] = quick_pow(fac[i], mods - 2);for (int i = 0; i <= k + k ; ++ i) C[i][i] = C[i][0] = 1;for (int i = 1; i <= k + k ; ++ i)for (int j = 1; j < i ; ++ j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mods;f[0][0] = 1;for (int i = 2; i <= min(n, k + 1) ; ++ i) {for (int j = 0; j <= k + k ; ++ j)for (int t = 0; t <= k ; ++ t) tmp[j][t] = f[j][t], f[j][t] = 0;for (int j = 0; j <= k + k ; ++ j) Mul[j] = 1;for (int p = 0, mul = 1; p <= k ; ++ p) {for (int j = i * p ; j <= k + k ; ++ j) {for (int t = (i - 1) * p ; t <= k ; ++ t)f[j][t] = (f[j][t] + 1ll * tmp[j - i * p][t - (i - 1) * p] * Mul[i * p] % mods * mul % mods * C[j][i * p] % mods) % mods;} for (int j = k + k; j >= 0 ; -- j)if (j >= i) Mul[j] = 1ll * Mul[j - i] * C[j - 1][i - 1] % mods;else Mul[j] = 0;mul = 1ll * mul * fac[i - 1] % mods;}}for (int i = 0, mul = 1; i <= min(k + k, n) ; ++ i) {for (int j = 0; j <= k ; ++ j) Ans[j] = (Ans[j] + 1ll * f[i][j] * mul % mods * inv[i] % mods) % mods;mul = 1ll * mul * (n - i) % mods;}for (int i = 2; i <= k ; ++ i) Ans[i] = (Ans[i] + Ans[i - 2]) % mods;for (int i = 1; i <= k ; ++ i) print(Ans[i]), putc(' ');return 0; }

總結

以上是生活随笔為你收集整理的CF1516E. Baby Ehab Plays with Permutations(组合数学)的全部內容，希望文章能夠幫你解決所遇到的問題。

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