stone (组合数学 + Lucas定理)

传送门 解题思路:第i组的人数必须大于Ci，于是我们可以将问题转化为\(N-\sum_{i=1}^M Ci\)人分到M组中，且保证每一组的人数大于0，然后我们可以使用隔板法求出分的的组数\(C_{N-1-\sum_{i=1}^M Ci}^{m-1}\) 我们可以直接通过基本的组合公式+费马小定理直接求，也可以通过Lucas定理求得: 直接求: Code:

#include
using namespace std;
#define ll long long
#define mod 1000000007
ll n,m,a,t;

ll power(ll a,ll b) {
	ll ans = 1;
	while(b) {
		if(b&1) ans = (ans*a)%mod;
		a = (a*a)%mod;
		b>>=1;
	}
	return ans;
}

ll inv(ll x) {
	return power(x,mod-2);
}

ll C(ll a,ll b) {
	ll ans =  1;
	for(ll i = 1;i >=1, (a*=a) %= p)
		if(b & 1) (ans *= a) %= p;
	return ans;
}

LL c(LL n, LL m, LL p) {
	if(n < m) return 0;
	if(m > n - m) m = n - m;
	LL s1 = 1, s2 = 1;
	for(int i=0; i