NOIP2018模板总结【数学】

质因数分解

//质因数分解
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;//						orfor(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);//						orreturn (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!-1for(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; //CAUTIONfor(int i = 1; i < MAXN; i++) //即n个不同元素构成m个圆排列的方案数{Su[i][0] = 0; //CAUTIONfor(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; //CAUTIONfor(int i = 1; i < MAXN; i++){Ss[i][0] = 0; //CAUTIONfor(int j = 1; j <= i; j++)Ss[i][j] = (Ss[i-1][j-1] - Ss[i-1][j]*(i-1)) % mod;}
}

“pascal”三角形

二项式系数  可以构成一个杨辉三角（pascal三角形）。同样第一类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;}
}

性质

① 注意  

② 

③ 

④ 

⑤ 

⑥ 

⑦ 

⑧ 

⑨  ，  是贝尔数。

⑩    由    推出

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

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

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

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

                ∵Ⅰ = Ⅰ

                ∴  

LL B[MAXN];
void init()
{for(int i = 1; i < MAXN; i++){for(int j = 0; j < i; j++) //CAUTIONB[i] = (B[i] + B[j]*C(i, j))%mod;//C -> 组合数orfor(int j = 1; j <= i; j++) //CAUTIONB[i] = (B[i] + S(i, j))%mod;//S -> 第二类斯特林数}
}
//同时适合"Touchard同余"
//B(n+p) ≡ B(n) + B(n+1) (mod p)

// 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));