buerdepepeqi的模板
头文件
#include#include
数学
费马小定理
a是不能被质数p整除的正整数，则有a^(p-1)≡ 1 mod p,即a^(p-1) mod p=1;推论：对于不能被质数p整除的正整数a，有a^p≡ a mod pa^b%p=a^(b%(p-1))%p
逆元
/*O(n)打表求1~n的逆元*/LL inv[maxn];void init() { inv[1] = 1; for (int i = 2; i < maxn; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;} 矩阵快速幂
struct matrix {//矩阵 int n;//长 int m;//宽 long long a[105][105]; matrix() {//构造函数 n = 2; m = 2; memset(a, 0, sizeof(a)); } matrix(int x, int y) { n = x; m = y; memset(a, 0, sizeof(a)); } void print() { for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { printf("%d ", a[i][j]); } printf("\n"); } } void setv(int x) {//初始化 if(x == 0) { memset(a, 0, sizeof(a)); } if(x == 1) { memset(a, 0, sizeof(a)); for(int i = 1; i <= n; i++) a[i][i] = 1; } } friend matrix operator *(matrix x, matrix y) { //矩阵乘法 matrix tmp = matrix(x.n, y.m); for(int i = 1; i <= x.n; i++) { for(int j = 1; j <= y.m; j++) { tmp.a[i][j] = 0; for(int k = 1; k <= y.n; k++) { tmp.a[i][j] += (x.a[i][k] * y.a[k][j]) % mod; } tmp.a[i][j] %= mod; } } return tmp; }};matrix fast_pow(matrix x, long long k) { //矩阵快速幂 matrix ans = matrix(n, n); ans.setv(1);//初始化为1 while(k > 0) { //类似整数快速幂 if(k & 1) { ans = ans * x; } k >>= 1; x = x * x; } return ans;} 欧拉定理和欧拉函数
欧拉函数phi(m)：当m>1是，phi(m)表示比m小且与m互质的正整数个数欧拉定理：a^phi(n) = 1 mod na^x = a^(x % phi(p) + p) (mod p)//打表int b[N],prime[N],phi[N];void init(){ //求欧拉函数和素数 int i,j,k,c=0; memset(b,0,sizeof(b)); for(i=2;i 1 ? res / n * (n - 1) : res;}//欧拉函数递归调用//计算dp[i] = 2^dp[i+1] % mod，需要先计算mod的phi，以及phi(mod)的phi直到为1//dp[i] = 2^(dp[i+1]%phi(mod)+phi(mod)) %modconst int MX = 1e5 + 5;const ll mod = 1e9 + 7;ll m[50], dp[MX][50];int sz, n;int Phi (int n) { int res = n; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) { res -= res / i; while (n % i == 0) n /= i; } } return n > 1 ? res / n * (n - 1) : res;}void init() { int x = mod; sz = 0; m[++sz] = x; while (x != 1) m[++sz] = Phi (x), x = m[sz], cout << x << endl;}ll pow (ll a, ll b, ll m) { ll ret = 1; while (b) { if (b & 1) ret = ret * a % m; a = a * a % m; b >>= 1; } return ret;}int main() { init(); for (int i = 1; i <= n; i++) { for (int j = 1; j < sz; j++) { dp[i][j] = pow (2ll, dp[i - 1][j + 1], m[j]) * 3 - 3; while (dp[i][j] < 0) dp[i][j] += m[j]; while (dp[i][j] >= m[j]) dp[i][j] -= m[j]; } } printf ("%lld\n", dp[n][1] % m[1]);} 扩展欧几里得定理
//递归LL ex_gcd(LL a, LL b, LL &x, LL &y) { if(b == 0) { x = 1, y = 0; return a; } int d = ex_gcd(b, a % b, x, y); int z = x; x = y; y = z - y * (a / b); return d;}//非递归//返回值为 gcd 以及 a,b 的系数pair exgcd(ll a,ll b){ valarray equation[2] = { {a,1,0},{b,0,1}}; while (equation[1][0]) { ll q = equation[0][0]/equation[1][0]; equation[0] -= q * equation[1]; swap(equation[0], equation[1]); } return MP(equation[0][0],MP(equation[0][1],equation[0][2]));} 组合数
1、普通组合数
void gcd(LL a, LL b, LL &d, LL &x, LL &y) { if(!b) { d = a; x = 1; y = 0; } else { gcd(b, a % b, d, y, x); y -= x * (a / b); }}LL inv(LL a, LL n) { LL d, x, y; gcd(a, n, d, x, y); return (x % n + n) % n;}LL fac[maxn], fav[maxn];LL C(LL n, LL m) { return fac[n] * fav[m] % mod * fav[n - m] % mod;}void init() { fac[0] = 1; fav[0] = 1; for(int i = 1; i < maxn; i++)fac[i] = fac[i - 1] * i % mod; for(int i = 1; i < maxn; i++)fav[i] = inv(fac[i], mod);} 2、Lucas组合数
LL p;LL n, m;LL fac[maxn];LL pow(LL y, int z, int p) { y %= p; LL ans = 1; for(int i = z; i; i >>= 1, y = y * y % p)if(i & 1)ans = ans * y % p; return ans;}LL C(LL n, LL m) { if(m > n)return 0; return ((fac[n] * pow(fac[m], p - 2, p)) % p * pow(fac[n - m], p - 2, p) % p);}LL Lucas(LL n, LL m) { if(!m)return 1; return C(n % p, m % p) * Lucas(n / p, m / p) % p;}int main() { scanf("%lld%lld%lld", &n, &m, &p); fac[0] = 1; for(int i = 1; i <= p; i++) { fac[i] = fac[i - 1] * i % p; } printf("%lld\n", Lucas(n, m) ); return 0;} 3、卡特兰数
卡特兰数是一种经典的组合数，经常出现在各种计算中，其前几项为 :
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...\[ C_n=\frac{(2n)!}{(n+1)!n!} \]卡特兰数满足如下递归
\[ C_0=0\quad and \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n\\ C_0=1\quad and \quad C_{n+1}=\sum_{i=0}^{n}C_iC_{n-i}\quad n>=0 \] 卡特兰数的渐进增长为\[ C_n=> \frac{4^n}{n^{3/2}\sqrt{\pi}} \]所有的奇卡塔兰数Cn都满足n = 2^k − 1。所有其他的卡塔兰数都是偶数。卡特兰数的经典问题
- n个左括号与n个右括号组成的合法序列的数量为卡特兰数
- 1，2，···，n经过一个栈，形成的合法的出栈序列的数量为卡特兰数
- n个节点构成不同的二叉树的数量为卡特兰数
- 在平面直角坐标系上，每一步只能向上走或向右走，从（0，0）走到（n，n）并且除了两个端点外不能接触直线y=x的路线数量为2*Cat_n-1
- Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数
- Cn表示集合{1, …, n}的不交叉划分的个数. 其中每个段落的长度为2
- Cn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数 下图为 n = 4的情况:
４、错排公式
\[ D(n)=(n-1)*[D(n-1) +D(n-2)] \]
约瑟夫环
//最后一个报号的人int main(){ int n, m, i, s = 0; scanf("%d%d", &n, &m); for (i = 2; i <= n; i++) s = (s + m) % i; printf ("\nThe winner is %d\n", s+1);}//第k个出去的人#include using namespace std; int main(){ int n,k; while(scanf("%d%d",&n,&k)==2){//n个人第k个人走，最后一个人是谁 int t; scanf("%d",&t); while(t--){ int q; scanf("%d",&q); long long N = (long long)q*k; while(N>n){ N = (N-n-1)/(k-1)+N-n; } printf("%d%c",(int)N," \n"[!t]); } } return 0;} 莫比乌斯函数
//线性筛求莫比乌斯函数int mu[maxn];int prime[maxn];int not_prime[maxn];int n,tot;void Mobiwus(){ mu[1] = 1; for(int i = 2; i <= n; i++) { if(!not_prime[i]) { prime[++tot] = i; mu[i] = -1; } for(int j = 1; prime[j]*i <= n; j++) { not_prime[prime[j]*i] = 1; if(i % prime[j] == 0) { mu[prime[j]*i] = 0; break; } mu[prime[j]*i] = -mu[i]; } }} BM递推式
namespace linear_seq {#define pb push_back#define SZ(x) ((int)(x).size())#define rep(i,a,b) for(int i=(a);i<(b);++i)#define per(i,a,b) for(int i=(a)-1;i>=(b);--i) typedef vector VI; const int N = 10010; const LL mod = 1e9 + 7; LL res[N], base[N], cnt[N], val[N]; LL power(LL a, LL b) { LL ret = 1; a %= mod; while(b) { if(b & 1)ret = ret * a % mod; a = a * a % mod; b >>= 1; } return ret; } vector v; void mul(LL *a, LL *b, int k) { rep(i, 0, k + k) cnt[i] = 0; rep(i, 0, k) if (a[i]) rep(j, 0, k) cnt[i + j] = (cnt[i + j] + a[i] * b[j]) % mod; per(i, k + k, k) if (cnt[i]) rep(j, 0, SZ(v)) cnt[i - k + v[j]] = (cnt[i - k + v[j]] - cnt[i] * val[v[j]]) % mod; rep(i, 0, k) a[i] = cnt[i]; } int solve(LL n, VI a, VI b) { // a系数 b初值 b[n+1]=a[0]*b[n]+... LL ans = 0, pnt = 0; int k = SZ(a); rep(i, 0, k) val[k - 1 - i] = -a[i]; val[k] = 1; v.clear(); rep(i, 0, k) if (val[i] != 0) v.push_back(i); rep(i, 0, k) res[i] = base[i] = 0; res[0] = 1; while ((1LL << pnt) <= n) pnt++; per(p, pnt + 1, 0) { mul(res, res, k); if ((n >> p) & 1) { per(i, k, 0) res[i + 1] = res[i]; res[0] = 0; rep(j, 0, SZ(v)) res[v[j]] = (res[v[j]] - res[k] * val[v[j]]) % mod; } } rep(i, 0, k) ans = (ans + res[i] * b[i]) % mod; if (ans < 0) ans += mod; return ans; } VI BM(VI s) { VI C(1, 1), B(1, 1); int L = 0, m = 1, b = 1; rep(n, 0, SZ(s)) { LL d = 0; rep(i, 0, L + 1) d = (d + (LL)C[i] * s[n - i]) % mod; if (d == 0) ++m; else if (2 * L <= n) { VI T = C; LL c = mod - d * power(b, mod - 2) % mod; while (SZ(C) < SZ(B) + m) C.pb(0); rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod; L = n + 1 - L; B = T; b = d; m = 1; } else { LL c = mod - d * power(b, mod - 2) % mod; while (SZ(C) < SZ(B) + m) C.pb(0); rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod; ++m; } } return C; } int gao(VI a, LL n) { VI c = BM(a); c.erase(c.begin()); rep(i, 0, SZ(c)) c[i] = (mod - c[i]) % mod; return solve(n, c, VI(a.begin(), a.begin() + SZ(c))); }};//用法vector v;//打表填系数递推//linear_seq::gao(v, n - 1) 字符串
马拉车
struct Manacher { int p[maxn << 1], str[maxn << 1]; bool check(int x) { return x - (x & -x) == 0; } bool equal(int x, int y) { if ((x & 1) != (y & 1)) return false; return (x & 1) || (check(mask[x >> 1]) && check(mask[y >> 1]) && str[x] == str[y]); } int solve(int len) { int max_right = 0, pos = 0, ret = 0; for (int i = 1; i <= len; i++) { p[i] = (max_right > i ? std::min(p[pos + pos - i], max_right - i) : 1); if ((i & 1) || check(mask[i >> 1])) { while (equal(i + p[i], i - p[i])) p[i]++; if (max_right < i + p[i]) pos = i, max_right = i + p[i]; ret += p[i] / 2; } else p[i] = 2; } return ret; }} manacher; 图论
三元环
#includeusing namespace std;const int N = 1e5 + 10;vector g[N];int deg[N], vis[N], n, m, ans;struct E { int u, v; } e[N * 3];int main() { scanf("%d%d", &n, &m); for(int i = 1 ; i <= m ; ++ i) { scanf("%d%d", &e[i].u, &e[i].v); ++ deg[e[i].u], ++ deg[e[i].v]; } for(int i = 1 ; i <= m ; ++ i) { int u = e[i].u, v = e[i].v; if(deg[u] < deg[v] || (deg[u] == deg[v] && u > v)) swap(u, v); g[u].push_back(v); } for(int x = 1 ; x <= n ; ++ x) { for(auto y: g[x]) vis[y] = x; for(auto y: g[x]) for(auto z: g[y]) if(vis[z] == x) ++ ans; } printf("%d\n", ans);}
小技巧
二进制状态压缩
\[ 取出整数n在二进制表示下的第k位：(n>>k)\&1\\ 取出整数n在二进制表示下的第0 \sim k-1位（后k位）:n\&((1<<k)-1)\\ 把整数n在二进制表示下第k位取反:n\quad xor\quad(1<<k)\\ 对整数n在二进制下表示的第k位赋值1：n|(1<<k)\\ 对整数n在二进制表示下的第k为赋值0：n\&(\sim(1<<k))\\ \]
rope的用法
头文件：#include
命名空间using namespace __gnu_cxx;
定义:rope r;
insert(pos, s)将字符串s插入pos位置
erase(pos, num)从pos开始删除num个字符
copy(pos, len, s)从pos开始len个字符用s代替
substr(pos, len)提取pos开始的len个字符
at(x)访问第x个元素