CF768F Barrels and boxes

朴灿烈づ我的快乐病毒、 2021-11-05 00:58 146阅读 0赞

[嘟嘟嘟][Link 1]  
  
此题不难。  
这种题做几道就知道些套路了：我们枚举酒有几堆，这样就能算出食物有多少堆以及他们的排列数，那么概率就是合法方案数 / 总方案数。  
设酒有\\(i\\)堆，那么就有\\(C\_\{w - 1\} ^ \{i - 1\}\\)种排列方法，对应的食物堆数就可能有\\(i - 1, i, i + 1\\)堆，然后同样用隔板法算出食物的排列方法，即\\(C\_\{f - 1\} ^ \{i - 2\}, C\_\{f - 1\} ^ \{i - 1\}, C\_\{f - 1\} ^ \{i\}\\)。把这俩乘起来就是当酒堆数为\\(i\\)的总方案数。  
至于合法方案数，就是我们先强制往每一堆酒上放\\(h\\)个，然后再往\\(i\\)堆酒上放\\(w - h \* i\\)个，即\\(C\_\{w - h \* i - 1\} ^ \{i - 1\}\\)。  
然后注意边界情况。

#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<vector> #include<stack> #include<queue> #include<assert.h> using namespace std; #define enter puts("") #define space putchar(' ') #define Mem(a, x) memset(a, x, sizeof(a)) #define In inline typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-8; const int maxn = 1e5 + 5; const ll mod = 1e9 + 7; In ll read() { ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans; } In void write(ll x) { if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0'); } In void MYFILE() { #ifndef mrclr freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif } int n, m, h; ll fac[maxn], inv[maxn]; In ll inc(ll a, ll b) {return a + b < mod ? a + b : a + b - mod;} In ll C(int n, int m) { if(m < 0 || m > n) return 0; return fac[n] * inv[m] % mod * inv[n - m] % mod; } In ll quickpow(ll a, ll b) { ll ret = 1; for(; b; b >>= 1, a = a * a % mod) if(b & 1) ret = ret * a % mod; return ret; } In void init() { fac[0] = inv[0] = 1; for(int i = 1; i < maxn; ++i) fac[i] = fac[i - 1] * i % mod; inv[maxn - 1] = quickpow(fac[maxn - 1], mod - 2); for(int i = maxn - 2; i; --i) inv[i] = inv[i + 1] * (i + 1) % mod; } int main() { //MYFILE(); m = read(), n = read(), h = read(); if(!m) {puts(n > h ? "1" : "0"); return 0;} if(!n) {puts("1"); return 0;} init(); ll ans1 = 0, ans2 = 0; for(int i = 1; i <= n; ++i) { ll tp1 = C(n - 1, i - 1); ll tp2 = inc(C(m - 1, i - 2), inc(C(m - 1, i - 1) * 2, C(m - 1, i))); if(1LL * n - 1LL * h * i >= i) ans2 = inc(ans2, C(n - h * i - 1, i - 1) * tp2 % mod); ans1 = inc(ans1, tp1 * tp2 % mod); } write(ans2 * quickpow(ans1, mod - 2) % mod), enter; return 0; }

转载于:https://www.cnblogs.com/mrclr/p/10935034.html

[Link 1]: https://www.luogu.org/problemnew/show/CF768F