首页 > 其他分享 >排列计数

排列计数

时间:2023-03-18 17:33:56浏览次数:35  
标签:排列 int res inv define 计数 MOD lld

排列计数

输入样例:

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

相关文章

  • SQL—计数(count)与求平均值(avg/AVG)大小写都能识别
    题目要求:计算男生人数以及求平均gpa,而且还需要将查询后的列重新命名(注意有将平均gpa保留到小数点后一位的限制。)两个具体要求:计数与平均、重新命名selectcount(gender)......
  • 【P2109 [NOI2007]】 生成树计数(状压 dp + 矩阵快速幂)
    状压dp+矩阵快速幂优化。感觉题解区几篇题解说得云里雾里的……也没有一定的证明……Link.SolutionPart1dp状态设计发现\(k\)的范围很小,具有很强的指向性——......
  • P4054 [JSOI2009] 计数问题
    二维树状数组板子,C[color][x][y] #include<bits/stdc++.h>usingnamespacestd;constintN=403,M=2e5+4;#defineintlonglongintA[N][N],c[101][N......
  • 计数排序
    计数排序的时间复杂度为:O(N)理由如下:数据取值范围是常数M,待排序元素个数是N,总的时间复杂度是O(M+N)=O(N)!我们只把每个待排序的数字访问了一遍,所以是O(N)!啥?你问......
  • 回溯算法解决排列—组合—子集问题
    回溯算法解决排列—组合—子集问题无论是排列、组合还是子集问题,就是让你从序列nums中以给定规则取若干元素,主要有以下几种变体:元素无重不可复选,即nums中的元素都......
  • 力扣中46 全排列
    //可以用类似77组合那种方法只不过加了访问数组//也可以用官方题解来搞设置一个正确排列后直接进行交换publicList<List<Integer>>permute(int[]nums){......
  • 最短路计数
    /*边权值都为1,所以可以用BFS来做记住BFS和dikstra都是满足拓扑序性质的,也就是说可以用二者解决图论中的dp问题,而spfa不满足拓扑序的性质*/#include<bits/st......
  • PostgreSQL 计数查询效率,物化视图 [重复]
    PostgreSQL计数查询效率,物化视图[重复]问题:PostgreSQL计数查询效率,物化视图[重复]可能重复:PostgreSQL计数查询优化使用PostgreSQL9.2,我们试图弄清楚是否有......
  • 四位计数器testbench的设计
    简单介绍一下四位计数器所要满足的条件: 1.4bit循环计数;      1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,1,.......2.能同步清零;        高电平有效3.有加载功能......
  • 华为OD机试,最大排列
    ......