# CF768F Barrels and boxes

Toot toot

This question is not difficult.
We can know some routines by doing several questions like this: how many piles of wine do we lift, so that we can figure out how many piles of food and their arrangement number, then the probability is the number of legal schemes / total schemes.
i f there are \ (i \) stacks for wine, then there are \ (C {W - 1} ^ {i - 1} \) permutations, and the corresponding number of food stacks may be \ (i - 1, i, i + 1 \) stacks. Then the partition method is also used to calculate the permutation of food, that is, \ (C {F - 1} ^ {i - 2}, C {F - 1} ^ {i} \). Multiplying these two is the total number of schemes when the number of wine stacks is \ (i \).
As for the number of legal schemes, we first force \ (H \) on each pile of wine, and then \ (w - h * i \) on \ (i \) pile of wine, that is \ (C {w - h * i - 1} ^ {i - 1} \).
Then pay attention to the boundary.

```#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;
{
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();
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;
}```

Keywords: PHP

Added by Hypnos on Sun, 03 Nov 2019 21:46:04 +0200