[BZOJ 4517] [SDOI 2016] 排列计数
省选前最后水一发…
SDOI 好像很喜欢数学题？_(:_」∠)_
用 f(n) 表示 1∼n 的错排方案数（满足 Ai≠i,∀i 的排列数），容易看出 Ans = f(n-m) \binom{n}{m}。
其中有 f(n) = \sum_{i=0}^{n} (-1)^i \binom{n}{i} (n-i)!。具体证明可以 Orz vfk
接下来是喜闻乐见的化简时间
\begin{align} Ans & = f(n-m) \binom{n}{m} \\ & = \sum_{i=0}^{n-m} (-1)^i \binom{n-m}{i} (n-m-i)! \cdot \binom{n}{m} \\ & = \sum_{i=0}^{n-m} (-1)^i \frac{(n-m)!}{i! (n-m-i)!} \cdot (n-m-i)! \cdot \frac{n!}{m! (n-m)!} \\ & = \sum_{i=0}^{n-m} (-1)^i \frac{n!}{m! \cdot i!} \\ & = \frac{n!}{m!} \cdot \sum_{i=0}^{n-m} \frac{(-1)^i}{i!} \end{align}
惊奇地发现（一点也不）所有的阶乘以及除法逆元都可以 O(n \log n) 预处理（不会 O(n) _(:_」∠)_）。。然后又惊奇地发现 \sum_{i=0}^{n-m} \frac{(-1)^i}{i!} 可以通过 O(n) 预处理计算部分和。。于是变成了 O(n \log n)-O(1) 目测 60s 不会被卡常数？= =
然后就愉快地解决了（难得不靠找规律做出一道数学题 QwQ）时间复杂度 O(n \log n + t)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | /************************************************************** Problem: 4517 User: cyand1317 Language: C Result: Accepted Time:31724 ms Memory:24192 kb****************************************************************/#include <stdio.h>#define MAXN 1000004#define MODULUS 1000000007typedef long long int64; int n, m; // f(n) = # of permutations P of length n// where not exists such i that P[i] = i// F(n) = sigma[i = 0 to n] f(i) * C(n,i)// = n! // Binomial inversion// f(n) = sigma[i = 0 to n] (-1)^i * C(n,i) * (n-i)!// Ans = f(n-m) * C(n,m)// = sigma[i = 0 to n-m] (-1)^i * C(n-m,i) * (n-m-i)! * C(n,m) // C(n,m) * C(n-m,i) * (n-m-i)!// = n!/(m! (n-m)!) * (n-m)!/(i! (n-m-i)!) * (n-m-i)!// = n!/(m! i! (n-m-i)!) * (n-m-i)!// = n!/(m! i!)// Ans = (sigma[i = 0 to n-m] (-1)^i / i!) * n!/m! int64 fact[MAXN], fact_inv[MAXN], pfxsum[MAXN];int64 fpow(int64 base, int exp){ int64 ans = 1; while (exp) { if (exp & 1) ans = ans * base % MODULUS; base = base * base % MODULUS; exp >>= 1; } return ans;}void preprocess(){ int i; fact[0] = fact[1] = 1; fact_inv[0] = fact_inv[1] = 1; pfxsum[0] = 1; pfxsum[1] = 0; for (i = 2; i < MAXN; ++i) { fact[i] = fact[i - 1] * i % MODULUS; fact_inv[i] = fpow(fact[i], MODULUS - 2); if (i & 1) pfxsum[i] = (pfxsum[i - 1] - fact_inv[i] + MODULUS) % MODULUS; else pfxsum[i] = (pfxsum[i - 1] + fact_inv[i]) % MODULUS; }}int64 nCr(int n, int m){ return (fact[n] * fact_inv[m]) % MODULUS * fact_inv[n - m] % MODULUS;}int64 calc(int n, int m){ return n < m ? 0 : pfxsum[n - m] * fact[n] % MODULUS * fact_inv[m] % MODULUS;} int main(){ preprocess(); int t; scanf("%d", &t); do { scanf("%d%d", &n, &m); printf("%lld\n", calc(n, m)); } while (--t); return 0;} |
貌似 O(n \log n) 跑得挺慢的？= =
之前 WA 了一发。。原因是计算部分和的时候没有 mod MODULUS。。（果然还是弱 省选药丸药丸啊←_←）
总之省选加油 Ganbarimasu~
评论 (0)