错排板子

1.预处理版本

函数

'cpp'
const long long MAXN=1e6+10;//预处理个数
inline void get_cp(){
cp[0] = 1;
    for (int i = 2; i <= MAXN; i++) {
        cp[i] = (i - 1) * (cp[i - 2] + cp[i - 1]) % mod;
    }
}

使用时直接在主函数中引用

#include<iostream>
using namespace std;
int main(){
get_cp();
//########
int x;
cin>>x;
cout<<cp[x];//查询第x个错排
//########
return 0;
}

完整代码：

'cpp'
#include<iostream>
using namespace std;
const long long MAXN=1e6+10;//预处理个数
inline void get_cp(){
    cp[0] = 1;
    for (int i = 2; i <= MAXN; i++) {
        cp[i] = (i - 1) * (cp[i - 2] + cp[i - 1]) % mod;
    }
}
int main(){
    get_cp();
//########
    int x;
    cin>>x;
    cout<<cp[x];//查询第x个错排
//########
    return 0;
}

2.不需要预处理

函数

'cpp'
inline void get_cp(long long x){
    cp[0] = 1;
    for (int i = 2; i <= x; i++) {
        cp[i] = (i - 1) * (cp[i - 2] + cp[i - 1]) % mod;
    }
}

使用时直接在主函数中引用

#include<iostream>
using namespace std;
int main(){
//######## 
    int x;
    cin>>x;
    get_cp(x);
    cout<<cp[x];//查询第x个错排
//########
    return 0;
}

完整代码：

'cpp'
#include<iostream>
using namespace std;
inline void get_cp(long long x){
    cp[0] = 1;
    for (int i = 2; i <= x; i++) {
        cp[i] = (i - 1) * (cp[i - 2] + cp[i - 1]) % mod;
    }
}
int main(){
//######## 
    int x;
    cin>>x;
    get_cp(x);
    cout<<cp[x];//查询第x个错排
//########
    return 0;
}

求组合数板子 $C_n^m$

1.预处理版本（卢卡斯定理+快速幂求组合数）

函数

'cpp'
const long long MAXN=1e6+10;
const long long mod=1e9+7;
long long f[maxn],inv[maxn];
long long fpow(ll a, ll b) {
    a %= mod;
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void Lucas()
{
    f[0] = 1;
    for (int i = 1; i < Maxn; i++)
    {
        f[i] = f[i - 1] * i % mod;
        inv[i] = fpow(f[i], mod - 2);
    }
}

使用时直接在主函数引用

#include<iostream>
using namespace std;
const long long mod=1e9+7;
int main()
{
    Lucas();
    long long T;
    scanf("%lld",&T);
    while(T--){
        long long n,m;
        scanf("%lld %lld",&n,&m);//输入n,m||n>=m
        printf("%lld",f[n] * inv[m] % mod * inv[n - m] % mod);//求组合数
    }
    return 0;
}

完整代码：

#include<iostream>
using namespace std;
const long long MAXN=1e6+10;
const long long mod=1e9+7;
long long f[maxn],inv[maxn];
long long fpow(ll a, ll b) {
    a %= mod;
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void Lucas()
{
    f[0] = 1;
    for (int i = 1; i < Maxn; i++)
    {
        f[i] = f[i - 1] * i % mod;
        inv[i] = fpow(f[i], mod - 2);
    }
}
int main()
{
    Lucas();
    long long T;
    scanf("%lld",&T);
    while(T--){
        long long n,m;
        scanf("%lld %lld",&n,&m);//输入n,m||n>=m
        printf("%lld",f[n] * inv[m] % mod * inv[n - m] % mod);//求组合数
    }
    return 0;
}

2.不需要预处理

函数

const long long mod=1e9+7;
long long fpow(long long a, long long b) {
    a %= mod;
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

long long Comb(long long a, long long b) {
   if (a < b)   return 0;
   if (a == b)  return 1;
   if (b > a - b)   b = a - b;
   long long ans = 1, ca = 1, cb = 1;
   for (long long i = 0; i < b; ++i) {
       ca = (ca * (a - i)) % mod;
       cb = (cb * (b - i)) % mod;
   }
   ans = (ca * fpow(cb, mod - 2)) % mod;
   return ans;
}

long long Lucas(long long n, long long m) {
   long long ans = 1;
   while (n && m && ans) {
       ans = (ans * Comb(n % mod, m % mod)) % mod;
       n /= mod;
       m /= mod;
   }
   return ans;
}

使用时直接在主函数中引用

#include<iostream>
using namespace std;
int main(){
    long long T;
    scanf("%lld",%T);
    while(T--){
        long long n,m;
        scanf("%lld %lld",&n,&m);//n>=m
        printf("%lld\n",Lucas(n,m));
    }
    return 0;
}

完整代码：

#include<iostream>
using namespace std;
const long long mod=1e9+7;
long long fpow(long long a, long long b) {
    a %= mod;
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

long long Comb(long long a, long long b) {
   if (a < b)   return 0;
   if (a == b)  return 1;
   if (b > a - b)   b = a - b;
   long long ans = 1, ca = 1, cb = 1;
   for (long long i = 0; i < b; ++i) {
       ca = (ca * (a - i)) % mod;
       cb = (cb * (b - i)) % mod;
   }
   ans = (ca * fpow(cb, mod - 2)) % mod;
   return ans;
}

long long Lucas(long long n, long long m) {
   long long ans = 1;
   while (n && m && ans) {
       ans = (ans * Comb(n % mod, m % mod)) % mod;
       n /= mod;
       m /= mod;
   }
   return ans;
}
int main(){
    long long T;
    scanf("%lld",%T);
    while(T--){
        long long n,m;
        scanf("%lld %lld",&n,&m);//n>=m
        printf("%lld\n",Lucas(n,m));
    }
    return 0;
}