首页 > 代码库 > [BestCoder Round#26] Apple 【组合数学】
[BestCoder Round#26] Apple 【组合数学】
题目链接：HDOJ - 5160
题目分析
第一眼看上去，要求统计所有不同排列对答案的贡献。嗯...完全没有想法。
但是，如果我们对每个数字单独考虑，计算这个数字在总答案中的贡献，就容易多了。
对于一个数字 ai ，有 ni 个 。比它大的数字有 p 个，比它小的数字有 q 个。所有的数字一共有 N 个。
首先，比它小的数字对它不会造成影响，所以我们只要考虑它和比它大的数字。那么我们就在 N 个位置中，选 (ni + p) 个位置，给它和比它大的数字。
然后比它大的数字有 x1 种排列，比它小的数字有 x2 种排列。这个如何来求呢？这是多重集排列。
多重集排列，对于一个多重集 A={a1*n1, a2*n2, a3*n3, ak*nk} 。排列数为 Sum(n1...nk)!/(n1!n2!n3!...nk!)
那么 ai 有多少个会被记入答案呢？我们枚举每种情况：有 ni 个记入答案, (ni-1) 个, (ni-2)个 .... 1 个。
如果有 k 个 ai 无法记入答案，说明有比它们大的数在他们前面，也就是说他们被插到了 p 个比他们大的数后面或之间。这 p 个数后面一共有 p 个位置，每个位置都可以插入任意个 ai ，这种情况数为 C(k + p - 1, k) （相当于向 p 个箱子里分配 k 个球，隔板法）。
那么 ai 对答案的贡献就为 C(N, ni + p) * x1 * x2 * sigma((ni - k) * C(k + p - 1, k)) (0 <= k < ni) * ai 。
Warning!
出现的错误： % 的优先级比 + 高！如果这样 Ans = Ans + temp % Mod 。Ans 是会爆掉的！！应该是 Ans = (Ans + Temp) % Mod 。
昨天晚上因为这个错误debug了3hours!!!!!!
代码
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MaxN = 100000 + 15; typedef long long LL;const LL Mod = 1000000007ll;int T, n, Top;LL Ans;LL A[MaxN], f[MaxN], g[MaxN], Sum[MaxN], NSum[MaxN], Fac[MaxN], NY_Fac[MaxN];struct ES_Num{ LL Cnt, Num; ES_Num() {} ES_Num(LL a, LL b) { Num = a; Cnt = b; }} ES[MaxN];LL Pow(LL a, LL b) { LL f, ret; f = a; ret = 1ll; while (b) { if (b & 1) { ret *= f; ret %= Mod; } b >>= 1; f *= f; f %= Mod; } return ret;}void Init() { int Max_Num = 100000 + 5; Fac[0] = 1; for (int i = 1; i <= Max_Num; ++i) Fac[i] = Fac[i - 1] * i % Mod; for (int i = 0; i <= Max_Num; ++i) NY_Fac[i] = Pow(Fac[i], Mod - 2);}LL C(LL a, LL b) { if (b == 0) return 1; if (a < b) return 0; LL ret; ret = Fac[a]; ret = ret * NY_Fac[a - b] % Mod; ret = ret * NY_Fac[b] % Mod; return ret;}int main() { Init(); scanf("%d", &T); for (int Case = 1; Case <= T; ++Case) { scanf("%d", &n); Ans = 0; for (int i = 1; i <= n; ++i) scanf("%d", &A[i]); sort(A + 1, A + n + 1); Top = 0; for (int i = 1; i <= n; ++i) { if (i != 1 && A[i] == A[i - 1]) ++(ES[Top].Cnt); else ES[++Top] = ES_Num((LL)A[i], 1); } Sum[0] = 0; for (int i = 1; i <= Top; ++i) Sum[i] = Sum[i - 1] + ES[i].Cnt; NSum[Top + 1] = 0; for (int i = Top; i >= 1; --i) NSum[i] = NSum[i + 1] + ES[i].Cnt; LL t = 1; f[0] = 1; for (int i = 1; i <= Top; ++i) { t = t * Fac[Sum[i]] % Mod * NY_Fac[ES[i].Cnt] % Mod; f[i] = t; t = t * NY_Fac[Sum[i]] % Mod; } t = 1; g[Top + 1] = 1; for (int i = Top; i >= 1; --i) { t = t * Fac[NSum[i]] % Mod * NY_Fac[ES[i].Cnt] % Mod; g[i] = t; t = t * NY_Fac[NSum[i]] % Mod; } LL x, y; for (int i = 1; i <= Top; ++i) { x = 0; for (int j = 0; j < ES[i].Cnt; ++j) { y = (ES[i].Cnt - j) * C(NSum[i + 1] + j - 1, j) % Mod; x = (x + y) % Mod; } x = x * ES[i].Num % Mod; x = x * f[i - 1] % Mod; x = x * g[i + 1] % Mod; x = x * C(NSum[1], NSum[i]) % Mod; Ans = (Ans + x) % Mod; } printf("Case #%d: %d\n", Case, (int)Ans); } return 0;}
[BestCoder Round#26] Apple 【组合数学】