# 14203: 【原4203】计数

### 题目描述

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

# 计数

## 样例输入

3
4 0
5 5
6 3


## 样例输出

1
1
20


## 数据规模

$$n\leq16$$

$$n\leq30$$

$$n\leq100$$
$$t\leq100$$

$$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;
}