排列计数
输入样例:
5
1 0
1 1
5 2
100 50
10000 5000
输出样例:
0
1
20
578028887
60695423
组合数+错排
错排式:D[n] = (n - 1) * (D[n - 1] + D[n - 2])
#include <bits/stdc++.h>
using namespace std;
#define INF LONG_LONG_MAX
#define int long long
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 1000010, MOD = 1e9 + 7;
int T;
int n, m;
int a[N], f[N];
int inv[N], s[N];
int qmi(int a, int k, int p) // 求a^k mod p
{
int res = 1 % p;
while (k)
{
if (k & 1)
res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
void init()
{
f[0] = 1, f[1] = 0, f[2] = 1;
s[0] = s[1] = inv[0] = inv[1] = 1;
for (int i = 2; i <= 1000000; i++)
{
if (i > 2)
f[i] = (i - 1) * (f[i - 1] + f[i - 2]) % MOD;
s[i] = s[i - 1] * i % MOD;
inv[i] = qmi(i, MOD - 2, MOD) * inv[i - 1] % MOD;
}
}
void solve()
{
scanf("%lld %lld", &n, &m);
printf("%lld\n", ((s[n] * inv[n - m]) % MOD * inv[m] % MOD) * f[n - m] % MOD);
}
signed main()
{
// FAST;
scanf("%lld", &T);
init();
while (T--)
solve();
return 0;
}
标签:排列,int,res,inv,define,计数,MOD,lld
From: https://www.cnblogs.com/Aidan347/p/17231268.html