一开始觉得是分拆数,后来发现是有序的分拆数,就变成插板法 sb 题了。
考虑本质上「堆」就是对总量的一个有序拆分。而这里不同的是总方案数要求不能存在某些位置放 $0$ 的情况。考虑如果可以放 $0$ 那么就是一个 $n$ 元线性不定方程组非负整数解的个数,这个地方要求 $k$ 个位置都 $\geq 1$ 的话,就只需要将等号右边的 $w/f$ 改成 $w-k$ 和 $f-k$ 即可。考虑合法方案数也是一样的道理,变成了 $w-h\cdot k$ 和 $f-h\cdot k$ 。
然后就可以考虑对每个堆数计数。发现对于一个数量 $n'$ 两者只会放 $\left\lfloor\dfrac{n}{2}\right\rfloor$ 和 $\left\lceil\dfrac{n}{2}\right\rceil$ 的数量,随便算一下即可。
```cpp
int res ;
int ans ;
int inv[N] ;
int fac[N] ;
int expow(int a, int b){
int ret = 1 ;
while (b){
if (b & 1)
ret = (ll)ret * a % P ;
a = (ll)a * a % P ; b >>= 1 ;
}
return ret ;
}
int binom(int x, int y){//\binom{x}{y}
return (ll)fac[x] * inv[y] % P * inv[x - y] % P ;
}
void prework(int p, int q){
fac[0] = inv[0] = 1 ; ans = res = 0 ;
for (int i = 1 ; i <= p + q + 1 ; ++ i)
fac[i] = 1ll * fac[i - 1] * i % P ;
inv[p + q + 1] = expow(fac[p + q + 1], P - 2) ;
for (int i = p + q ; i >= 1 ; -- i)
inv[i] = 1ll * inv[i + 1] * (i + 1) % P ;
}
int p, q, h ;
int main(){
cin >> q >> p >> h ;
prework(p, q) ; int x, y, z ;
// debug(fac, 1, p + q) ;
// debug(inv, 1, p + q) ;
if (p == 0)
return cout << 1 << '\n', 0 ;
if (q == 0){
if (p > h) cout << 1 << '\n' ;
else cout << 0 << '\n' ; return 0 ;
}
for (int i = 2 ; i <= p + q ; ++ i){
x = ceil(1.0 * i / 2.0) ;
y = floor(1.0 * i / 2.0) ; z = 0 ;
if (x <= p && y <= q)
add(z, 1ll * binom(p - 1, x - 1) % P * binom(q - 1, y - 1) % P) ;
if (x <= q && y <= p)
add(z, 1ll * binom(q - 1, x - 1) % P * binom(p - 1, y - 1) % P) ;
add(ans, z) ; z = 0 ;
if (1ll * x * h <= p && y <= q)
add(z, 1ll * binom(p - x * h - 1, x - 1) % P * binom(q - 1, y - 1) % P) ;
if (1ll * y * h <= p && x <= q)
add(z, 1ll * binom(p - y * h - 1, y - 1) % P * binom(q - 1, x - 1) % P) ;
add(res, z) ;
// debug(res, ' ') ;
// debug(ans) ;
}
// debug(res, ' ') ;
// debug(ans) ;
if (p + q <= 1) res = 1, ans = 1 ;
cout << 1ll * res * expow(ans, P - 2) % P << '\n' ;
return 0 ;
}
```