组合数部分

简介: 笔记

组合数定义


10.png


带模数

数据范围(a 、b较小)


11.png
const int N = 2005;
int ans[N][N];
void init() { // 递推预处理
  for (int i = 0;i < N;++i) {
    for (int j = 0;j <= i;++j) {
      if (!j)ans[i][j] = 1;
      else ans[i][j] = (ans[i - 1][j] + ans[i - 1][j - 1]) % mod;
    }
  }
}
int main() {
  init();
  int n;cin >> n;
  while (n--) {
    int a, b;cin >> a >> b;
    printf("%d\n", ans[a][b]);
  }
  return 0;
}


数据范围(a、b较大)


12.png

const int N = 100010;
int fact[N], infact[N];
int qmi(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1)res = (LL)res * a % mod;
    a = (LL)a * a % mod;
    b >>= 1;
  }
  return res;
}
int main() {
  fact[0] = infact[0] = 1;
  for (int i = 1;i < N;++i) {
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2) % mod; //求逆元
  }
  int n;cin >> n;
  while (n--) {
    int a, b;
    cin >> a >> b;
    printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
  }
  return 0;
}


数据范围(a、b非常大)


13.png

const int N = 100010;
int p;
int qmi(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1)res = (LL)res * a % p;
    a = (LL)a * a % p;
    b >>= 1;
  }
  return res;
}
int C(int a, int b) {
  if (b > a)return 0;
  int res = 1;
  for (int i = 1, j = a;i <= b;++i, --j) {
    res = (LL)res * j % p;
    res = (LL)res * qmi(i, p - 2) % p;
  }
  return res;
}
int lucas(LL a, LL b) {
  if (a < p && b < p)return C(a, b);
  return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}
int main() {
  int n;cin >> n;
  while (n--) {
    LL a, b;
    cin >> a >> b >> p;
    cout << lucas(a, b) << endl;
  }
  return 0;
}


无模数


数据范围14.png

等式右边分子分母分解质因数后约掉 再用高精度乘法

const int N = 100010;
bool st[N];
int primes[N], cnt;
int sum[N];
//欧拉筛
void get_primes(int n) {
  for (int i = 2;i <= n;++i) {
    if (!st[i]) {
      primes[cnt++] = i;
    }
    for (int j = 0;primes[j] <= n / i;++j) {
      st[primes[j] * i] = true;
      if (i % primes[j] == 0)break;
    }
  }
}
//求n的阶乘中 质因子p的次数
int get(int n, int p) {
  int res = 0;
  while (n) {
    res += n / p;
    n /= p;
  }
  return res;
}
//高精度乘法
vector<int>mul(vector<int>a, int b) {
  vector<int >c;
  int t = 0;
  for(int i = 0;i < a.size() || t;++i){
    if(i < a.size())t += a[i] * b;
    c.push_back(t % 10);
    t /= 10;
  }
  return c;
}
int main() {
  int a, b;cin >> a >> b;
  get_primes(a);
  for (int i = 0;i < cnt;i++) {
    int p = primes[i];
    sum[i] = get(a,p) - get(b,p) - get(a - b,p);//最终结果中质因子p的次数
  }
  vector<int>ans;
  ans.push_back(1);
//因为数据太大可能会溢出LL 所以不用快速幂 用高精度乘法
  for (int i = 0;i < cnt;++i) {
    for (int j = 0; j < sum[i];++j) {
      ans = mul(ans, primes[i]);//将最终化简结果的质因数分解形式变成原来的数据
    }
  }
  for (int i = ans.size() - 1;i >= 0;--i)printf("%d", ans[i]);
  cout << endl;
  return 0;
}


卡特兰数


image.png17.png

目录
相关文章
|
人工智能
找出组合数中的最大组合数
如下需求给出一个整形数组,要找出组合中最大的一个数 比如121,12,212,21  最大是 2122112121 想起用冒泡排序比较方便于是列出如下代码可供参考 public static void main(String[] args...
1014 0
|
移动开发
NYOJ459快速组合数
#include int main() { int m,n,a,b;int ans=1; scanf("%d%d",&n,&m); a=n-m+1; b=1; while(a
613 0
NYOJ 32(组合数)
  组合数 //唐甲希 #include #include int a[10]; void fun(int n,int k) { int i,j; for(i=n;i>0;--i)//每个递归里也有这个循环!!! {    //printf("...
817 0
|
9月前
82: 求组合数
82: 求组合数
|
算法 内存技术
求组合数三种算法
求组合数三种算法
99 0
|
机器学习/深度学习 人工智能
组合数学 - 组合数的个数
组合数的个数  输入一个n,然后输入n个一位数,求这n个数组成的不重复出现的整数的总和。   Mean:   略 analyse:  这样的数可以是1~n位,总共数的数目为:P(n,1)+p(n,2)+p(n,3)+.....+p(n,n)个。
787 0
|
C语言 C++
1056 组合数的和 (15 分)
给定 N 个非 0 的个位数字,用其中任意 2 个数字都可以组合成 1 个 2 位的数字。要求所有可能组合出来的 2 位数字的和。例如给定 2、5、8,则可以组合出:25、28、52、58、82、85,它们的和为330。
110 0
|
8月前
1056 组合数的和 (15 分)
1056 组合数的和 (15 分)

热门文章

最新文章