B|B - Average Gym - 101161B 组合数学 B-AverageGym-101161B组合数学

http://codeforces.com/gym/101161/attachments
今天被卡常了，其实是自己对组合数技巧研究的不够。
如果是n, m <= 1e5的，然后取模是质数，那么可以用费马小定理。
如果n, m都比较小，那么其实是直接杨辉三角。不用逆元那些。
这题的思路是，枚举每一一个ave，然后总和就是n * ave
【B|B - Average Gym - 101161B 组合数学】相当于方程x1 + x2 + .... + xn = n * ave中，在0 <= x[i] <= full的情况下，不同解的个数中，使得x[i] == ave的个数。每有一个x[i] == ave
ans++
首先x1 + x2 + ..... + xn = n * ave在0 <= x[i] <= full有多少个不同的解，可以容斥出来，这里就不说了，复杂度O(n)
可以看看这个，http://www.cnblogs.com/liuweimingcprogram/p/6091396.html
然后怎么统计有多少个ans
考虑每一个的贡献，因为每个人的贡献是独立的，
如果x[1] == ave，有多少种情况？就是x2 + x3 + ..... + xn = ave * n - ave的合法解的个数种。
x[2] == ave同理，所以ans += n * 合法总数。
就比如ave = 1，序列1、1、1中，贡献是3，其中x1 = 1的时候，x2 = x3 = 1一种，然后x2 = 1, x1 = x3 = 1又是一种。

文章图片

文章图片

#include #include #include #include #include #include #include #include #include #include #include #include #define X first #define Y second #define lson T[rt].l #define rson T[rt].r #define clr(u,v); memset(u,v,sizeof(u)); #define in() freopen("data.txt","r",stdin); #define out() freopen("ans","w",stdout); #define Clear(Q); while (!Q.empty()) Q.pop(); #define pb push_backusing namespace std; typedef long long LL; typedef pair pii; const int maxn = 1e6 + 20; LL C[14000 + 2][60 + 2]; const int MOD = 1e9 + 7; LL calc(int n, int en, int sum) { if (sum < 0) return 0; LL all = C[sum + n - 1][n - 1]; for (int i = 1; i <= n; ++i) { int fuck = sum - i * (en + 1) + n - 1; if (fuck < 0) break; //notice if (i & 1) { all = (all + MOD - C[n][i] * C[fuck][n - 1] % MOD) % MOD; } else all = (all + MOD + C[n][i] * C[fuck][n - 1] % MOD) % MOD; } return all; } int n, full; void work() { LL ans = 0; for (int i = 0; i <= full; ++i) { // 枚举ave ans += n * calc(n - 1, full, i * n - i) % MOD; ans %= MOD; } cout << ans << endl; }int main() { #ifdef local in(); #else #endif C[0][0] = 1; C[1][0] = 1, C[1][1] = 1; for (int i = 2; i <= 14000; ++i) { int en = min(60, i); C[i][0] = 1; for (int j = 1; j <= en; ++j) { C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD; } } while (scanf("%d%d", &n, &full) > 0 && (n + full)) work(); return 0; }

View Code
转载于:https://www.cnblogs.com/liuweimingcprogram/p/7309139.html