14203: 【原4203】计数

题目

题目描述

author: fur 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4203

计数

题目描述

要解决的问题很简单，组合数\(\binom{n}{m}\)的值是多少
当然，它很容易太大以致需要高精度，为了专注于有意义的问题我们只要输出答案对\(1e9+7\)取模即可

数学小知识

费马小定理:若有质数\(p\)，且有\(\gcd(x,p)=1\)，则\(x^{p-1}\equiv1(\mod p)\)

输入格式

第一行一个数\(t\)，表示共有\(t\)个需要求出的组合数
接下来\(t\)行，每行两个数\(n_i,m_i\)表示\(\binom{n_i}{m_i}\)

输出格式

共\(t\)行，每行一个数表示\(\binom{n_i}{m_i}\)的值

样例输入

样例输出

1  
1  
20

数据规模

对于20%的数据有
\(n\leq16\)
对于50%的数据有
\(n\leq30\)
对于70%的数据有
\(n\leq100\)
\(t\leq100\)
对于100%的数据有
\(0\leq m\leq n\leq1e5\)
\(1\leq t\leq2e4\)

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/17.
//
// 组合数计算 数论倒数

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

using ll=long long;

constexpr int N = 100000 + 5;

constexpr ll p = 1e9 + 7;
ll fac[N] = {1, 1};
ll f[N] = {1, 1};
ll inv[N] = {1, 1};

ll pow(ll x, ll y) {
    if (y == 0) return 1;
    ll z = pow(x, y / 2) % p;
    if (y % 2 == 0) return z * z % p;
    else return z * z % p * x % p;
}

ll c(int n, int m) {
    if (n == m || m == 0) return 1;
    return fac[n] * inv[m] % p * inv[n - m] % p;
}

int main() {
    for (int i = 2; i < 100000 + 5; ++i) {
        fac[i] = fac[i - 1] * i % p;
        f[i] = (p - p / i) * f[p % i] % p;
        inv[i] = inv[i - 1] * f[i] % p;
    }

    int T;
    int n, m;

    cin >> T;
    while (T--) {
        scanf("%d%d", &n, &m);
        printf("%lld\n", c(n, m));
    }
}

ligongzzz's solution

#include "iostream"
#include "cmath"
#include "cstdio"
using namespace std;

long long jc[100009] = { 0 };
constexpr long long mod = (long long)(1e9 + 7);

long long fast_pow(long long a, long long b) {
    long long ans = 1, base = a;
    while (b) {
        if (b & 1)
            ans = (ans * base) % mod;
        base = (base * base) % mod;
        b >>= 1;
    }
    return ans;
}

int main() {
    int t;
    scanf("%d", &t);
    //计算阶乘
    jc[0] = 1;
    for (long long i = 1; i <= 100005; ++i) {
        jc[i] = (jc[i - 1] * i) % mod;
    }
    for (; t > 0; --t) {
        long long n, m;
        scanf("%lld %lld", &n, &m);
        long long temp = (jc[m] * jc[n - m]) % mod;
        temp = fast_pow(temp, mod - 2);
        temp = (jc[n] * temp) % mod;
        printf("%lld\n", temp);
    }

    return 0;
}

skyzh's solution

#include <iostream>
using namespace std;

const int M = 1000000007;

long long ext_gcd(long long a, long long b, long long &x, long long &y) 
 {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    } else {
        long long r = ext_gcd(b, a % b, x, y);
        long long t = x;
        x = y;
        y = t - a / b * y;
        return r;
    }
}

long long mul_N[100001];
long long div_N[100001];

int main() {
    mul_N[1] = 1;
    for (int i = 2; i <= 100000; i++) {
        mul_N[i] = (mul_N[i - 1] * i) % M;
    }
    long long x, y;
    div_N[1] = 1;
    for (int i = 2; i <= 100000; i++) {
        long long a = mul_N[i];
        ext_gcd(a, M, x, y);
        while (x < 0) {
            x += M;
            y -= a;
        }
        div_N[i] = x;
    }
    int t;
    scanf("%d", &t);
    int a, b;
    for (int i = 0; i < t; i++) {
        scanf("%d%d", &a, &b);
        if (b == 0 || a == b) {
            printf("1\n");
        } else {
            int _m1 = (mul_N[a] * div_N[b]) % M;
            int _m2 = (_m1 * div_N[a - b]) % M;
            printf("%d\n", _m2);
        }
    }
    return 0;
}