OI数学入门

模运算

//加法 
x=(a+b)%p;
x=(0ll+a+b+c)%p;
x=((a+b)%p+c)%p;
//减法 
x=((a-b)%p+p)%p;
//乘法 
x=1ll*a*b%p;
x=1ll*a*b%p*c%p;

高精度：
正数的高精度读入，输出，储存，和 \(+,-,\times\) 运算。
代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
struct gaojing{
	int n;//n 代表这个数的位数
	int a[MAXN];//a[i] 代表这个数的第 i 位是多少
	//个位在 a[1]
	char s[MAXN];//读入的
	gaojing(){
		n=1;
		memset(a,0,sizeof(a));
	}
	void read(){
		cin>>s+1;
		n=strlen(s+1);
		for(int i=1,j=n;i<=n;i++,j--)
			a[i]=s[j]-'0'; 
	}
	void print(){
		for(int i=n;i>=1;i--)
			cout<<a[i];
	}
};
gaojing operator+(const gaojing &a,const gaojing &b){
	gaojing c;
	c.n=max(a.n,b.n);	
	for(int i=1;i<=c.n;i++){
		c.a[i]+=a.a[i]+b.a[i];
		c.a[i+1]+=c.a[i]/10;
		c.a[i]=c.a[i]%10;
	}	
	if(c.a[c.n+1])c.n++;
	return c;
}
gaojing operator-(const gaojing &a,const gaojing &b){
	gaojing c;
	c.n=max(a.n,b.n);
	for(int i=1;i<=c.n;i++){
		c.a[i]+=a.a[i]-b.a[i];		
		if(c.a[i]<0){
			c.a[i]+=10;
			c.a[i+1]--;
		}
	}	
	while(c.n>1&&!c.a[c.n])
		c.n--;
	return c;
}
gaojing operator*(const gaojing &a,const gaojing &b){
	gaojing c;
	c.n=a.n+b.n;
	for(int i=1;i<=a.n;i++)
		for(int j=1;j<=b.n;j++)
			c.a[i+j-1]+=a.a[i]*b.a[j];
	for(int i=1;i<=c.n;i++){
		c.a[i+1]+=c.a[i]/10;
		c.a[i]=c.a[i]%10;
	}
	while(c.n>1&&!c.a[c.n])
		c.n--;
	return c;
}
signed main(){
	gaojing a,b,c;
	a.read();
	b.read();
	c=a+b;
	c.print();
	putchar('\n');
	c=a*b;
	c.print();
	putchar('\n');
	c=a-b;
	c.print();
	return 0;
}

素数：
定义：除了自己和他本身没有其他因数的数。

组合数：
加法原理：不能同时选
乘法原理：可以同时选

排列：顺序不同，方案不同
一个排列数，表示为 \(P^n_m\)
如 \(P^3_2 = 6\)
所有方案：
\(1\) \(2\)
\(1\) \(3\)
\(2\) \(1\)
\(2\) \(3\)
\(3\) \(1\)
\(3\) \(2\)
求排列数公式
\(P^n_m = n(n-1)(n-2)...(n-m+1) = \frac {n!}{(n-m!)}\)

组合：数相同，顺序不同，方案相同

组合数表示为：\(C^n_m\) （在 \(n\) 个数中选 \(m\) 个数）
求组合数公式：\(C^n_m = \frac {n!}{m!(n-m)!}\)

组合数的性质：$C^n_m = C^{(n-1)}_{(m-1)} + C^{n-1}_m $

\(C^n_n = 1\)

\(C^n_0 = 1\)
\(n\) 个数中选 \(n\) 个数或 \(0\) 个数，只有一种选法。

杨辉三角:
第 \(n+1\) 行的第i个数等于第 \(n\) 行的第 \(i-1\) 个数和第 \(i\) 个数之和，这也是组合数的性质之一。即 \(C_{n+1}^i = C_n^i + C_n^{i-1}\)。

从 \(n\) 个数中选奇数个数和偶数个数的方案数相等

证明见 排列DP 中的例题：求逆序对。

用递推求组合数Code：

#include<bits/stdc++.h>
using namespace std;
int C[1005][1005];
//C(i,j) 0<=i<=n,0<=j<=i 要求这个范围的组合数
signed main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++){
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++)
			C[i][j]=C[i-1][j-1]+C[i-1][j];
	}
	cout<<C[n][m];
	return 0;
}