首页 > 其他分享 >组合数学

组合数学

时间：2024-04-11 18:11:44浏览次数：22  
标签：组合 int inv MAXV 1ll 数学 nv MOD

逆元

若 \(i \cdot x = 1\)，则 \(i^{-1}=x\)。

递推求乘法逆元

\[令模数为 p,正整数 i,a=\lfloor\frac{p}{i}\rfloor,b=p\operatorname{mod} i,且b\ne0。\\ a\cdot i+b=p\\ \Downarrow\\ a\cdot i+b\equiv0 (\operatorname{mod}p)\\ \frac{i}{b}+\frac{1}{a}\equiv0(\operatorname{mod}p)\\ \frac{i}{b}\equiv-\frac{1}{a}(\operatorname{mod}p)\\ \frac{b}{i}\equiv-a(\operatorname{mod}p)\\ i^{-1}\equiv(-a)\cdot b^{-1}(\operatorname{mod}p)\\ \]

令 \(inv_i=i^{-1}\)，则我们可以由上面的结论得到 \(inv_i = \lfloor-\frac{p}{i}\rfloor \cdot inv_{p \operatorname{mod} i} \operatorname{mod} p\) 。

代码

void C() {
  inv[1] = 1;
  for(int i = 2; i < MAXV; ++i) {
    inv[i] = 1ll * (p - p / i) * inv[p % i] % p;
  }
}

C();

平方求组合数

可以发现，\(C_n^m\) 有两种情况：

  • 选最后一个：\(C_{n-1}^{m-1}\)。
  • 不选最后一个：\(C_{n-1}^m\)。

所以 \(C_n^m=C_{n-1}^{m-1}+C_{n-1}^m\)。（实际上这就是杨辉三角）

代码

void C() {
  for(int i = 0; i < MAXV; ++i) {
    c[i][0] = 1;
    for(int j = 1; j <= i; ++j) {
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
    }
  }
}

预处理求组合数

众所周知，\(C_n^m=\frac{n!}{m!(n-m)!}\)。所以我们只需预处理出阶乘的逆元。

令 \(f_i=i!,g_i=i!^{-1}\)，则：

\[f_i=f_{i-1}\cdot i \operatorname{mod} p\\ g_i=g_{i-1}\cdot inv_i \operatorname{mod} p\\ C_n^m=f_n\cdot g_m\cdot g_{n-m} \operatorname{mod} p \]

void C() {
  inv[1] = f[0] = Inv[0] = 1;
  for(int i = 1; i < MAXV; ++i) {
    f[i] = 1ll * f[i - 1] * i % p;
    inv[i] = (i > 1 ? 1ll * (p - p / i) * inv[p % i] % p : 1);
    Inv[i] = 1ll * Inv[i - 1] * inv[i] % p;
  }
}

C();

题目

CSES P1715

题目描述

给定一个字符串 \(S\)，求将其重新排列后能得到多少种不同的字符串。

思路

首先在不考虑字符相同的情况下答案明显就是 \(|S|!\)，而每种相同字符会重复计算 \(cnt_x!\) 次，其中 \(cnt_x\) 表示字符 \(x\) 的出现次数，所以答案为：\(|S|! \cdot \prod \limits_{i=0}^{25} cnt_i!^{-1}\)。

时空复杂度均为 \(O(N)\)。

细节

无。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXV = 1000001, MOD = 1000000007;

int f[MAXV], nv[MAXV], inv[MAXV], cnt[26], ans;
string s;

void C() {
  f[0] = f[1] = nv[1] = inv[0] = inv[1] = 1;
  for(int i = 2; i < MAXV; ++i) {
    f[i] = 1ll * f[i - 1] * i % MOD;
    nv[i] = 1ll * (MOD - MOD / i) * nv[MOD % i] % MOD;
  }
  for(int i = 2; i < MAXV; ++i) {
    inv[i] = 1ll * inv[i - 1] * nv[i] % MOD;
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  C();
  cin >> s;
  for(int i = 0; i < int(s.size()); ++i) {
    cnt[s[i] - 'a']++;
  }
  ans = f[s.size()];
  for(int i = 0; i < 26; ++i) {
    ans = 1ll * ans * inv[cnt[i]] % MOD;
  }
  cout << ans;
  return 0;
}

CSES P1716

题目描述

有 \(N\) 个小朋友和 \(M\) 个苹果，求有多少中分配方案。

思路

可以看做是 \(M\) 个苹果之间有 \(M-1\) 个空位，有 \(N-1\) 个板子要插在空位中，相邻两块板子之间的苹果就是属于同一个小朋友的。可是小朋友可以不拿苹果，所以我们再加入 \(N\) 个虚拟苹果，使得每个小朋友都能拿到苹果，所以答案为 \(C_{N+M-1}^{N-1}\)。

时空复杂度均为 \(O(N)\)。

细节

无

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXV = 2000001, MOD = 1000000007;

int n, m, f[MAXV], nv[MAXV], inv[MAXV], cnt[26], ans;

void C() {
  f[0] = f[1] = nv[1] = inv[0] = inv[1] = 1;
  for(int i = 2; i < MAXV; ++i) {
    f[i] = 1ll * f[i - 1] * i % MOD;
    nv[i] = 1ll * (MOD - MOD / i) * nv[MOD % i] % MOD;
  }
  for(int i = 2; i < MAXV; ++i) {
    inv[i] = 1ll * inv[i - 1] * nv[i] % MOD;
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  C();
  cin >> n >> m;
  cout << ((1ll * f[m + n - 1] * inv[n - 1]) % MOD * inv[m]) % MOD;
  return 0;
}

GYM 104386 C

题目描述

有一个数组 \(A=\{1,1,\dots\}\)，每次对 \(A\) 进行前缀和，求 \(K\) 次操作后 \(A_N\) 的值。

思路

令第 \(i\) 次第 \(j\) 项为 \(f_{i,j}\)，可以得到 \(f_{i,j}=f_{i,j-1}+f_{i-1,j}\)，现在我们转换一下坐标系，变为斜方向的，即 \(f_{i,j}=f_{i-1,j-1}+f_{i-1,j}\)，很容易发现这就是组合数的递推式。因为转换了坐标系，所以答案为 \(C_{N+K-1}^{N-1}\)。

时空复杂度均为 \(O(N+K)\)。

细节

注意第一维是 \(1\) 下标，第二维是 \(0\) 下标。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXV = 2000001, MOD = 1000000007;

int t, n, k, f[MAXV], nv[MAXV], inv[MAXV];

void C() {
  f[0] = f[1] = nv[1] = inv[0] = inv[1] = 1;
  for(int i = 2; i < MAXV; ++i) {
    f[i] = 1ll * f[i - 1] * i % MOD;
    nv[i] = 1ll * (MOD - MOD / i) * nv[MOD % i] % MOD;
  }
  for(int i = 2; i < MAXV; ++i) {
    inv[i] = 1ll * inv[i - 1] * nv[i] % MOD;
  }
}

void Solve() {
  cin >> n >> k;
  int x = n + k - 1, y = n - 1;
  cout << ((1ll * f[x] * inv[y]) % MOD * inv[x - y]) % MOD << "\n";
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  C();
  cin >> t;
  while(t--) {
    Solve();
  }
  return 0;
}

CSES P1717

题目描述

有 \(N\) 个小朋友送礼物，不能给自己送礼物，求每个小朋友都收到礼物的方案数。

思路

由于每个小朋友都要收到礼物，所以这就是求错排数，使用 DP。

令 \(dp_x\) 表示长度为 \(x\) 的错排数，\(A_1=i(2 \le i \le x)\)。则第 \(i\) 位上有两种情况：

  • \(A_i=1\)，则方案数为 \(dp_{x-2}\)，因为 \(A_1\) 和 \(A_i\) 已经不会对答案造成影响。
  • \(A_i\ne 1\)，则方案数为 \(dp_{x-1}\)，因为 \(A_1\) 已经没有作用，可以把 \(A_i\) 看做 \(A_1\)。

所以 \(dp_x = (x-1)(dp_{x-1}+dp_{x-2})\)。

细节

\(dp_0=1,dp_1=0\)。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXV = 2000001, MOD = 1000000007;

int n, f[MAXV], nv[MAXV], inv[MAXV], dp[MAXV];

void F() {
  f[0] = f[1] = nv[1] = inv[0] = inv[1] = 1;
  for(int i = 2; i < MAXV; ++i) {
    f[i] = 1ll * f[i - 1] * i % MOD;
    nv[i] = 1ll * (MOD - MOD / i) * nv[MOD % i] % MOD;
  }
  for(int i = 2; i < MAXV; ++i) {
    inv[i] = 1ll * inv[i - 1] * nv[i] % MOD;
  }
}

int C(int x, int y) {
  return ((1ll * f[x] * inv[y]) % MOD * inv[x - y]) % MOD;
}

int A(int x, int y) {
  return (1ll * f[x] * inv[y]) % MOD;
}

int Pow(int a, int b) {
  int res = 1;
  while(b) {
    if(b & 1) {
      res = (1ll * res * a) % MOD;
    }
    a = (1ll * a * a) % MOD;
    b >>= 1;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  F();
  cin >> n;
  dp[0] = 1, dp[1] = 0;
  for(int i = 2; i <= n; ++i) {
    dp[i] = 1ll * (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD;
  }
  cout << dp[n];
  return 0;
}

Luogu P4071

题目描述

求有多少种 \(1\) 到 \(N\) 的排列 \(A\)，使得恰好有 \(M\) 个 \(i\) 满足 \(A_i=i\)。

思路

由于有 \(M\) 个位置 \(A_i=i\)，则剩下的肯定不满足，即错排，所以方案数为 \(dp_{N-M} \cdot C_{N}^{M}\)。

时空复杂度均为 \(O(N)\)

细节

无。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXV = 2000001, MOD = 1000000007;

int t, n, m, f[MAXV], nv[MAXV], inv[MAXV], dp[MAXV];

void F() {
  f[0] = f[1] = nv[1] = inv[0] = inv[1] = 1;
  for(int i = 2; i < MAXV; ++i) {
    f[i] = 1ll * f[i - 1] * i % MOD;
    nv[i] = 1ll * (MOD - MOD / i) * nv[MOD % i] % MOD;
  }
  for(int i = 2; i < MAXV; ++i) {
    inv[i] = 1ll * inv[i - 1] * nv[i] % MOD;
  }
  dp[0] = 1, dp[1] = 0;
  for(int i = 2; i <= MAXV; ++i) {
    dp[i] = 1ll * (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD;
  }
}

int C(int x, int y) {
  return ((1ll * f[x] * inv[y]) % MOD * inv[x - y]) % MOD;
}

int A(int x, int y) {
  return (1ll * f[x] * inv[y]) % MOD;
}

int Pow(int a, int b) {
  int res = 1;
  while(b) {
    if(b & 1) {
      res = (1ll * res * a) % MOD;
    }
    a = (1ll * a * a) % MOD;
    b >>= 1;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  F();
  cin >> t;
  while(t--) {
    cin >> n >> m;
    cout << 1ll * dp[n - m] * C(n, n - m) % MOD << "\n";
  }
  return 0;
}

标签：组合,int,inv,MAXV,1ll,数学,nv,MOD
From： https://www.cnblogs.com/yaosicheng124/p/18129812

相关文章

  • 洛谷题单指南-数学基础问题-P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
    原题链接：https://www.luogu.com.cn/problem/P1029题意解读：已知x，y，求有多少对p、q，使得p、q的最大公约数为x，最小公倍数为y。解题思路：枚举法即可。枚举的对象：枚举p，且p必须是x的倍数，还有p<=yq的计算：q=x*y/p，q要存在，必须x*y%p==0，且gcd(p,q)==x100分代码：#include......
  • 洛谷题单指南-数学基础问题-P1835 素数密度
    原题链接：https://www.luogu.com.cn/problem/P1835题意解读：要计算L-R范围内素数的个数。解题思路：直接对L~R的每个数判断素数肯定不可取，因为L、R的范围较大。既然要计算素数的个数，那么可以把其中的合数标记出来即可。如何标记合数？可以借助于筛素数的算法思想，枚举每一个素数，然......
  • 【SQL】mysql数学函数功能介绍并举例
    mysql数学函数：ABS(x):返回x的绝对值。CEIL(x)或CEILING(x):返回大于或等于x的最小整数。FLOOR(x):返回小于或等于x的最大整数。ROUND(x,d):返回x四舍五入到小数点后d位的值。POW(x,y)或POWER(x,y):返回x的y次幂。SQRT(x):返回x的平方根。m......
  • 神经网络背后的数学原理
    原文地址：TheMathBehindNeuralNetworks2024年3月29日深入研究现代人工智能的支柱——神经网络，了解其数学原理，从头开始实现它，并探索其应用。神经网络是人工智能（AI）的核心，为从发现照片中的物体到翻译语言的各种应用提供动力。在本文中，我们将深入探讨神经网络是什么，它......
  • 【数学】多项式插值
    问题描述给出\(n+1\)个二维平面上的点对\((x_0,y_0),(x_1,y_1),(x_2,y_2),\cdots,(x_{n},y_{n})\)，求一个经过这些点的不超过\(n\)次的多项式\(P(x)=p_{n}\cdotx^{n}+p_{n-1}\cdotx^{n-1}+p_{n-2}\cdotx^{n-2}+\cdots+p_{1}\cdotx+......
  • TypeScript 与组合式 API
    看吧：https://cn.vuejs.org/guide/typescript/composition-api.html为组件的props标注类型<scriptsetuplang="ts">constprops=defineProps({foo:{type:String,required:true},bar:Number})props.foo//stringprops.bar//number|undefine......
  • 组合数学程序包 by My_Desire
    BeginPackage["My`"]RTRow::usage="ReadTrianglebyRow"TpQ::usage="全正性判断"LSTP::usage="三角全正性判断"RiordanArray::usage="RiordanArray[d_Function,h_Function,n_]"ExpRiordanArray::usage="ex......
  • 组合创新，原创模型！多类型需求响应负荷标准化建模+共享储能（附matlab代码实现）
    专题推荐：论文推荐，代码分享，视角（点击即可跳转）所有链接建议使用电脑端打开，手机端打开较慢【代码推荐购买指南】电力系统运行优化与规划、时间序列预测、回归分类预测matlab代码公众号历史推文合集23.3.21（电力系统前沿视角/预测和优化方向matlab代码/电力系统优秀论文推程......
  • 二十九 4009. 收集卡牌 (数学期望|状压DP)
    4009.收集卡牌(数学期望|状压DP)略importjava.util.*;publicclassMain{privatestaticfinalintN=16,M=1<<N;privatestaticintn,m;privatestaticdouble[]p=newdouble[N];privatestaticdouble[][]dp=newdouble[M][N*5......
  • 全排列价值（数学问题）
     1importjava.util.*;23publicclassDemo1{4publicstaticvoidmain(String[]args){5Scannersc=newScanner(System.in);6longn;7n=sc.nextLong();8longres=n*(n-1)/2%998244353;9for(in......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99