西南交大INT杯2020-D.排列计数【排列组合+经典隔板法】

排列计数

Description

正所谓“牛如其主”，XHK家里养的N只牛牛因为身形健硕所以被邀请去参加集会里的展示活动，这些牛可以是公牛，也可以是母牛。牛们要站成一排，但是公牛是好斗的，为了避免公牛闹出乱子，任意两只公牛之间至少要有K只母牛。

现在请计算一共有多少种排队的方法，所有公牛可以看成是相同的，所有母牛也一样，答案对5000011取模。

Input

一行，输入两个整数N和K

Output

一个整数，表示排队的方法数。

Sample Input

4 2

Sample Output

6

思路：

1.首先，最多有多少只公牛其实很好求，就是n/(k+1)向上取整，将一只公牛和k只母牛放到一起计算，公牛最多就有n/(k+1)向上取整。

2.其次，就可以枚举放不同公牛的方案数，设当前枚举的公牛为x只，母牛必须固定为位置是x只公牛之间（x-1个空格）的y = k*(x-1)只母牛。现在就等于x+1个位置放n-y-x只牛，允许为空，有多少种方案数，这儿就要引入隔板法了，隔板法先放下面。所以方案数为：
∁ \complement ∁ x + 1 − 1 n − y − x + x + 1 − 1 x+1-1 \atop n-y-x+x+1-1 n−y−x+x+1−1x+1−1​ ⇒ ∁ \complement ∁ x n − k ∗ ( x − 1 ) x \atop n-k*(x-1) n−k∗(x−1)x​ (注：这儿写的比较细，耐心看肯定能懂);

3.最后求出枚举过不同公牛的方案总数，题目数据很大，所以要用乘法逆元来求组合数。

隔板法：

应用隔板法必须满足3个条件： 　　
（1） 这n个元素必须互不相异；
（2） 所分成的每一组至少分得1个元素；
（3） 分成的组别彼此相异。

1：假设有n个苹果，放到m个盘子中，每个盘子至少有1个，求总方案数。
相当于有m - 1个板子，将n个苹果分开。这m-1个板子只能放到n-1个间隔中，所以就是 ∁ \complement ∁ m − 1 n − 1 m-1 \atop n-1 n−1m−1​;

2：假设有n个苹果，放到m个盘子中，盘子可以为空，求总方案数。
我们可以将问题转化为将n+m个苹果，放到m个盘子中，每个盘子至少有1个，求总方案数。所以就是 ∁ \complement ∁ m − 1 n + m − 1 m-1 \atop n+m-1 n+m−1m−1​;

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 5000011;
ll fast_power(ll a, ll b) {
	ll ans=1;
	while (b > 0) {
		if(b & 1) {
           ans = ans * a % mod;
		}
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
ll calc(ll m, ll n)
{
	ll sum1 = 1, sum2 = 1;
	if(m > n - m) m = n - m;
	for(ll i = 1; i <= m; i++) {
        sum1 *= (n - i + 1);
        sum1 %= mod;
        sum2 *= i;
	    sum2 %= mod;
	}
	return (sum1 * fast_power(sum2, mod-2)) % mod;
}
void solve() {
    ll ans = 0;
	int n, k;
	cin >> n >> k;
	//maxn表示最多有多少头公牛
	int maxn = (n - 1) / (k + 1) + 1;
	for(int i = 1;i <= maxn; i++){
        //利用经典的隔板法。m个球放到n个盒子里的情况，允许盒子为空的情况类似。
        ans=(ans % mod + calc(i, n - k * i + k) % mod) % mod;
	}
	cout << (ans + 1) % mod;
}
int main() {
    solve();
	return 0;
}