自动搬运

查看原文

来自洛谷，原作者为

	hongzy **

搬运于2025-08-24 21:27:51，当前版本为作者最后更新于2018-06-06 20:38:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解法

首先将n减去所有的$C_i$，于是是原问题转换为：n个相同的球放入m个不同盒子里，不能为空，求方案数.

可以直接运用隔板法，答案为 $C(n-1, m-1)$ $mod$ $p$ ;

（以下就用$p$代表模质数1000000007

下面介绍两种求 $C(n-1, m-1)$ $mod$ $p$ 的方法.

方法1 : 直接求

组合数的公式：$C(n, k) = n!$ $/$ $(k!(n-k)!)$

设分子为 $a$，分母为 $b$，则$C(n, k) = a$ $/$ $b$

可以预处理出1~MAXN的阶乘 mod p，$a$和$b$可以O(1)得到

除法取模不能直接除并取模，答案应该为$a * b'$ $mod$ $p$，$b'$为$b$在模$p$意义下的逆元.

考虑到$p$是个质数，求逆元不需要Extended_gcd和欧拉定理，只需要费马小定理.

运行时间：80ms.

#include <iostream>
#include <cstdio>
using namespace std;

#define MOD 1000000007
#define MAXN 1000000
typedef long long LL;

int Read() { //快读 
	char c; int ans(0); 
	while(!isdigit(c = getchar()));
	do ans = ans * 10 + c - 48;
	while(isdigit(c = getchar()));
	return ans;
}

int n, m, ans;
int fc[MAXN + 10];

LL Qpow(LL a, LL b) { //快速幂 
	LL ans = 1;
	for(; b; b>>=1, a=a*a%MOD)
		if(b & 1) ans = ans*a % MOD;
	return ans;
}

int C(int n, int k) { //求组合数 
	LL fm = (1LL * fc[n-k] * fc[k]) % MOD;
	return 1LL * fc[n] * Qpow(fm, MOD-2) % MOD;
}

int main() {
	fc[0] = 1;
	for(int i=1; i<=MAXN; i++) //预处理阶乘
		fc[i] = (1LL * fc[i-1] * i) % MOD;
	n = Read(), m = Read();
	for(int i=1; i<=m; i++) n -= Read();
	printf("%d\n", C(n-1, m-1));
	return 0;
}

方法2 : Lucas定理

Lucas定理可以直接求 $C(n, m)$ $mod$ $p$

跑得非常快，4ms（手写getchar可以0ms），建议掌握这种方法.

#include <iostream>
#include <cstdio>
using namespace std;

#define MOD 1000000007
typedef long long LL;

int Read() { //快读
	char c; int ans(0);
	while(!isdigit(c = getchar()));
	do ans = ans * 10 + c - 48;
	while(isdigit(c = getchar()));
	return ans;
}

int n, m;

LL Qpow(LL a, LL b, LL p) { //快速幂 
	LL ans = 1;
	for(; b; b>>=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<m; i++) {
		s1 = s1 * (n - i) % p;
		s2 = s2 * (i + 1) % p;
	}
	return s1 * Qpow(s2, p-2, p) % p;
}

LL Lucas(LL n, LL m, LL p) { //Lucas
	if(m == 0) return 1;
	return c(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}

int main() {
	n = Read(), m = Read();
	for(int i=1; i<=m; i++) n -= Read();
	printf("%d\n", Lucas(n-1, m-1, MOD));
	return 0;
}