空间链接制作网站,鹤壁市做网站,wordpress留言快速审核,有限公司和公司哪个好CF1516E. Baby Ehab Plays with Permutations
Solution
因为组合水平不行所以只弄出来一个O(k4)O(k^4)O(k4)的做法#xff08;虽然随便改改可能就O(k3logk)O(k^3\log k)O(k3logk)或者O(k3)O(k^3)O(k3)了#xff09;而且因为没想清楚而自闭了很久#xff0c;从而导致摸yu…CF1516E. Baby Ehab Plays with Permutations
Solution
因为组合水平不行所以只弄出来一个O(k4)O(k^4)O(k4)的做法虽然随便改改可能就O(k3logk)O(k^3\log k)O(k3logk)或者O(k3)O(k^3)O(k3)了而且因为没想清楚而自闭了很久从而导致摸yu时间被阉割。
首先大概有个显然的性质设一个任意的操作方案形成的最终序列为a1,a2...ana_1,a_2...a_na1,a2...an把iii和aia_iai连边会形成若干个环有个显然的结论是到达该状态的最少操作次数是所有环长度减一的和而一个任意方案可以表示为最少操作方案加上若干无用操作显然无用操作个数为偶数由逆序对个数奇偶性可得因此我们只需要计算最少iii步能到达的状态个数AnsiAns_iAnsi再让Ansi′∑k0⌊i2⌋Ansi−2kAns_i\sum_{k0}^{\lfloor\frac{i}{2}\rfloor}Ans_{i-2k}Ansi′∑k0⌊2i⌋Ansi−2k即为最终的答案。
因此我们要对每一个iii求出最少iii步能到达的状态个数。
这就相当于取若干个环使得所有环的长度减一的和为iii也就类似于做一个完全背包取jjj个数形成环的方案数就是环排列个数(j−1)!(j-1)!(j−1)!因此枚举枚举环长iii枚举该种环的个数ppp再枚举环包含的点数jjj和操作次数kkk可得 fj,k∑pfj−ip,k−(i−1)p(i−1)p(jip)∏t0p−1(ip−it−1i−1)f_{j,k}\sum_{p}f_{j-ip,k-(i-1)p} (i-1)^p\binom{j}{ip}\prod_{t0}^{p-1}\binom{ip-it-1}{i-1} fj,kp∑fj−ip,k−(i−1)p(i−1)p(ipj)t0∏p−1(i−1ip−it−1)
Ansi∑jfj,i(nj)Ans_{i} \sum_{j} f_{j,i}\binom{n}{j} Ansij∑fj,i(jn)
预处理一些东西即可计算。
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;
}
