质因数分解

//质因数分解

int prime[MAXN], tim[MAXN], cnt;

void Divide(int N)

{

	printf("%d = ", N);

	for(int i = 2; i * i <= N; i++) if(N % i == 0)

	{

		prime[++cnt] = i;

		while(N % i == 0) N /= i, tim[cnt]++;

	}

	if(N > 1) prime[++cnt] = N, tim[cnt] = 1;

	printf("%d^%d", prime[1], tim[1]);

	for(int i = 2; i <= cnt; i++)

		printf(" * %d^%d", prime[i], tim[i]);

}

线性筛素数/欧拉函数

线性筛素数/欧拉函数

int phi[MAXN], prime[MAXP], cnt;

bool vis[MAXN];

void Prime(int N)

{

	phi[1] = 1;

	for(int i = 2; i <= N; i++)

	{

		if(!vis[i]) prime[++cnt] = i, phi[i] = i-1;

		for(int j = 1; j <= cnt && i*prime[j] <= N; j++)

		{

			vis[i*prime[j]] = true;

			if(i % prime[j] == 0) { phi[i*prime[j]] = phi[i] * prime[j]; break; }

			phi[i*prime[j]] = phi[i] * (prime[j]-1);

		}

	}

}

Miller-Robin大素数测试/快速幂/快速乘

//Miller-Robin大素数测试

#define LL long long

//O(1)快速乘(模)

LL kmul(LL a,LL b,LL P)

{

    a = (a % P + P) % P,b = (b % P + P) % P;

    return ((a * b - (LL)((long double)a / P * b + 1e-6) * P) % P + P) % P;

}

//O(logn)快速幂

LL kpow(LL a, LL b, LL mod)

{

	LL ret = 1;

	while(b)

	{

		if(b & 1) ret = kmul(ret, a, mod);

		a = kmul(a, a, mod); b >>= 1;

	}

	return ret;

}

bool Mil_Rb(LL N, LL a)

{

	LL d = N-1; int s = 0;

	while(!(d & 1))

		d >>= 1, s++;

	LL t = kpow(a, d, N);

	if(t == 1 || t == -1) return true;

	for(int i = 0; i < s; i++)

	{

		if(t == N-1) return 1;

		t = kmul(t, t, N);

	}

	return 0;

}

bool isPrime(LL N)

{

	if(N == 2) return true;

	if(N == 1 || !(N & 1)) return false;

	LL a[5] = { 2, 3, 5, 7, 11 };

	for(int i = 0; i < 5; i++)

	{

		if(N == a[i]) return true;

		if(!(N % a[i])) return false;

		if(N > a[i] && !Mil_Rb(N, a[i])) return false;

	}

	return true;

}

gcd & lcm

//gcd & lcm

LL gcd(LL a, LL b) { return b ? gcd(b, a%b) : a; }

LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }

exgcd

//a*x + b*y = b*y + (a%b)*x + (a/b)*b*x

//          = b*(y+x*(a/b)) + (a%b)*x

#define LL long long

void exgcd(LL a, LL b, LL &x, LL &y, LL &gcd)

{

	if(!b) { x = 1, y = 0; gcd = a; return; }

	exgcd(b, a%b, y, x, gcd); y -= x * (a/b);

}

中国剩余定理

//中国剩余定理

void exgcd(int a, int b, int &x, int &y)

{

	if(!b) { x = 1; y = 0; return; }

	exgcd(b, a%b, y, x); y -= x*(a/b);

}

int CRT(int *W, int *B, int k) // W > B

{

	int x, y, mulsum = 1, ans = 0;

	for(int i = 1; i <= k; i++)

		mulsum *= W[i];

	for(int i = 1; i <= k; i++)

	{

		int M = mulsum/W[i];

		exgcd(W[i], M, x, y);

		ans = (ans + y*M*B[i]) % mulsum;

	}

	if(ans < 0) ans += mulsum;

	return ans;

}

卡特兰数

// ksm(a, mod-2)在mod为素数的情况下≡a^(-1)，即a在mod下的逆元

//Catalan

const int MAXN = 5005;

int Catalan[MAXN];

int pre()

{

	Catalan[0] = 1;

	for(int i = 1; i < MAXN; i++)

		for(int j = 0; j < i; j++)

			Catalan[i] = (Catalan[i] + (LL)Catalan[j] * Catalan[i-j-1]  %mod) % mod;

	//						or

	for(int i = 1; i < MAXN; i++)

		Catalan[i] = (LL)Catalan[i-1] * (4*i-2) % mod * ksm(n+1, mod-2);

}

int Catalan(int n)

{

	return C(n<<1, n) * ksm(n+1, mod-2);

	//						or

	return (C(n<<1, n) - C(n<<1, n-1)) % mod + mod) % mod;

}

康托展开式

LL Fac[21];

//预处理阶乘(20!在longlong范围内而21!爆longlong)

inline void init()

{

	Fac[0] = Fac[1] = 1;

	for(int i = 2; i <= 20; i++)

		Fac[i] = Fac[i-1] * i;

}

//康托展开

inline LL cantor(vector<int>A, int n)//即求字典序小于此排列的个数

{

	LL ret = 0; //答案从0 ~ n!-1

	for(int i = 0; i < n; i++)

	{

		int k = 0;

		for(int j = i+1; j < n; j++)//求逆序对

			if(A[i] > A[j]) k++;

		ret += Fac[n-i-1] * k;

	}

	return ret;

}

//逆康托

vector<int> decantor(LL x, int n)

{

	vector<int>left, ret;

	for(int i = 1; i <= n; i++) left.push_back(i); //存剩下的数字

	for(int i = n; i >= 1; i--)

	{

		int q = x/Fac[i-1];

		x %= Fac[i-1];

		ret.push_back(left[q]);

		left.erase(left.begin()+q); //删除

	}

	return ret;

}

N的（随机/全）排列

//Random

srand(time(NULL));

int num[MAXN], n;

scanf("%d", &n);

for(int i = 1; i <= n; i++)

	num[i] = i;

random_shuffle(num + 1, num + n + 1);

for(int i = 1; i <= n; i++)

	printf("%d ", num[i]);

//All

int num[MAXN], n;

scanf("%d", &n);

for(int i = 1; i <= n; i++)

	num[i] = i;

do {

	for(int i = 1; i <= n; i++)

		printf("%d ", num[i]);

	putchar('\n');

}while(next_permutation(num + 1, num + n + 1));

N的R排列

int seq[MAXN], N, R;

inline void Print()

{

	for(int i = 1; i <= R; i++)

		printf("%d%c", seq[i], i == R ? '\n' : ' ');

}

bool vis[MAXN];

inline void dfs(int now) //N的R排列

{

	if(now > R)

	{

		Print();

		return;

	}

	for(int i = 1; i <= N; i++)

		if(!vis[i])

		{

			vis[i] = 1;

			seq[now] = i; dfs(now+1);

			vis[i] = 0;

		}

}

N的R排列（可重复）

int seq[MAXN], N, R;

inline void Print()

{

	for(int i = 1; i <= R; i++)

		printf("%d%c", seq[i], i == R ? '\n' : ' ');

}

inline void dfs(int now) //N的R排列(可重复)

{

	if(now > R)

	{

		Print();

		return;

	}

	for(int i = 1; i <= N; i++)

		seq[now] = i, dfs(now+1);

}

N的R组合（可重复）

int seq[MAXN], N, R;

inline void Print()

{

	for(int i = 1; i <= R; i++)

		printf("%d%c", seq[i], i == R ? '\n' : ' ');

}

inline void dfs(int now) //N的R组合(可重复)

{

	if(now > R)

	{

		Print();

		return;

	}

	for(int i = max(seq[now-1], 1); i <= N; i++)

		seq[now] = i, dfs(now+1);

}

第一类斯特林数(有/无符号)

LL Su[MAXN][MAXN]; //无符号第一类斯特林数

LL Ss[MAXN][MAXN]; //有符号第一类斯特林数

inline void init()

{

	Su[0][0] = 1; //CAUTION

	for(int i = 1; i < MAXN; i++) //即n个不同元素构成m个圆排列的方案数

	{

		Su[i][0] = 0; //CAUTION

		for(int j = 1; j <= i; j++)

			Su[i][j] = (Su[i-1][j-1] + Su[i-1][j]*(i-1)) % mod;

	}

	Ss[0][0] = 1; //CAUTION

	for(int i = 1; i < MAXN; i++)

	{

		Ss[i][0] = 0; //CAUTION

		for(int j = 1; j <= i; j++)

			Ss[i][j] = (Ss[i-1][j-1] - Ss[i-1][j]*(i-1)) % mod;

	}

}

“pascal”三角形

二项式系数可以构成一个杨辉三角（pascal三角形）。同样第一类Stirling数同样也可以构成一个三角，可以由此分析其性质。

	无符号Stirling数	有符号Stirling数
n=0	1	1
n=1	0 1	0 1
n=2	0 1 1	0 -1 1
n=3	0 2 3 1	0 2 -3 1
n=4	0 6 11 6 1	0 -6 11 -6 1
n=5	0 24 50 35 10 1	0 24 -50 35 -10 1
n=6	0 120 274 225 85 15 1	0 -120 274 -225 85 -15 1
n=7	0 720 1764 1624 735 175 21 1	0 720 -1764 1624 -735 175 -21 1

性质

无符号Stirling数有如下性质：

①

②

③

④

⑤

⑥

⑦

⑧

有符号stirling性质类似：

①

② ，注意

以上摘自万能的百度百科

第二类斯特林数

LL S[MAXN][MAXN];

inline void init()

{

	S[0][0] = 1;

	for(int i = 1; i < MAXN; i++)

	{

		S[i][0] = 0;

		for(int j = 1; j <= i; j++)

			S[i][j] = (S[i-1][j-1] + S[i-1][j] * j) %mod;

	}

}

“pascal”三角形

n=0	1
n=1	0 1
n=2	0 1 1
n=3	0 1 3 1
n=4	0 1 7 6 1
n=5	0 1 15 25 10 1
n=6	0 1 31 90 65 15 1
n=7	0 1 63 301 350 140 21 1
n=8	0 1 127 966 1701 1050 266 28 1
n=9	0 1 255 3025 7770 6951 2646 462 36 1

性质

① 注意

②

③

④

⑤

⑥

⑦

⑧

⑨ ，是贝尔数。

⑩ 由推出

其中Ⅰ. 实际上为【n个不同的球，放入m个有区别的盒子，允许盒子为空】的方案数

Ⅱ. 为【n个不同的球，放入m个无区别的盒子，允许盒子为空】的方案数

因为Ⅰ的盒子有区别，所以用Ⅱ乘上排列即为Ⅰ，Ⅰ= 。

又因为Ⅰ中每个球有m种选择且相互独立，Ⅰ=

∵Ⅰ = Ⅰ

∴

推论

(1) 若n<m，，因为S(n, m) = 0

(2) ，因为S(m, m) = 1

以上摘自万能的百度百科

贝尔数

LL B[MAXN];

void init()

{

	for(int i = 1; i < MAXN; i++)

	{

		for(int j = 0; j < i; j++) //CAUTION

			B[i] = (B[i] + B[j]*C(i, j))%mod;//C -> 组合数

					or

		for(int j = 1; j <= i; j++) //CAUTION

			B[i] = (B[i] + S(i, j))%mod;//S -> 第二类斯特林数

	}

}

//同时适合"Touchard同余"

//B(n+p) ≡ B(n) + B(n+1) (mod p)

Lucas定理

// C(n, m) ≡ C(n/p, m/p) * C(n%p, m%p) (mod p) p为质数

LL Lucas(LL n, LL m, LL p)

{

	return Lucas(n/p, m/p) * C(n%p, m%p) % p;

}

枚举子集(二进制输出)

int s, all;

scanf("%d", &all); s = all;

do {

	cout<<bitset<N>(s)<<endl;

}while(s && (--s&=all, 1));

巴特西

NOIP2018模板总结【数学】

质因数分解

线性筛素数/欧拉函数

Miller-Robin大素数测试/快速幂/快速乘

gcd & lcm

exgcd

中国剩余定理

卡特兰数

康托展开式

N的（随机/全）排列

N的R排列

N的R排列（可重复）

N的R组合（可重复）

第一类斯特林数(有/无符号)

“pascal”三角形

性质

第二类斯特林数

“pascal”三角形

性质

推论

贝尔数

Lucas定理

枚举子集(二进制输出)

最新文章

热门文章