题解 P1680 【奇怪的分组】

· · 题解

解法

首先将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;
}