Algorithm9.3 组合数
[TOC]
组合数
基本的排列组合数
A(n, m)和C(n, m)
第二类Stirling数
数学意义：把n个数划分成k个集合
实际意义：将n个球分到k个相同的盒子
// 递归写法
ll stirling(int n, int k){
if (k==n || k==1) return 1;
else if (k==2) return pow(2, (n-1)*1.0)-1;
else return stirling(n-1, k-1)+k*stirling(n-1, k);
}
// 非递归写法
第二类Stirling数的变形
数学意义：把n个数划分成k个不同的集合
实际意义：把n个球分到k个不同的盒子里
和第二类Stirling数的区别：就是划分出来的集合再进行容器的匹配，对于不同的集合划分到不同的容器中。匹配原则：Ann
ll stirling(int n, int k){
if (k==n || k==1) return 1;
else if (k==2) return pow(2, (n-1)*1.0)-1;
else return stirling(n-1, k-1)+k*stirling(n-1, k);
}
// 排列数Ann
ll factorial(ll n) {
ll fc = 1;
for (ll i = 1; i <= n; ++i) fc *= i;
return fc;
}
https://www.luogu.com.cn/problem/P1287
#include <iostream>
using namespace std;
typedef long long ll;
int a, b;
#include <cmath>
ll factorial(ll n) {
ll fc = 1;
for (ll i = 1; i <= n; ++i) fc *= i;
return fc;
}
ll stirling(int i, int j)
{
if ((j == i) || (j == 1)) return 1;
else if (j == 2) return pow(2, (i - 1) * 1.0) - 1;
else return stirling(i - 1, j - 1) + j * stirling(i - 1, j);
}
int main() {
scanf("%d%d", &a, &b);
printf("%lld\n", stirling(a, b)*factorial(b));
return 0;
}
最大公约数[gcd]与最小公倍数[gld]乘积 == 这两个数的乘积
a*b = gcd(a, b)*gld()
最小公倍数[gld]
可以利用最大公约数倒推回去，也就是gld(a, b)=a*b/gcd(a, b)
质数
判断1～n中的所有质数
1、基础：O(n^2)复杂度，遍历，遍历的边界从3～sqrt(x)
bool isprime(int x){
for (int i = 3; i <= sqrt(x); ++i) if (x%i == 0) return false;
return true;
}
2、埃拉托斯特尼筛：O(nlogn)复杂度
3、线性筛：O(n)
prime是质数列表，isprime
#define maxn 10000010
int vis[maxn], prime[maxn], isprime[maxn];
void Prime()
{
for(int i=2; i<=b; i++)
{
if(!vis[i]) prime[cnt++] = i, isprime[i] = 1;
for(int j=0; j<cnt&&i*prime[j]<=b; j++)
{
vis[i*prime[j]] = i;
if(i%prime[j]==0) break;
}
}
}
b = 100; // 设置筛的边界
LPrime();
for (int i = 5; i < 20; ++i) {
printf("%d %d %d\n", i, prime[i], isprime[i]); // prime是按照顺序的素数存放进来， isprime是索引的数是否为质数
}