## 基础 ### 一些函数 1. `__builtin_ctz/__builtin_ctzll` 二进制末尾零的个数，不能传入0（f(12)=2） 2. `__builtin_ffs/__builtin_ffsll` 二进制最低位1的位置，0返回0（f(12)=3） 3. `__builtin_popcount/__builtin_popcountll` 求二进制中 1 的个数 4. `__builtin_parity/__builtin_parityll` 二进制下 `1` 的个数 mod 2 5. `__builtin_clz/__builtin_clzll` 二进制下前导 0 的个数，最高位位置/floor(log2(x))=`31-__builtin_clz(x)` 或 `63-__builtin_clzll(x)` 6. `__gcd` 求 $\gcd$，最好不要用 7. `iota(a+1,a+n+1,x)` 表示令a[1]=x,a[i]=a[i-1]+1($1<i\le n$） 8. `fill(a+1, a+n+1, x)` 表示令a[1~n]=x 9. `next_permutation(p+1, p+n+1);` 下一组排列（不止可以用在排列上，初始时升序，最后降序） ### 关闭同步流+cout 保留小数 ```cpp ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout<<fixed<<setprecision(2)<<acos(-1)<<"\n"; ``` ### 离散化 ```cpp for (int i=1; i<=n; i++) a[i]=c[i]=read(); for (int i=1; i<=m; i++) b[i]=c[n+i]=read(); sort(c+1, c+n+m+1); l=unique(c+1, c+n+m+1)-(c+1); for (int i=1; i<=n; i++) a[i]=lower_bound(c+1, c+l+1, a[i])-c; for (int i=1; i<=m; i++) b[i]=lower_bound(c+1, c+l+1, b[i])-c; ``` ### 修改栈空间 `-Wl,--stack=536870912 -O2 -std=c++23` ### 小根堆 `priority_queue<int, vector<int>, greater<int>> q;` ### sort 从大到小排序 `sort(q.begin(), q.end(), greater<int>());` `sort(q.begin(), q.end(), [](PII a, PII b) { return a.first>b.first; });` ### 整数除法上取整/下取整（整型默认是向零取整，也可转double/long double直接用自带函数） ```cpp int ceil(int x, int y) { if (y<0) x=-x, y=-y; return x>=0 ? (x+y-1)/y : x/y; } int floor(int x, int y) { if (y<0) x=-x, y=-y; return x>=0 ? x/y : (x-y+1)/y; } ``` ### 运算符重载 ```cpp struct node { int x, y, z; bool operator < (const node &a) const { return z<a.z; } } e[M]; ``` ### 模拟退火 ```cpp void sa() { ans=calc();//计算初始状态 for (double t=1000; t>1e-10; t*=0.997) {//初始温度、末温度、降温参数根据题目修改 ......//产生一个新的状态，如果类似函数的问题则转移距离要和当前温度有关 double/int/... now=calc(), d=now-ans; //计算新状态的价值和差距 if (d<0) ans=now, ......;//如果更优直接到新的状态并更新状态 if (exp(-1.0*d/t)*RAND_MAX>rand()) ......//如果在一定容差范围内则接受新状态 } } ``` ### CDQ 分治实现三维数点 ```cpp void add(int x, int y) { while (x<N) { c[x]+=y; x+=x&-x; } } int ask(int x) { int r=0; while (x) { r+=c[x]; x-=x&-x; } return r; } int cdq(int l, int r) { if (l==r) return 0; int mid=l+r>>1; int ans=cdq(l, mid)+cdq(mid+1, r); sort(t+l, t+mid+1, [](node x, node y) {return x.b<y.b || x.b==y.b && x.c<y.c;}); sort(t+mid+1, t+r+1, [](node x, node y) {return x.b<y.b || x.b==y.b && x.c<y.c;}); int j=l; for (int i=mid+1; i<=r; i++) { while (j<=mid && t[j].b<=t[i].b) { add(t[j].c, 1); j++; } ans+=ask(t[i].c); } for (int i=l; i<j; i++) add(t[i].c, -1); return ans; } sort(t+1, t+n+1, [](node x, node y) {return x.a<y.a || x.a==y.a && (x.b<y.b || x.b==y.b && x.c<y.c);}); // 严格小于时需按照 a 升，b 降，c 降来排序 ans=cdq(1, n); ``` ## stl & ext & pb_ds ### bitset - `count()`: 返回 `true` 的数量。 - `size()`: 返回 `bitset` 的大小。 - `test(pos)`: 它和 `vector` 中的 `at()` 的作用是一样的，和 `[]` 运算符的区别就是越界检查。 - `any()`: 若存在某一位是 `true` 则返回 `true`，否则返回 `false`。 - `none()`: 若所有位都是 `false` 则返回 `true`，否则返回 `false`。 - `all()`: 若所有位都是 `true` 则返回 `true`，否则返回 `false`。 - 1. `set()`: 将整个 `bitset` 设置成 `true`。 2. `set(pos, val = true)`: 将某一位设置成 `true`/`false`。 - 1. `reset()`: 将整个 `bitset` 设置成 `false`。 2. `reset(pos)`: 将某一位设置成 `false`。相当于 `set(pos, false)`。 - 1. `flip()`: 翻转每一位。（$0\leftrightarrow1$，相当于异或一个全是 $1$ 的 `bitset`） 2. `flip(pos)`: 翻转某一位。 - `to_string()`: 返回转换成的字符串表达。 - `to_ulong()`: 返回转换成的 `unsigned long` 表达（`long` 在 NT 及 32 位 POSIX 系统下与 `int` 一样，在 64 位 POSIX 下与 `long long` 一样）。 - `to_ullong()`:（**C++11** 起）返回转换成的 `unsigned long long` 表达。 另外，libstdc++ 中有一些较为实用的内部成员函数[^bitset1]： - `_Find_first()`: 返回 `bitset` 第一个 `true` 的下标，若没有 `true` 则返回 `bitset` 的大小。 - `_Find_next(pos)`: 返回 `pos` 后面（下标严格大于 `pos` 的位置）第一个 `true` 的下标，若 `pos` 后面没有 `true` 则返回 `bitset` 的大小。 ### set/multiset/unordered_set/unordered_multiset * `insert(x)` 当容器中没有等价元素的时候，将元素 x 插入到 `set` 中。 * `erase(x)` 删除值为 x 的 **所有** 元素，返回删除元素的个数。 * `erase(pos)` 删除迭代器为 pos 的元素，要求迭代器必须合法。 * `erase(first,last)` 删除迭代器在 [first,last) 范围内的所有元素。 * `clear()` 清空 `set`。 * `count(x)` 返回 `set` 内键为 x 的元素数量。 * `find(x)` 在 `set` 内存在键为 x 的元素时会返回该元素的迭代器，否则返回 `end()`。 * `lower_bound(x)` 返回指向首个不小于给定键的元素的迭代器。如果不存在这样的元素，返回 `end()`。 * `upper_bound(x)` 返回指向首个大于给定键的元素的迭代器。如果不存在这样的元素，返回 `end()`。 **一定要用自带的** * `empty()` 返回容器是否为空。 * `size()` 返回容器内元素个数。 ### map/multimap/unordered_map/unordered_multimap * 可以直接通过下标访问来进行查询或插入操作。例如 `mp["Alan"]=100`。 * 通过向 `map` 中插入一个类型为 `pair<Key, T>` 的值可以达到插入元素的目的，例如 `mp.insert(pair<string,int>("Alan",100));`； * `erase(key)` 函数会删除键为 `key` 的 **所有** 元素。返回值为删除元素的数量。 * `erase(pos)`: 删除迭代器为 pos 的元素，要求迭代器必须合法。 * `erase(first,last)`: 删除迭代器在 [first,last) 范围内的所有元素。 * `clear()` 函数会清空整个容器。 * `count(x)`: 返回容器内键为 x 的元素数量。复杂度为 O(\log(size)+ans)（关于容器大小对数复杂度，加上匹配个数）。 * `find(x)`: 若容器内存在键为 x 的元素，会返回该元素的迭代器；否则返回 `end()`。 * `lower_bound(x)`: 返回指向首个不小于给定键的元素的迭代器。 * `upper_bound(x)`: 返回指向首个大于给定键的元素的迭代器。若容器内所有元素均小于或等于给定键，返回 `end()`。 * `empty()`: 返回容器是否为空。 * `size()`: 返回容器内元素个数。 ### rope ```cpp #include <ext/rope> using namespace __gnu_cxx; ``` - `rope<int> a` 初始化 `rope`（与 `vector` 等容器很相似） - `a.push_back(x)` 在 `a` 的末尾添加元素 `x` - `a.insert(pos, x)` 在 `a` 的 `pos` 个位置添加元素 `x` - `a.erase(pos, x)` 在 `a` 的 `pos` 个位置删除 `x` 个元素 - `a.at(x)` 或 `a[x]` 访问 `a` 的第 `x` 个元素 - `a.length()` 或 `a.size()` 获取 `a` 的大小 - `a.replace(pos, x)` 将 `a` 的 `pos` 个位置的元素修改成 `x` - `a.substr(pos, x)` 从 `a` 的第 `pos` 位开始的 `x` 个元素 ### tree（带排名的平衡树） ```cpp #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; ``` 定义： ```cpp typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; ordered_set t; ``` - `t.insert(x)` / `t.erase(x)` / `t.upper_bound(x)` / `t.lower_bound(x)` 用法与 `set` 一致 - `t.find_by_order(k)` 返回指向排名为 `k` 的元素的**迭代器**（0-indexed，第 0 名为最小） - `t.order_of_key(k)` 返回比 `x` **小**的元素的个数（即 `x` 的排名） **eg**（用 pair 实现对重复数据的处理） 1. 插入 $x$ 数 2. 删除 $x$ 数(若有多个相同的数，应只删除一个) 3. 查询 $x$ 数的排名(排名定义为比当前数小的数的个数 $+1$ ) 4. 查询排名为 $x$ 的数 5. 求 $x$ 的前驱(前驱定义为小于 $x$，且最大的数) 6. 求 $x$ 的后继(后继定义为大于 $x$，且最小的数) ```cpp #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } int n, cnt; tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> t; int main() { n=read(); while (n--) { int op=read(), x=read(); if (op==1) t.insert({x, ++cnt}); if (op==2) t.erase(t.lower_bound({x, 0})); if (op==3) printf("%d\n", t.order_of_key({x, 0})+1); if (op==4) printf("%d\n", t.find_by_order(x-1)->first); if (op==5) printf("%d\n", (--t.lower_bound({x, 0}))->first); if (op==6) printf("%d\n", t.lower_bound({x, cnt+1})->first); } return 0; } ``` ### gp_hash_table / cc_hash_table 哈希表 （与 `unordered_map` 用法相同更快） `gp_hash_table` 更小更快 ```cpp #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; gp_hash_table<string, int> h; ``` ### priority_queue 配对堆（可并堆） ```cpp #include <ext/pb_ds/priority_queue.hpp> using namespace __gnu_pbds; typedef priority_queue<int, less<int>, pairing_heap_tag> pbds_pq; ``` 用法基本和 `stl` 中的 `priority_queue` 相同 合并 `pq2` 到 `pq1`，`pq2` 变为空，时间复杂度 $O(1)$ ```cpp pbds_pq pq1; pq1.push(10); pq1.push(30); pbds_pq pq2; pq2.push(20); pq2.push(40); pq1.join(pq2); ``` ## 数据结构 ### RMQ ```cpp for (int j=1; j<=lg[n]; j++) for (int i=1; i<=n-(1<<j)+1; i++) f[i][j]=max(f[i][j-1], f[i+(1<<j-1)][j-1]); for (int i=1; i<=m; i++) { int x=read(), y=read(), z=lg[y-x]; printf("%d\n", max(f[x][z], f[y-(1<<z)+1][z])); } ``` ### 笛卡尔树 ```cpp for (int i=1; i<=n; i++) { while (!s.empty() && a[s.top()]>a[i]) l[i]=s.top(), s.pop(); if (!s.empty()) r[s.top()]=i; s.push(i); } ``` ### 树状数组 ```cpp struct fenwick { int n, c[N]; void clear(int _n) { n=_n; fill(c+1, c+n+1, 0); } void add(int x, int y) { while (x<=n) { c[x]+=y; x+=x&-x; } } int ask(int x) { int r=0; while (x) { r+=c[x]; x-=x&-x; } return r; } int ask(int l, int r) { return ask(r)-ask(l-1); } int kth(int k) { int x=0, sum=0, step=1; while ((step<<1)<=n) step<<=1; while (step) { int nxt=x+step; if (nxt<=n && sum+c[nxt]<k) { x=nxt; sum+=c[nxt]; } step>>=1; } return x+1; } } C; ``` ### 树状数组 区间加、区间和 ```cpp void addd(int x, int v) { int y=x; while (x<=n) { c1[x]+=v; c2[x]+=(y-1)*v; x+=x&-x; } } int askk(int x) { int r=0, y=x; while (x) { r+=c1[x]*y-c2[x]; x-=x&-x; } return r; } void add(int l, int r, int v) {addd(l, v), addd(r+1, -v);} int ask(int l, int r) {return askk(r)-askk(l-1);} ``` ### 分块 ```cpp void add(int l, int r, int c) { int p1=id[l], p2=id[r]; if (p1==p2) { for (int i=l; i<=r; i++) a[i]+=c, s[p1]+=c; return; } for (int i=l; id[i]==p1; i++) a[i]+=c, s[p1]+=c; for (int i=p1+1; i<=p2-1; i++) b[i]+=c, s[i]+=len*c; for (int i=r; id[i]==p2; i--) a[i]+=c, s[p2]+=c; } int ask(int l, int r, int c) { int p1=id[l], p2=id[r], ans=0; if (p1==p2) { for (int i=l; i<=r; i++) ans=(ans+a[i]+b[p1])%c; return ans; } for (int i=l; id[i]==p1; i++) ans=(ans+a[i]+b[p1])%c; for (int i=p1+1; i<=p2-1; i++) ans=(ans+s[i])%c; for (int i=r; id[i]==p2; i--) ans=(ans+a[i]+b[p2])%c; return ans; } { scanf("%lld", &n), len=sqrt(n); for (int i=1; i<=n; i++) { scanf("%lld", &a[i]); id[i]=(i-1)/len+1; s[id[i]]+=a[i]; } for (int i=1; i<=n; i++) { scanf("%lld%lld%lld%lld", &op, &l, &r, &c); if (op==0) add(l, r, c); else printf("%lld\n", ask(l, r, c+1)); } return 0; } ``` ### 莫队 ```cpp struct node { int l, r, id; bool operator < (const node &b) const { return l/len==b.l/len ? r<b.r : l<b.l; } } a[N]; sort(a+1, a+m+1); for (int i=1, l=1, r=0; i<=m; i++) { while (r<a[i].r) add(c[++r]); while (r>a[i].r) del(c[r--]); while (l<a[i].l) del(c[l++]); while (l>a[i].l) add(c[--l]); } ``` ### 线段树 ```cpp struct seg { int s[N*4], t1[N*4], t2[N*4]; void build(int p, int l, int r) { s[p]=t1[p]=0, t2[p]=1; if (l==r) return s[p]=a[l]%P, void(); int mid=l+r>>1; build(lp, l, mid); build(rp, mid+1, r); s[p]=(s[lp]+s[rp])%P; } void pushdown(int p, int l, int r) { int mid=l+r>>1; s[lp]=(s[lp]*t2[p]+t1[p]*(mid-l+1))%P; s[rp]=(s[rp]*t2[p]+t1[p]*(r-mid))%P; t2[lp]=(t2[lp]*t2[p])%P; t2[rp]=(t2[rp]*t2[p])%P; t1[lp]=(t1[lp]*t2[p]+t1[p])%P; t1[rp]=(t1[rp]*t2[p]+t1[p])%P; t1[p]=0, t2[p]=1; } void mul(int p, int l, int r, int L, int R, int k) { if (L<=l && r<=R) { t1[p]=t1[p]*k%P; t2[p]=t2[p]*k%P; s[p]=s[p]*k%P; return; } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) mul(lp, l, mid, L, R, k); if (R>mid) mul(rp, mid+1, r, L, R, k); s[p]=(s[lp]+s[rp])%P; } void add(int p, int l, int r, int L, int R, int k) { if (L<=l && r<=R) { s[p]=(s[p]+k*(r-l+1))%P; t1[p]=(t1[p]+k)%P; return; } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) add(lp, l, mid, L, R, k); if (R>mid) add(rp, mid+1, r, L, R, k); s[p]=(s[lp]+s[rp])%P; } int ask(int p, int l, int r, int L, int R) { if (L<=l && r<=R) return s[p]; pushdown(p, l, r); int mid=l+r>>1, res=0; if (L<=mid) res+=ask(lp, l, mid, L, R); if (R>mid) res+=ask(rp, mid+1, r, L, R); return res%P; } } S; ``` ### 线段树（区间加、赋值） ```cpp struct seg { int s[N*4], mn[N*4], t1[N*4], t2[N*4]; void pushup(int p) { s[p]=s[lp]+s[rp]; mn[p]=min(mn[lp], mn[rp]); } void build(int p, int l, int r) { t1[p]=-1;//assign lazy tag t2[p]=0;//add lazy tag if (l==r) { s[p]=mn[p]=a[l]; return; } int mid=l+r>>1; build(lp, l, mid); build(rp, mid+1, r); pushup(p); } void pushdown(int p, int l, int r) { int mid=l+r>>1; if (t1[p]!=-1) { Assign(lp, l, mid, t1[p]); Assign(rp, mid+1, r, t1[p]); t1[p]=-1; } if (t2[p]!=0) { Add(lp, l, mid, t2[p]); Add(rp, mid+1, r, t2[p]); t2[p]=0; } } void Assign(int p, int l, int r, int k) { s[p]=k*(r-l+1); mn[p]=t1[p]=k; t2[p]=0; } void assign(int p, int l, int r, int L, int R, int k) { if (L<=l && r<=R) { Assign(p, l, r, k); return; } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) assign(lp, l, mid, L, R, k); if (R>mid) assign(rp, mid+1, r, L, R, k); pushup(p); } void Add(int p, int l, int r, int k) { mn[p]+=k; s[p]+=(r-l+1)*k; t2[p]+=k; } void add(int p, int l, int r, int L, int R, int k) { if (L<=l && r<=R) { Add(p, l, r, k); return; } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) add(lp, l, mid, L, R, k); if (R>mid) add(rp, mid+1, r, L, R, k); pushup(p); } int ask(int p, int l, int r, int L, int R) { if (L<=l && r<=R) return s[p]; pushdown(p, l, r); int mid=l+r>>1, res=0; if (L<=mid) res=ask(lp, l, mid, L, R); if (R>mid) res+=ask(rp, mid+1, r, L, R); return res; } int ask2(int p, int l, int r, int L, int R) { if (L<=l && r<=R) return mn[p]; pushdown(p, l, r); int mid=l+r>>1, res=1e9; if (L<=mid) res=ask2(lp, l, mid, L, R); if (R>mid) res=min(res, ask2(rp, mid+1, r, L, R)); return res; } } S; ``` ### 动态开点线段树 ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=100000*25; int n, m, lp[N], rp[N], tag[N], s[N], rt, num; void pushdown(int p, int l, int r) { if (!tag[p] || l==r) return; int mid=l+r>>1; if (!lp[p]) lp[p]=++num; if (!rp[p]) rp[p]=++num; tag[lp[p]]+=tag[p]; tag[rp[p]]+=tag[p]; s[lp[p]]+=(mid-l+1)*tag[p]; s[rp[p]]+=(r-mid)*tag[p]; tag[p]=0; } void add(int &p, int l, int r, int L, int R, int v) { if (!p) p=++num; if (L<=l && r<=R) return s[p]+=(r-l+1)*v, tag[p]+=v, void(); pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) add(lp[p], l, mid, L, R, v); if (R>mid) add(rp[p], mid+1, r, L, R, v); s[p]=s[lp[p]]+s[rp[p]]; } int ask(int p, int l, int r, int L, int R) { if (!p) return 0; if (L<=l && R>=r) return s[p]; pushdown(p, l, r); int res=0, mid=(l+r)/2; if (L<=mid) res+=ask(lp[p], l, mid, L, R); if (R>mid) res+=ask(rp[p], mid+1, r, L, R); return res; } signed main() { n=read(), m=read(); for (int i=1; i<=n; i++) add(rt, 1, n, i, i, read()); while (m--) { if (read()==1) { int l=read(), r=read(), v=read(); add(rt, 1, n, l, r, v); } else { int l=read(), r=read(); printf("%lld\n", ask(rt, 1, n, l, r)); } } return 0; } ``` ### 线段树合并 ```cpp int merge(int a, int b, int l, int r) { if (!a || !b) return a|b; if (l==r) { s[a]+=s[b]; return a; } int mid=l+r>>1; ls[a]=merge(ls[a], ls[b], l, mid); rs[a]=merge(rs[a], rs[b], mid+1, r); s[a]=s[ls[a]]+s[rs[a]]; return a; } ``` ## 数学 ### 十二重计数之八 #### 1. 球相同，盒子不同，不能有空盒 **公式**：$\binom{n-1}{m-1}$ **解释**：**隔板法**。$n-1$ 个缝隙插 $m-1$ 块板。 #### 2. 球相同，盒子不同，可以有空盒 **公式**：$\binom{n+m-1}{m-1}$ **解释**：**借球法**。先给 $m$ 个盒子各借 1 球转化为“不能有空盒”。 #### 3. 球不同，盒子不同，可以有空盒 **公式**：$m^n$ **解释**：每个球独立选择 $m$ 个盒子，乘法原理 $m^n$。 #### 4. 球不同，盒子相同，不能有空盒 **基本公式**：第二类斯特林数 $S(n,m)$ **递推公式**： $$ S(n, m) = S(n-1, m-1) + m \cdot S(n-1, m) $$ *解释：第 $n$ 个球独占一盒 $S(n-1, m-1)$，或放入已有 $m$ 盒之一 $m \cdot S(n-1, m)$。* **容斥原理显式**： $$ S(n,m) = \frac{1}{m!} \sum_{k=0}^{m} (-1)^k \binom{m}{k} (m-k)^n $$ *解释：用总映射 $m^n$ 容斥扣掉有空盒情况，再除以 $m!$ 消除盒子顺序。* 补充：上升幂 $x^{\overline{n}} = \prod_{k=0}^{n-1}(x+k)$。 $x^{\overline{n}} = \sum_{k} \left[ \begin{matrix} n \\ k \end{matrix} \right] x^k$ $x^{n} = \sum_{k} \left\{ \begin{matrix} n \\ k \end{matrix} \right\} (-1)^{n-k} x^{\overline{k}}$ 下降幂 $x^{\underline{n}} = \frac{x!}{(x-n)!} = \prod_{k=0}^{n-1}(x-k)$。 $x^{n} = \sum_{k} \left\{ \begin{matrix} n \\ k \end{matrix} \right\} x^{\underline{k}}= \sum_{k} \left\{ \begin{matrix} n \\ k \end{matrix} \right\} \binom{x}{k}k!$ $x^{\underline{n}} = \sum_{k} \left[ \begin{matrix} n \\ k \end{matrix} \right] (-1)^{n-k} x^{k}$ $\left\{ \begin{matrix} n \\ k \end{matrix} \right\}$ 表示**第二类斯特林数**，$\left[ \begin{matrix} n \\ k \end{matrix} \right]$ 表示**无符号第一类斯特林数**。 #### 5. 球不同，盒子不同，不能有空盒 **公式**：$m! \cdot S(n,m)$ **容斥直接求法（满射数）** $$ \sum_{k=0}^{m} (-1)^k \binom{m}{k} (m-k)^n $$ **解释**：在情况 4 基础上乘 $m!$ 给盒子赋予编号；用容斥求即为全集减去有空盒。 #### 6. 球不同，盒子相同，可以有空盒 **公式**：$\sum_{i=1}^{\min(n,m)} S(n,i)$ **解释**：按实际非空盒子数 $i$ 累加。 **贝尔数（当 $m \ge n$ 时，记为 $B_n$）**： **贝尔数递推公式**： $$ B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k $$ *解释：固定第 $n+1$ 个球，假设它所在集合还有 $k$ 个球，从剩下 $n$ 个球选 $k$ 个组合。* #### 7. 球相同，盒子相同，可以有空盒 **记号**：整数拆分 $P(n,m)$ **递推公式**： $$ P(n,m) = P(n,m-1) + P(n-m, m) \quad (n \ge m) $$ **解释**：有空盒扔掉一盒 $P(n,m-1)$；无空盒则每盒先发 1 球 $P(n-m, m)$。 #### 8. 球相同，盒子相同，不能有空盒 **公式**：$P(n-m, m)$ **解释**：每盒先垫 1 个球满足非空，剩下的 $n-m$ 个球转化为“可以有空盒”求解。 ### 组合 ```cpp int fac[N], inv[N]; int power(int x, int y) { int r=1; while (y) { if (y&1) r=r*x%P; x=x*x%P; y>>=1; } return r; } void init(int n) { fac[0]=1; for (int i=1; i<=n; i++) fac[i]=fac[i-1]*i%P; inv[n]=power(fac[n], P-2); for (int i=n-1; ~i; i--) inv[i]=inv[i+1]*(i+1)%P; } int C(int n, int m) { if (n<0 || m<0 || n<m) return 0; return fac[n]*inv[m]%P*inv[n-m]%P; } ``` ### 线性筛 ```cpp void init(int n) { for (int i=2; i<=n; i++) { if (!vis[i]) p[++cnt]=i; for (int j=1; j<=cnt && i*p[j]<=n; j++) { vis[i*p[j]]=1; if (i%p[j]==0) break; } } } ``` ### 狄利克雷前后缀和 前缀和：令 $f_i$ 表示答案为 $i$ 时候的方案数，求答案为 $i$ 的因数时的方案数。 ```cpp for (int i=1; i<=cnt; i++) for (int j=1; j<=n/p[i]; j++) f[j*p[i]]+=f[j]; ``` 后缀和：令 $f_i$ 表示答案为 $i$ 时候的方案数，求答案为 $i$ 的倍数时的方案数。 ```cpp for (int i=1; i<=cnt; i++) for (int j=n/p[i]; j>=1; j--) f[j]+=f[j*p[i]]; ``` 倒前缀和：令 $f_i$ 表示答案为 $i$ 因数时的方案数，求答案为 $i$ 时的方案数。 ```cpp for (int i=cnt; i>=1; i--) for (int j=n/p[i]; j>=1; j--) f[j*p[i]]-=f[j]; ``` 倒后缀和：令 $f_i$ 表示答案为 $i$ 倍数时的方案数，求答案为 $i$ 是的方案数。 ```cpp for (int i=cnt; i>=1; i--) for (int j=1; j<=n/p[i]; j++) f[j]-=f[j*p[i]]; ``` ### 线性基 ```cpp void insert(int x) { for(int i=55; i>=0; i--) { if (!((x>>i)&1)) continue; if(a[i]) { x^=a[i]; if (!x) return; } else { for (int j=i-1; j>=0; j--) if (x>>j&1) x^=a[j]; a[i]=x; for (int j=55; j>i; j--) if (a[j]>>i&1) a[j]^=x; return; } } } ``` ### 整除分块 所有满足 $\lfloor \frac{n}{i} \rfloor = d$ 的整数 $i$ 的取值范围为： $$ \lfloor \frac{n}{d+1} \rfloor + 1 \le i \le \lfloor \frac{n}{d} \rfloor $$ 所有满足 $\lceil \frac{n}{i} \rceil = d$ 的整数 $i$ 的取值范围为： $$ \lceil \frac{n}{d} \rceil \le i \le \lceil \frac{n}{d-1} \rceil - 1 $$ ### 莫比乌斯反演 **积性函数** 若 $\gcd(x,y) = 1$ 且 $f(xy)=f(x)f(y)$，则 $f(n)$ 为积性函数。 若 $f(x)$，$g(x)$均为积性函数，则以下函数也为积性函数： $$ \begin{aligned} & h(x) = f(x^p)\\ & h(x) = f^p(x)\\ & h(x) = f(x)g(x)\\ & h(x) = \sum_{d\mid x} f(d)g\left(\dfrac{x}{d}\right) \end{aligned} $$ **常见积性函数** * 单位函数 $e(n) = [n = 1]$。 * 幂函数 $\operatorname{Id}_{k}(n) = n^k$， $\operatorname{id}_1(n)$ 通常简记为$\operatorname{id}(n)$。 * 常数函数 $1(n) = 1$。 * 因数个数 $\operatorname{d}(n) = \sum\limits_{d\mid n} 1$。 * 除数函数 $\sigma_{k}(n) = \sum\limits_{d\mid n} d^k$。 * 欧拉函数 $\varphi(n) = \sum\limits_{i=1}^{n} [\gcd(i,n) = 1]$。 * 莫比乌斯函数 $$ \mu(n) = \begin{cases} 1 &n=1\\0 &n\ \text{含有平方因子}\\(-1)^k &k\text{为}\ n\ \text{的本质不同质因子个数} \end{cases} $$ **性质** $$ \large \sum_{d\mid n} \mu (d) = [n=1] $$ **反演常用** $$ [\gcd(i,j) = 1] = \sum\limits_{d\mid \gcd(i,j)} {\mu (d)} $$ **狄利克雷卷积** $$ \large(f\ast g) (n) = \sum_{d\mid n} f(d)g\left(\dfrac{n}{d}\right) $$ 1. 满足交换律，结合律，分配律。 * $f \ast g = g \ast f$ * $(f \ast g) \ast h = f\ast (g\ast h)$ * $f\ast (g+h) = f\ast g + f\ast h$ 2. $e$ 为狄利克雷卷积的单位元，有$(f\ast e)(n) = f(n)$。 3. 若 $f,g$ 为积性函数，则 $f\ast g$ 为积性函数。 **单位元** $e$ $$ (\mu\ast\mathbf 1)(n)=\sum_{d\mid n}\mu(d)=e(n)=[n=1] $$ **除数函数与幂函数** 幂函数 $\operatorname{Id}_{k}(n) = n^k$。 除数函数 $\sigma_{k}(n) = \sum\limits_{d\mid n} d^k$。 $$ (\operatorname{Id}_k\ast 1)(n) = \sum_{d\mid n} \operatorname{Id_k}(d) = \sum_{d\mid n} d^k = \sigma_k(n) $$ **欧拉函数与恒等函数** $$ \begin{aligned} \varphi \ast 1 =& \operatorname{Id}\\ \varphi =& \operatorname{Id}\ast \mu \end{aligned} $$ **恒等式** $$ n = \sum_{d\vert{}n} \varphi(d) $$ **莫比乌斯反演** 如果有 $$ f(n)=\sum_{d\mid n}g(d) $$ 那么 $$ g(n) = \sum_{d\mid n}\mu(d)f\left(\frac nd\right) = \sum_{d\mid n}\mu\left(\frac nd\right)f(d) $$ **证明** $$ f=g\ast\mathbf 1 $$ 所以 $$ f\ast\mu = g\ast\mathbf 1\ast\mu = g\ast e = g $$ **一些例子** $$ \begin{aligned} \mu\ast\mathbf 1&=e,\\ \operatorname{id}_k\ast\mathbf 1&=\sigma_k, &\sigma_k\ast\mu&=\operatorname{id}_k,\\ \varphi\ast\mathbf 1&=\operatorname{id}, &\operatorname{id}\ast\mu&=\varphi,\\ \mathbf 1\ast\mathbf 1&=\tau. \end{aligned} $$ **应用举例** $$ \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=1] = \sum_{d=1}^{\min(n,m)} \mu(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor $$ ### 裴蜀定理 $ax+by=c$ 有整数解**当且仅当** $\gcd(a,b)\mid c$ ### 威尔逊定理 当且仅当 $p$ 为质数时满足 $(p-1)!\equiv -1\pmod p$ ### EXGCD ```cpp int exgcd(int a, int b, int &x, int &y) { if (b==0) { x=1; y=0; return a; } int g=exgcd(b, a%b, y, x); y-=a/b*x; return g; } void calc(int a, int b, int c, int &x, int &y) { int g=exgcd(a, b, x, y); if (c%g!=0) { x=y=0; return; } a/=g, b/=g, c/=g; x*=c, y*=c;//任意一组解 int del=((x%b+abs(b))%b-x)/b; x+=del*b; y-=del*a;//x最小自然数解 if (x==0) x+=abs(b), y-=a*b/abs(b);//x最小正整数解 } ``` ### 中国剩余定理 ```cpp M=1, ans=0; for (int i=1; i<=n; i++) { cin>>m[i]>>a[i]; M*=m[i]; } for (int i=1; i<=n; i++) { int k=M/m[i], t, x; int g=exgcd(k, m[i], t, x); t=(t%m[i]+m[i])%m[i]; ans=(ans+(__int128)t*k%M*a[i])%M; } ans=(ans+M)%M; ``` ### EX中国剩余定理 ```cpp int excrt(vector<int> mm, vector<int> aa) { int M=mm[0], A=aa[0]; for (int i=1; i<mm.size(); i++) { int m=mm[i], a=aa[i], k, t; int g=exgcd(M, m, k, t); int c=((a-A)%m+m)%m; if (c%g) return -1; int p=m/g; k=((__int128)c/g*k%p+p)%p; A=(A+(__int128)k*M)%(M*p); M*=p; } return A; } ``` ### 线性求逆元 ```cpp inv[1]=1; for (int i=2; i<N; i++) inv[i]=(P-inv[P%i])*(P/i)%P; for (int i=1; i<=100; i++) printf("%lld %lld\n", inv[i], power(i, P-2)); ``` ### 欧拉函数 ```cpp int phi(int n) { int ans=n; for (int i=2; i*i<=n; i++) if (n%i==0) { ans=ans/i*(i-1); while (n%i==0) n/=i; } if (n>1) ans=ans/n*(n-1); return ans; } ``` #### 线性求欧拉函数 ```cpp void init(int n) { phi[1]=1; for (int i=2; i<=n; i++) { if (!vis[i]) p[++cnt]=i, phi[i]=i-1; for (int j=1; j<=cnt && i*p[j]<=n; j++) { vis[i*p[j]]=1; if (i%p[j]) phi[i*p[j]]=phi[i]*phi[p[j]]; else {phi[i*p[j]]=phi[i]*p[j]; break;} } } } ``` ### 扩展欧拉定理 $$ a^b \equiv \begin{cases} a^{b \bmod \varphi(m)}, &\gcd(a,m) = 1, \\ a^b, &\gcd(a,m)\ne 1, b < \varphi(m), \\ a^{(b \bmod \varphi(m)) + \varphi(m)}, &\gcd(a,m)\ne 1, b \ge \varphi(m). \end{cases} \pmod m $$ ### BSGS $$ a^{i\cdot t-j}\equiv b\pmod p\Rightarrow a^{i\cdot t}\equiv b\cdot a^j\pmod p $$ ```cpp int power(int x, int y, int p) { int r=1; while (y) { if (y&1) r=r*x%p; x=x*x%p; y>>=1; } return r; } int bsgs(int a, int b, int p) { unordered_map<int, int> f; int t=ceil(sqrt(p)); for (int i=1; i<=t; i++) b=b*a%p, f[b]=i; int tmp=power(a, t, p), s=1; for (int i=1; i<=t; i++) { s=s*tmp%p; if (f.count(s)) return i*t-f[s]; } return -1; } ``` ### 高斯消元 ```cpp for (int i=1; i<=n; i++) { int pos=i; for (int j=i+1; j<=n; j++) if (fabs(a[j][i])>fabs(a[pos][i])) pos=j; if (pos!=i) swap(a[pos], a[i]); if (fabs(a[i][i])<1e-9) return puts("No Solution"), 0; for (int j=1; j<=n; j++) { if (i==j) continue; double t=a[j][i]/a[i][i]; for (int k=1; k<=n+1; k++) a[j][k]-=a[i][k]*t; } } //a[i][n+1]/a[i][i] ``` ### 最简行阶梯形 ```cpp int rank=0; for (int j=1; j<=m && rank<n; j++) { int pos=-1; for (int i=rank+1; i<=n; i++) if (a[i][j]==1) {pos=i; break;} if (pos==-1) continue; rank++; swap(a[rank], a[pos]); for (int i=1; i<=n; i++) { if (i==rank || a[i][j]==0) continue; for (int k=1; k<=m; k++) a[i][k]^=a[rank][k]; } } ``` ### 拉格朗日插值 ```cpp int lagrange(int n, int *x, int *y, int X) { int ans=0; for (int i=1; i<=n; i++) { int s1=1, s2=1; for (int j=1; j<=n; j++) { if (i==j) continue; s1=s1*(X-x[j])%p; s2=s2*(x[i]-x[j])%p; } ans=(ans+y[i]*s1%p*power(s2, p-2)%p)%p; } return (ans+p)%p; } ``` ### 矩阵（vector 常数较大） ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int n, k; struct matrix{ int n, m, p=1e9+7; vector<vector<int> > a; matrix(int _n=0, int _m=0) { n=_n, m=_m; if (m==0) m=n; a=vector<vector<int> >(n+1, vector<int> (m+1)); } void mod(int _p) {p=_p;} vector<int>& operator[](int x) & {return a[x];} const vector<int>& operator[](int x) const& {return a[x];} void read() { for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) scanf("%lld", &a[i][j]); } void write() { for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) printf("%lld ", a[i][j]); printf("\n"); } } matrix operator * (const matrix &b) const { assert(m==b.n); matrix r(n, b.m); for (int i=1; i<=n; i++) for (int k=1; k<=m; k++) for (int j=1; j<=b.m; j++) r[i][j]=(r[i][j]+1ll*a[i][k]*b[k][j])%p; return r; } matrix operator ^ (int k) const { assert(n==m || k<=1); matrix r(m), a=*this; for (int i=1; i<=m; i++) r[i][i]=1; while (k) { if (k&1) r=r*a; a=a*a; k>>=1; } return r; } }; signed main() { scanf("%lld%lld", &n, &k); matrix a(n); a.read(); (a^k).write(); return 0; } ``` ### 大素数测试与分解质因数与计算所有因数（Miller-Rabin & Pollard-Rho） 时间复杂度：素性检测：$O(\sqrt{n})$，分解：$O(n^{\frac{1}{4}})$ ```cpp #define int long long namespace price { using i128=__int128; int mul(int a, int b, int m) { return (i128)a*b%m; } int power(int x, int y, int P) { int r=1; while (y) { if (y&1) r=mul(r, x, P); x=mul(x, x, P); y>>=1; } return r; } bool isprime(int n) { if (n<2) return 0; if (n%2==0) return n==2; int d=n-1, s=__builtin_ctzll(d); d>>=s; // 可换成 {2, 325, 9375, 28178, 450775, 9780504, 1795265022} 更快 for (int a:{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) { if (n%a==0) return n==a; int x=power(a, d, n); if (x==1 || x==n-1) continue; for (int i=1; i<s && x!=n-1; i++) x=mul(x, x, n); if (x!=n-1) return 0; } return 1; } int nxt(int x, int n) { return (mul(x, x, n)+1)%n; } int rho(int n) { if (n%2==0) return 2; if (n%3==0) return 3; for (int st=2;; st++) { int x=st, y=st, d=1; int pw=1, len=0, v=1; while (d==1) { y=nxt(y, n); ++len; v=mul(v, abs(x-y), n); if (len%127==0) { d=gcd(v, n); v=1; } if (pw==len) { x=y; pw<<=1; len=0; d=gcd(v, n); v=1; } } if (d!=n) return d; } } vector<int> a; void fac(int n) { if (n<10000) { for (int i=2; i*i<=n; i++) { while (n%i==0) a.push_back(i), n/=i; } if (n>1) a.push_back(n); } else if (isprime(n)) a.push_back(n); else { int d=rho(n); fac(d); fac(n/d); } } vector<int> factorize(int n) { //分解质因数 a.clear(); if (n>1) fac(n); sort(a.begin(), a.end()); return a; } vector<int> divisor(int n) { //所有因数 vector<int> p=factorize(n), d{1}; for (int i=0; i<p.size();) { int j=i, x=1, m=d.size(); while (j<p.size() && p[j]==p[i]) { x*=p[i]; for (int k=0; k<m; k++) d.push_back(d[k]*x); j++; } i=j; } sort(d.begin(), d.end()); return d; } }; ``` ## 图论 ### Pick 定理 给定顶点均为整点的简单多边形，皮克定理说明了其面积 ${\displaystyle A}$ 和内部格点数目 ${\displaystyle i}$、边上格点数目 ${\displaystyle b}$ 的关系：${\displaystyle A=i+{\frac {b}{2}}-1}$． ### 欧拉公式 在一个不和自己交叉的多面体中，面的个数+顶点（角）的个数-棱的个数=2，${\displaystyle V-E+F=2}$ ### 倍增 LCA ```cpp void dfs(int x, int fa) { f[x][0]=fa; dep[x]=dep[fa]+1; for (int i=1; i<=22; i++) f[x][i]=f[f[x][i-1]][i-1]; for (int y:e[x]) if (y!=fa) dfs(y, x); } int lca(int x, int y) { if (dep[x]<dep[y]) swap(x, y); for (int i=22; i>=0; i--) if (dep[f[x][i]]>=dep[y]) x=f[x][i]; if (x==y) return x; for (int i=22; i>=0; i--) if (f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i]; return f[x][0]; } ``` ### Floyd 最短路 ```cpp for (int k=1; k<=n; k++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) f[i][j]=min(f[i][j], f[i][k]+f[k][j]); ``` ### Dijkstra 最短路 ```cpp void dijkstra(int s) { fill(dis+1, dis+n+1, 1e18); fill(vis+1, vis+n+1, 0); dis[s]=0; priority_queue<pair<int, int> > q; q.push({0, s}); while (!q.empty()) { int x=q.top().second; q.pop(); if (vis[x]) continue; vis[x]=1; for (auto [y, z]:e[x]) { if (dis[y]>dis[x]+z) { dis[y]=dis[x]+z; q.push({-dis[y], y}); } } } } ``` ### SPFA 最短路 ```cpp bool spfa(int s) { fill(dis+1, dis+n+1, 1e18); fill(vis+1, vis+n+1, 0); fill(cnt+1, cnt+n+1, 0); dis[s]=0, vis[s]=1; queue<int> q; q.push(s); while (!q.empty()) { int x=q.front(); q.pop(), vis[x]=0; for (auto [y, z]:e[x]) { if (dis[y]>dis[x]+z) { dis[y]=dis[x]+z; cnt[y]=cnt[x]+1; if (cnt[y]>n) return 0; if (!vis[y]) { q.push(y); vis[y]=1; } } } } return 1; } ``` ### Johnson 全源最短路 ```cpp bool spfa(int s) { fill(h, h+n+1, 1e18); fill(vis, vis+n+1, 0); fill(cnt, cnt+n+1, 0); h[s]=0, vis[s]=1; queue<int> q; q.push(s); while (!q.empty()) { int x=q.front(); q.pop(), vis[x]=0; for (auto [y, z]:e[x]) { if (h[y]>h[x]+z) { h[y]=h[x]+z; cnt[y]=cnt[x]+1; if (cnt[y]>n) return 0; if (!vis[y]) { q.push(y); vis[y]=1; } } } } return 1; } void dijkstra(int s) { fill(dis, dis+n+1, 1e18); fill(vis, vis+n+1, 0); dis[s]=0; priority_queue<pair<int, int> > q; q.push({0, s}); while (!q.empty()) { int x=q.top().second; q.pop(); if (vis[x]) continue; vis[x]=1; for (auto [y, z]:e[x]) { if (dis[y]>dis[x]+z) { dis[y]=dis[x]+z; q.push({-dis[y], y}); } } } } void Johnson() { for (int i=1; i<=n; i++) e[0].emplace_back(i, 0); if (!spfa(0)) return puts("-1"), void(); for (int x=1; x<=n; x++) for (auto &[y, z]:e[x]) z+=h[x]-h[y]; for (int i=1; i<=n; i++) { dijkstra(i); for (int j=1; j<=n; j++) dist[i][j]=(dis[j]==1e18 ? 1e18 : dis[j]+h[j]-h[i]); } } ``` ### Kruskal 最小生成树 ```cpp struct node { int x, y, z; bool operator < (const node &a) const { return z<a.z; } } e[M]; int find(int x) {return fa[x]==x ? x : fa[x]=find(fa[x]);} int main() { n=read(), m=read(); for (int i=1; i<=m; i++) e[i].x=read(), e[i].y=read(), e[i].z=read(); sort(e+1, e+m+1); for (int i=1; i<=n; i++) fa[i]=i; int cnt=0; for (int i=1; i<=m; i++) { int x=find(e[i].x), y=find(e[i].y); if (x==y) continue; ans+=e[i].z; fa[x]=y; cnt++; if (cnt==n-1) break; } if (cnt<n-1) printf("orz\n"); else printf("%d\n", ans); return 0; } ``` ### PRIM 最小生成树 ```cpp for (int i=1; i<=m; i++) { int x=read(), y=read(), z=read(); e[x].emplace_back(y, z); e[y].emplace_back(x, z); } fill(dis, dis+n+1, 1e9); dis[1]=0; for (int i=1; i<=n; i++) { int x=0; for (int j=1; j<=n; j++) if (!vis[j] && dis[j]<dis[x]) x=j; if (!x) return puts("orz"), 0; vis[x]=1; ans+=dis[x]; for (auto [y, z] : e[x]) if (!vis[y] && z<dis[y]) dis[y]=z; } ``` ### Boruvka 最小生成树 ```cpp int boruvka() { fill(vis+1, vis+m+1, 0); iota(fa+1, fa+n+1, 1); int cnt=0, status=1; while (status) { status=0; fill(best+1, best+n+1, 0); for (int i=1; i<=m; i++) { if (vis[i]) continue; int x=find(e[i].x), y=find(e[i].y); if (x==y) continue; if (best[x]==0 || e[i].z<e[best[x]].z) best[x]=i; if (best[y]==0 || e[i].z<e[best[y]].z) best[y]=i; } for (int i=1; i<=n; i++) if (best[i] && !vis[best[i]]) { status=1; cnt++; ans+=e[best[i]].z; vis[best[i]]=1; int x=find(e[best[i]].x); int y=find(e[best[i]].y); fa[x]=y; } } if (cnt==n-1) return ans; return -1; } ``` ### 树上启发式合并 ```cpp void dfs1(int x, int fa) { sz[x]=1, big[x]=0; for (int y:e[x]) { if (y==fa) continue; dfs1(y, x); sz[x]+=sz[y]; if (sz[y]>sz[big[x]]) big[x]=y; } } void add(int x, int fa, int v) { if (v==1) { cnt[c[x]]++; if (cnt[c[x]]==1) sum++; } else { cnt[c[x]]--; if (cnt[c[x]]==0) sum--; } for (int y:e[x]) if (y!=fa) add(y, x, v); } void dfs2(int x, int fa, bool keep) { for (int y:e[x]) if (y!=fa && y!=big[x]) dfs2(y, x, 0); if (big[x]) dfs2(big[x], x, 1); cnt[c[x]]++; if (cnt[c[x]]==1) sum++; for (int y:e[x]) if (y!=fa && y!=big[x]) add(y, x, 1); ans[x]=sum; if (!keep) add(x, fa, -1); } dfs1(1, 0); dfs2(1, 0, true); ``` ### 点分治（eg.树上是否存在距离为k的点对） ```cpp #include <bits/stdc++.h> using namespace std; const int N=1e4+10; int n, m, rt, q[N], cnt, tot, sz[N], mx[N], dis[N], num[N], tmp[N], maxq; bool vis[N], ans[N]; vector<char> flag; vector<pair<int, int> > e[N]; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } void dfsroot(int x, int fa) { sz[x]=1, mx[x]=0; for (auto [y, z]:e[x]) { if (y==fa || vis[y]) continue; dfsroot(y, x); sz[x]+=sz[y]; mx[x]=max(mx[x], sz[y]); } mx[x]=max(mx[x], tot-sz[x]); if (mx[x]<mx[rt]) rt=x; } void dfssize(int x, int fa) { sz[x]=1; for (auto [y, z]:e[x]) { if (y==fa || vis[y]) continue; dfssize(y, x); sz[x]+=sz[y]; } } void dfs(int x, int fa) { if (dis[x]>maxq) return; num[++cnt]=dis[x]; for (auto [y, z]:e[x]) { if (y==fa || vis[y]) continue; dis[y]=dis[x]+z; dfs(y, x); } } void calc(int x) { int t=0; for (auto [y, z]:e[x]) { if (vis[y]) continue; cnt=0; dis[y]=z; dfs(y, x); for (int j=1; j<=cnt; j++) for (int k=1; k<=m; k++) if (q[k]>=num[j]) ans[k]|=flag[q[k]-num[j]]; for (int j=1; j<=cnt; j++) { flag[num[j]]=1; tmp[++t]=num[j]; } } for (int i=1; i<=t; i++) flag[tmp[i]]=0; } void dfz(int x) { dfssize(x, 0); vis[x]=1; flag[0]=1; calc(x); for (auto [y, z]:e[x]) { if (vis[y]) continue; tot=sz[y]; mx[rt=0]=1e9; dfsroot(y, x); dfz(rt); } } int main() { n=read(), m=read(); for (int i=1; i<n; i++) { int x=read(), y=read(), z=read(); e[x].emplace_back(y, z); e[y].emplace_back(x, z); } for (int i=1; i<=m; i++) q[i]=read(), maxq=max(maxq, q[i]); flag.assign(maxq+1, 0); tot=n, mx[rt]=1e9; dfsroot(1, 0), dfz(rt); for (int i=1; i<=m; i++) printf(ans[i] ? "AYE\n" : "NAY\n"); return 0; } ``` ### tarjan SCC（有向图缩点）（注：scc编号为反拓扑序） ```cpp void tarjan(int x) { dfn[x]=low[x]=++num; s.push(x); ins[x]=1; for (int y:e[x]) { if (!dfn[y]) { tarjan(y); low[x]=min(low[x], low[y]); } else if (ins[y]) low[x]=min(low[x], dfn[y]); } if (dfn[x]==low[x]) { int y; cnt++; do { y=s.top(); s.pop(); ins[y]=0; bel[y]=cnt, scc[cnt].push_back(y); } while (x!=y); } } for (int i=1; i<=n; i++) if (!dfn[i]) tarjan(i); for (int x=1; x<=n; x++) for (int y:e[x]) if (bel[x]!=bel[y]) add_c(bel[x], bel[y]); ``` ### tarjan V-DCC（无向图割点+割点缩点） ```cpp void tarjan(int x, int rt) { dfn[x]=low[x]=++num; s.push(x); if (x==rt && e[x].empty()) return dcc[++cnt].push_back(x), void(); int flag=0; for (int y:e[x]) { if (!dfn[y]) { tarjan(y, rt); low[x]=min(low[x], low[y]); if (low[y]>=dfn[x]) { if (x!=rt || (++flag)>1) cut[x]=1; int z; cnt++; do { z=s.top(); s.pop(); dcc[cnt].push_back(z); } while (z!=y); dcc[cnt].push_back(x); } } else low[x]=min(low[x], dfn[y]); } } for (int i=1; i<=n; i++) if (!dfn[i]) tarjan(i, i); ``` #### 圆方树 ```cpp void tarjan(int x, int rt) { dfn[x]=low[x]=++num; s.push(x); if (x==rt && e[x].empty()) { cnt++; E[n+cnt].push_back(x); E[x].push_back(n+cnt); return; } int flag=0; for (int y:e[x]) { if (!dfn[y]) { tarjan(y, rt); low[x]=min(low[x], low[y]); if (low[y]>=dfn[x]) { int z; cnt++; do { z=s.top(); s.pop(); E[n+cnt].push_back(z); E[z].push_back(n+cnt); } while (z!=y); E[n+cnt].push_back(x); E[x].push_back(n+cnt); } } else low[x]=min(low[x], dfn[y]); } } ``` #### 记录每个点双中的边 ```cpp void tarjan(int x, int fa, int rt) { dfn[x]=low[x]=++num; s.push(x); if (x==rt && e[x].empty()) return dcc[++cnt].push_back(x), void(); int flag=0; for (int y:e[x]) { if (y==fa) continue; if (!dfn[y]) { se.push({x, y}); tarjan(y, x, rt); low[x]=min(low[x], low[y]); if (low[y]>=dfn[x]) { if (x!=rt || (++flag)>1) cut[x]=1; int z; cnt++; pair<int, int> ze; do { ze=se.top(); se.pop(); ecc[cnt].push_back(ze); } while (ze!=make_pair(x, y)); do { z=s.top(); s.pop(); dcc[cnt].push_back(z); } while (z!=y); dcc[cnt].push_back(x); } } else { low[x]=min(low[x], dfn[y]); if (dfn[y]<dfn[x]) se.push({x, y}); } } } for (int i=1; i<=n; i++) if (!dfn[i]) tarjan(i, 0, i); ``` ### tarjan E-BCC（无向图割边+割边缩点） ```cpp void tarjan(int x, int fa) { dfn[x]=low[x]=++num; s.push(x), ins[x]=1; for (int y:e[x]) { if (!dfn[y]) { tarjan(y, x); low[x]=min(low[x], low[y]); if (low[y]>dfn[x]) bridge.push_back({x, y});//割边 } else if (y!=fa) low[x]=min(low[x], dfn[y]); } if (low[x]==dfn[x]) {//缩点 int y; cnt++; do { y=s.top(); s.pop(); ins[y]=0; bel[y]=cnt, bcc[cnt].push_back(y); } while (x!=y); } } for (int i=1; i<=n; i++) if (!dfn[i]) tarjan(i, 0); ``` #### 链式前向星写法 ```cpp int tot=1; void add(int x, int y) { ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot; } void tarjan(int x, int id) { dfn[x]=low[x]=++num; for (int i=head[x]; i; i=nxt[i]) { int y=ver[i]; if (!dfn[y]) { tarjan(y, i); low[x]=min(low[x], low[y]); if (low[y]>dfn[x]) bridge[i]=bridge[i^1]=1; } else if (i!=(id^1)) low[x]=min(low[x], dfn[y]); } } ``` ### 欧拉路径 ```cpp void dfs(int x) { while (!e[x].empty()) { auto [y, id]=e[x].back(); e[x].pop_back(); if (!vis[id]) { vis[id]=1; dfs(y); ans.push_back(id); } } } ``` ```cpp int n, m, st, in[N], out[N], cur[N]; vector<int> e[N]; stack<int> s; void dfs(int x) { while (cur[x]<e[x].size()) { int y=e[x][cur[x]++]; dfs(y); s.push(y); } } int main() { n=read(), m=read(); for (int i=1; i<=m; i++) { int x=read(), y=read(); e[x].push_back(y); in[y]++; out[x]++; } for (int i=1; i<=n; i++) sort(e[i].begin(), e[i].end()); st=1; int tot=0, flag=0; for (int i=1; i<=n; i++) { if (abs(in[i]-out[i])) tot++; if (abs(in[i]-out[i])>1) flag=1; } if (tot>2 || flag) return puts("No"), 0; for (int i=1; i<=n; i++) if (out[i]==in[i]+1) {st=i; break;} dfs(st); s.push(st); while (!s.empty()) printf("%d ", s.top()), s.pop(); return 0; } ``` ### 网络最大流 时间复杂度：$O(kE)\sim O(V^2E)$ 二分图：$O(E\sqrt V)$ ```cpp #define ll long long namespace flow { int n, s, t, d[N], cnt=1, head[N], cur[N], to[M], nxt[M]; ll val[M]; void addedge(int x, int y, ll z) { to[++cnt]=y; val[cnt]=z; nxt[cnt]=head[x]; head[x]=cnt; } void add(int x, int y, ll z) { addedge(x, y, z); addedge(y, x, 0); } void init(int _n, int _s, int _t) { cnt=1, n=_n, s=_s, t=_t; fill(head+1, head+n+1, 0); } bool bfs() { for (int i=1; i<=n; i++) cur[i]=head[i], d[i]=0; queue<int> q; q.push(s), d[s]=1; while (!q.empty()) { int x=q.front(); q.pop(); for (int i=head[x]; i; i=nxt[i]) { int y=to[i]; if (d[y] || !val[i]) continue; d[y]=d[x]+1; q.push(y); if (y==t) return 1; } } return 0; } ll dinic(int x, ll flow) { if (x==t) return flow; ll rest=flow; for (int &i=cur[x]; i; i=nxt[i]) { int y=to[i]; if (d[y]!=d[x]+1 || !val[i]) continue; ll k=dinic(y, min(rest, val[i])); if (!k) d[y]=0; val[i]-=k; val[i^1]+=k; rest-=k; if (!rest) break; } return flow-rest; } ll maxflow() { ll res=0; while (bfs()) res+=dinic(s, INF); return res; } }; ``` ### 最小费用最大流 最坏情况：$O(VE+KE\log V)$ ```cpp #define ll long long namespace flow { struct node { int y, e; } p[N]; int head[N], vis[N], to[M], nxt[M]; ll dis[N], h[N], val[M], cost[M]; int n, s, t, cnt=1; void addedge(int x, int y, ll f, ll c) { to[++cnt]=y; val[cnt]=f; cost[cnt]=c; nxt[cnt]=head[x]; head[x]=cnt; } void add(int x, int y, ll f, ll c) { addedge(x, y, f, c); addedge(y, x, 0, -c); } void init(int _n, int _s, int _t) { n=_n, s=_s, t=_t, cnt=1; fill(head+1, head+n+1, 0); } bool dijkstra() { priority_queue<pair<ll, int> > q; for (int i=1; i<=n; i++) dis[i]=INF; for (int i=1; i<=n; i++) vis[i]=0; dis[s]=0; q.push({0, s}); while (!q.empty()) { int x=q.top().second; q.pop(); if (vis[x]) continue; vis[x]=1; for (int i=head[x]; i; i=nxt[i]) { int y=to[i]; ll nc=cost[i]+h[x]-h[y]; if (val[i] && dis[y]>dis[x]+nc) { dis[y]=dis[x]+nc; p[y].y=x; p[y].e=i; if (!vis[y]) q.push({-dis[y], y}); } } } return dis[t]!=INF; } void spfa() { queue<int> q; fill(h+1, h+n+1, INF); fill(vis+1, vis+n+1, 0); h[s]=0, vis[s]=1; q.push(s); while (!q.empty()) { int x=q.front(); q.pop(); vis[x]=0; for (int i=head[x]; i; i=nxt[i]) { int y=to[i]; if (val[i] && h[y]>h[x]+cost[i]) { h[y]=h[x]+cost[i]; if (!vis[y]) { vis[y]=1; q.push(y); } } } } } pair<ll, ll> calc(ll lim=INF) { if (s==t || lim<=0) return {0, 0}; ll maxf=0, minc=0; spfa(); /* 若没有负数费用，可将 spfa(); 替换成 fill(h+1, h+n+1, 0); */ while (maxf<lim && dijkstra()) { ll minf=lim-maxf; for (int i=1; i<=n; i++) if (dis[i]!=INF) h[i]+=dis[i]; for (int i=t; i!=s; i=p[i].y) minf=min(minf, val[p[i].e]); for (int i=t; i!=s; i=p[i].y) { val[p[i].e]-=minf; val[p[i].e^1]+=minf; } maxf+=minf; minc+=minf*h[t]; } return {maxf, minc}; } }; ``` ### 重链剖分 ```cpp #include <cstdio> #include <cctype> #include <vector> #include <algorithm> #define int long long using namespace std; const int N=4e5+10; int fa[N], dep[N], siz[N], son[N], top[N], dfn[N], rnk[N]; int n, m, rt, mod, a[N], cnt; int l[N], r[N], s[N], t[N]; vector<int> e[N]; int read() { int x=0, f=0; char ch=getchar(); while (!isdigit(ch)) {f|=ch=='-'; ch=getchar();} while (isdigit(ch)) {x=(x<<3)+(x<<1)+(ch^48); ch=getchar();} return f?-x:x; } void dfs1(int x) { dep[x]=dep[fa[x]]+1; siz[x]=1; for (int i=0; i<e[x].size(); i++) { int y=e[x][i]; if (y==fa[x]) continue; fa[y]=x; dfs1(y); siz[x]+=siz[y]; if (siz[y]>siz[son[x]]) son[x]=y; } } void dfs2(int x, int t) { top[x]=t; dfn[x]=++cnt; rnk[cnt]=x; if (!son[x]) return; dfs2(son[x], t); for (int i=0; i<e[x].size(); i++) if(e[x][i]!=fa[x] && e[x][i]!=son[x]) dfs2(e[x][i], e[x][i]); } int lca(int x, int y) { while (top[x]!=top[y]) if (dep[top[x]]>dep[top[y]]) x=fa[top[x]]; else y=fa[top[y]]; return dep[x]<dep[y] ? x : y; } #define lp p<<1 #define rp p<<1|1 void build(int p, int L, int R) { l[p]=L, r[p]=R; if (L==R) { s[p]=a[rnk[L]]; return; } int mid=L+R>>1; build(lp, L, mid); build(rp, mid+1, R); s[p]=(s[lp]+s[rp])%mod; } void pushdown(int p) { s[lp]=(s[lp]+(r[lp]-l[lp]+1)*t[p])%mod; s[rp]=(s[rp]+(r[rp]-l[rp]+1)*t[p])%mod; t[lp]=(t[lp]+t[p])%mod, t[rp]=(t[rp]+t[p])%mod, t[p]=0; } void change(int p, int L, int R, int v) { if (L<=l[p] && r[p]<=R) { t[p]=(t[p]+v)%mod; s[p]=(s[p]+(r[p]-l[p]+1)*v)%mod; return; } pushdown(p); int mid=l[p]+r[p]>>1; if (L<=mid) change(lp, L, R, v); if (R>mid) change(rp, L, R, v); s[p]=(s[lp]+s[rp])%mod; } int query(int p, int L, int R) { if (L<=l[p] && r[p]<=R) return s[p]; pushdown(p); int mid=l[p]+r[p]>>1, r=0; if (L<=mid) r=(r+query(lp, L, R))%mod; if (R>mid) r=(r+query(rp, L, R))%mod; return r; } void change_tree(int x, int v) { change(1, dfn[x], dfn[x]+siz[x]-1, v); } int query_tree(int x) { return query(1, dfn[x], dfn[x]+siz[x]-1); } void change_chain(int x, int y, int z) { int fx=top[x], fy=top[y]; while (fx!=fy) { if (dep[fx]>=dep[fy]) change(1, dfn[fx], dfn[x], z), x=fa[fx]; else change(1, dfn[fy], dfn[y], z), y=fa[fy]; fx=top[x], fy=top[y]; } change(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), z); } int query_chain(int x, int y) { int res=0, fx=top[x], fy=top[y]; while (fx!=fy) { if (dep[fx]>=dep[fy]) res=(res+query(1, dfn[fx], dfn[x]))%mod, x=fa[fx]; else res=(res+query(1, dfn[fy], dfn[y]))%mod, y=fa[fy]; fx=top[x], fy=top[y]; } res=(res+query(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y])))%mod; return res; } signed main() { n=read(), m=read(), rt=read(), mod=read(); for (int i=1; i<=n; i++) a[i]=read(); for (int i=1; i<n; i++) { int x=read(), y=read(); e[x].push_back(y); e[y].push_back(x); } dfs1(rt); dfs2(rt, rt); build(1, 1, n); while (m--) { int opt=read(); if (opt==1) { int x=read(), y=read(), z=read();; change_chain(x, y, z); } else if (opt==2) { int x=read(), y=read(); printf("%lld\n", query_chain(x, y)); } else if (opt==3) { int x=read(), z=read(); change_tree(x, z); } else { int x=read(); printf("%lld\n", query_tree(x)); } } return 0; } ``` ### 长链条剖分求 k 级祖先 ```cpp void dfs1(int x, int fa) { dep[x]=dep[fa]+1; f[x][0] = fa; for (int i=1; i<=20; i++) f[x][i]=f[f[x][i-1]][i-1]; for (int y:e[x]) { if (y==fa) continue; dfs1(y, x); if (len[y]>len[son[x]]) son[x]=y; } len[x] = len[son[x]] + 1; } void dfs2(int x, int tp) { top[x]=tp; if (x==tp) { for (int y=x, i=0; y&&i<len[x]; i++, y=f[y][0]) up[x].push_back(y); for (int y=x, i=0; y&&i<len[x]; i++, y=son[y]) down[x].push_back(y); } if (son[x]) dfs2(son[x], tp); for (int y:e[x]) if (y!=f[x][0] && y!=son[x]) dfs2(y, y); } int query(int x, int k) { if (k==0) return x; if (k>=dep[x]) return 0; int i=__lg(k); x=f[x][i], k-=(1<<i); int tp=top[x]; if (dep[x]-dep[tp]>=k) return down[tp][dep[x]-dep[tp]-k]; else return up[tp][k-(dep[x]-dep[tp])]; } ``` ### 长链剖分优化DP（eg.CF1009F，求每个点子树中深度为多少的点最多，注意存储方式） ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=1e6+10; int n, buf[N], *now=buf, *f[N], ans[N]; int len[N], son[N]; vector<int> e[N]; void dfs1(int x, int fa) { for (int y:e[x]) { if (y==fa) continue; dfs1(y, x); if (len[y]>len[son[x]]) son[x]=y; } len[x]=len[son[x]]+1; } void dfs2(int x, int fa) { f[x][0]=1; if (son[x]) { f[son[x]]=f[x]+1; dfs2(son[x], x); ans[x]=ans[son[x]]+1; } for (int y:e[x]) { if (y==fa || y==son[x]) continue; f[y]=now, now+=len[y]; dfs2(y, x); for (int i=1; i<=len[y]; i++) { f[x][i]+=f[y][i-1]; if (f[x][i]>f[x][ans[x]] || f[x][i]==f[x][ans[x]] && i<ans[x]) ans[x]=i; } } if (f[x][ans[x]]==1) ans[x]=0; } signed main() { n=read(); for (int i=1; i<n; i++) { int x=read(), y=read(); e[x].push_back(y); e[y].push_back(x); } dfs1(1, 0); f[1]=now, now+=len[1]; dfs2(1, 0); for (int i=1; i<=n; i++) printf("%d\n", ans[i]); return 0; } ``` ## 字符串 ### 字典树（trie） ```cpp struct trie { int cnt=1, tr[M][26], sum[M], vis[M]; void clear() { for (int i=1; i<=cnt; i++) { sum[i]=0, vis[i]=0; for (int j=0; j<26; j++) tr[i][j]=0; } cnt=1; } void insert(char *s) { int l=strlen(s), p=1; for (int i=0; i<l; i++) { int c=s[i]-'a'; if (!tr[p][c]) tr[p][c]=++cnt; p=tr[p][c]; } vis[p]=1; } bool find(char *s) { int l=strlen(s), p=1; for (int i=0; i<l; i++) { int c=s[i]-'a'; if (!tr[p][c]) return 0; p=tr[p][c]; } return vis[p]; } } tr; ``` ### Hash 哈希 ```cpp const int base=2333; const int P1=1000000053; const int P2=1000000097; struct Hash { int h1[N], h2[N]; int p1[N], p2[N]; void init(string s) { int n=s.size(); p1[0]=p2[0]=1; h1[0]=h2[0]=0; for (int i=0; i<n; i++) { p1[i+1]=(1ll*p1[i]*base)%P1; p2[i+1]=(1ll*p2[i]*base)%P2; h1[i+1]=(1ll*h1[i]*base+s[i])%P1; h2[i+1]=(1ll*h2[i]*base+s[i])%P2; } } // 查询区间 [l, r] (0-based) pair<int, int> query(int l, int r) { int len=r-l+1; int r1=(h1[r+1]-1ll*h1[l]*p1[len]%P1+P1)%P1; int r2=(h2[r+1]-1ll*h2[l]*p2[len]%P2+P2)%P2; return {r1, r2}; } } sh; ``` ### KMP $s2[1\to next[i]]=s2[i-next[i]+1\to i]$ $s2[1\to f[i]]=s1[i-f[i]+1\to i]$ ```cpp n=strlen(s2+1), m=strlen(s1+1); nxt[1]=0; for (int i=2, j=0; i<=n; i++) { while (j>0 && s2[i]!=s2[j+1]) j=nxt[j]; if (s2[i]==s2[j+1]) j++; nxt[i]=j; } for (int i=1, j=0; i<=m; i++) { while (j>0 && (j==n || s1[i]!=s2[j+1])) j=nxt[j]; if (s1[i]==s2[j+1]) j++; if ((f[i]=j)==n) printf("%d\n", i-n+1); } ``` ### exKMP/Z 函数 $t[1\to z[i]]=t[i\to i+z[i]-1]$ $t[1\to p[i]]=s[i\to i+p[i]-1]$ ```cpp int n=strlen(s+1), m=strlen(t+1); z[1]=m; for (int i=2, l=0; i<=m; i++) { z[i]=0; if (l+z[l]>i) z[i]=min(z[i-l+1], l+z[l]-i); while (i+z[i]<=m && t[z[i]+1]==t[i+z[i]]) z[i]++; if (i+z[i]>l+z[l]) l=i; } for (int i=1, l=0; i<=n; i++) { p[i]=0; if (l+p[l]>i) p[i]=min(z[i-l+1], l+p[l]-i); while (i+p[i]<=n && p[i]<m && t[p[i]+1]==s[i+p[i]]) p[i]++; if (i+p[i]>l+p[l]) l=i; } ``` ### 马拉车/Manacher ```cpp int init(char *s) { int len=strlen(s+1), j=0; st[j++]='$', st[j++]='#'; for (int i=1; i<=len; i++) { st[j++]=s[i]; st[j++]='#'; } st[j++]='^'; st[j]='\0'; return j; } int manacher(char *s) { int ans=0, len=init(s); for (int i=1, mid=0, r=0; i<len; i++) { p[i]=(i<=r) ? min(r-i, p[2*mid-i]) : 0; while (st[i+p[i]+1]==st[i-p[i]-1]) p[i]++; if (i+p[i]>r) r=i+p[i], mid=i; ans=max(ans, p[i]); } return ans; } ``` ### 最小表示法 ```cpp int findmin(char *s) { int k=0, i=1, j=2; while (k<n && i<=n && j<=n) { if (s[(i+k-1)%n+1]==s[(j+k-1)%n+1]) k++; else { if (s[(i+k-1)%n+1]>s[(j+k-1)%n+1]) i=i+k+1; else j=j+k+1; if (i==j) i++; k=0; } } return min(i, j); } ``` ## 多项式 ### NTT ```cpp #include <bits/stdc++.h> using namespace std; namespace NTT { const int N=1<<21, P=998244353, G=3, Gi=(P+1)/3; int rev[N], A[N], B[N]; int power(int x, int y) { int r=1; while (y) { if (y&1) r=1ll*r*x%P; x=1ll*x*x%P, y>>=1; } return r; } void ntt(int *a, int n, int inv) { for (int i=0; i<n; i++) { rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0); if (i<rev[i]) swap(a[i], a[rev[i]]); } for (int len=1; len<n; len<<=1) { int wn=power(inv==1 ? G : Gi, (P-1)/(len<<1)); for (int i=0; i<n; i+=(len<<1)) { for (int j=0, w=1; j<len; j++, w=1ll*w*wn%P) { int x=a[i+j], y=1ll*w*a[i+j+len]%P; a[i+j]=(x+y)%P; a[i+j+len]=(x-y+P)%P; } } } if (inv==-1) { int invn=power(n, P-2); for (int i=0; i<n; i++) a[i]=1ll*a[i]*invn%P; } } void mul(int *a, int n, int *b, int m, int *r) { int L=1; while (L<n+m-1) L<<=1; for (int i=0; i<L; i++) A[i]=i<n ? a[i] : 0; for (int i=0; i<L; i++) B[i]=i<m ? b[i] : 0; ntt(A, L, 1), ntt(B, L, 1); for (int i=0; i<L; i++) A[i]=1ll*A[i]*B[i]%P; ntt(A, L, -1); for (int i=0; i<n+m-1; i++) r[i]=A[i]; } } int a[9]={1, 2, 3}; int b[9]={4, 5, 6}; int main() { int n=3, m=3; NTT::mul(a, n, b, m, a); for (int i=0; i<n+m-1; i++) printf("%d ", a[i]); puts(""); return 0; } ``` #### vector 实现 ```cpp #include <bits/stdc++.h> using namespace std; const int P=998244353, G=3; namespace NTT { int power(int x, int y) { int r=1; while (y) { if (y&1) r=1ll*r*x%P; x=1ll*x*x%P, y>>=1; } return r; } void ntt(vector<int> &a, bool inv) { int n=a.size(); for (int i=0, j=0; i<n; i++) { if (i<j) swap(a[i], a[j]); for (int k=n>>1; (j^=k)<k; k>>=1); } for (int len=2; len<=n; len<<=1) { int wlen=power(G, (P-1)/len); if (inv) wlen=power(wlen, P-2); for (int i=0; i<n; i+=len) { int w=1; for (int j=0; j<len/2; j++) { int u=a[i+j], v=1ll*w*a[i+j+len/2]%P; a[i+j]=(u+v)%P; a[i+j+len/2]=(u-v+P)%P; w=1ll*w*wlen%P; } } } if (inv) { int invn=power(n, P-2); for (int i=0; i<n; i++) a[i]=1ll*a[i]*invn%P; } } vector<int> mul(vector<int> a, vector<int> b) { int n=1; while (n<a.size()+b.size()) n<<=1; int len=a.size()+b.size()-1; a.resize(n); b.resize(n); ntt(a, 0), ntt(b, 0); for (int i=0; i<n; i++) a[i]=1ll*a[i]*b[i]%P; ntt(a, 1); a.resize(len); return a; } }; int main() { vector<int> a={1, 2, 3}; vector<int> b={4, 5, 6}; vector<int> c=NTT::mul(a, b); for (int i:c) printf("%d ", i); puts(""); return 0; } ``` ### 牛顿恒等式 初等对称多项式 * $e_0 = 1$ * $e_1 = x_1 + x_2 + \dots + x_n$ * $e_2 = x_1x_2 + x_1x_3 + \dots + x_{n-1}x_n$ * $e_n = x_1x_2\dots x_n$ (注意：当 $k > n$ 时，$e_k = 0$) 幂和对称多项式 * $p_1 = x_1 + x_2 + \dots + x_n$ * $p_2 = x_1^2 + x_2^2 + \dots + x_n^2$ * $p_k = x_1^k + x_2^k + \dots + x_n^k$ 有 $$ k e_k = \sum_{i=1}^{k} (-1)^{i-1} e_{k-i} p_i $$ 和 $$ p_k = (-1)^{k-1} k e_k + \sum_{i=1}^{k-1} (-1)^{i-1} e_i p_{k-i} $$ #### 多项式优化 - **初等多项式 $E(x)$**：$E[i] = e_i$ （规定 $E[0] = 1$） - **辅助多项式 $A(x)$**：$A[i] = \frac{(-1)^{i-1} p_i}{i} \pmod M$ （规定 $A[0] = 0$） 核心恒等式：$E(x) \equiv \exp(A(x)) \pmod{x^{k+1}}$ $p \to e$ 1. **构造 $A(x)$**：令 $A[0] = 0$。对于 $i \in [1, k]$，计算 $A[i] = (-1)^{i-1} \cdot p_i \cdot i^{-1} \pmod M$。 2. **跑多项式 $\exp$**：计算 $E(x) = \exp(A(x)) \pmod{x^{k+1}}$。 3. **提取答案**：$e_i = E[i]$。 $e \to p$ 1. **构造 $E(x)$**：令 $E[0] = 1$。对于 $i \in [1, k]$，将 $e_i$ 直接填入 $E[i]$。 2. **跑多项式 $\ln$**：计算 $A(x) = \ln(E(x)) \pmod{x^{k+1}}$。 - (Ln 通过 $\int \frac{E'(x)}{E(x)} dx$) 3. **提取答案**：对于 $i \in [1, k]$，计算 $p_i = (-1)^{i-1} \cdot i \cdot A_i\pmod M$。 Loading... ## 基础 ### 一些函数 1. `__builtin_ctz/__builtin_ctzll` 二进制末尾零的个数，不能传入0（f(12)=2） 2. `__builtin_ffs/__builtin_ffsll` 二进制最低位1的位置，0返回0（f(12)=3） 3. `__builtin_popcount/__builtin_popcountll` 求二进制中 1 的个数 4. `__builtin_parity/__builtin_parityll` 二进制下 `1` 的个数 mod 2 5. `__builtin_clz/__builtin_clzll` 二进制下前导 0 的个数，最高位位置/floor(log2(x))=`31-__builtin_clz(x)` 或 `63-__builtin_clzll(x)` 6. `__gcd` 求 $\gcd$，最好不要用 7. `iota(a+1,a+n+1,x)` 表示令a[1]=x,a[i]=a[i-1]+1($1<i\le n$） 8. `fill(a+1, a+n+1, x)` 表示令a[1~n]=x 9. `next_permutation(p+1, p+n+1);` 下一组排列（不止可以用在排列上，初始时升序，最后降序） ### 关闭同步流+cout 保留小数 ```cpp ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout<<fixed<<setprecision(2)<<acos(-1)<<"\n"; ``` ### 离散化 ```cpp for (int i=1; i<=n; i++) a[i]=c[i]=read(); for (int i=1; i<=m; i++) b[i]=c[n+i]=read(); sort(c+1, c+n+m+1); l=unique(c+1, c+n+m+1)-(c+1); for (int i=1; i<=n; i++) a[i]=lower_bound(c+1, c+l+1, a[i])-c; for (int i=1; i<=m; i++) b[i]=lower_bound(c+1, c+l+1, b[i])-c; ``` ### 修改栈空间 `-Wl,--stack=536870912 -O2 -std=c++23` ### 小根堆 `priority_queue<int, vector<int>, greater<int>> q;` ### sort 从大到小排序 `sort(q.begin(), q.end(), greater<int>());` `sort(q.begin(), q.end(), [](PII a, PII b) { return a.first>b.first; });` ### 整数除法上取整/下取整（整型默认是向零取整，也可转double/long double直接用自带函数） ```cpp int ceil(int x, int y) { if (y<0) x=-x, y=-y; return x>=0 ? (x+y-1)/y : x/y; } int floor(int x, int y) { if (y<0) x=-x, y=-y; return x>=0 ? x/y : (x-y+1)/y; } ``` ### 运算符重载 ```cpp struct node { int x, y, z; bool operator < (const node &a) const { return z<a.z; } } e[M]; ``` ### 模拟退火 ```cpp void sa() { ans=calc();//计算初始状态 for (double t=1000; t>1e-10; t*=0.997) {//初始温度、末温度、降温参数根据题目修改 ......//产生一个新的状态，如果类似函数的问题则转移距离要和当前温度有关 double/int/... now=calc(), d=now-ans; //计算新状态的价值和差距 if (d<0) ans=now, ......;//如果更优直接到新的状态并更新状态 if (exp(-1.0*d/t)*RAND_MAX>rand()) ......//如果在一定容差范围内则接受新状态 } } ``` ### CDQ 分治实现三维数点 ```cpp void add(int x, int y) { while (x<N) { c[x]+=y; x+=x&-x; } } int ask(int x) { int r=0; while (x) { r+=c[x]; x-=x&-x; } return r; } int cdq(int l, int r) { if (l==r) return 0; int mid=l+r>>1; int ans=cdq(l, mid)+cdq(mid+1, r); sort(t+l, t+mid+1, [](node x, node y) {return x.b<y.b || x.b==y.b && x.c<y.c;}); sort(t+mid+1, t+r+1, [](node x, node y) {return x.b<y.b || x.b==y.b && x.c<y.c;}); int j=l; for (int i=mid+1; i<=r; i++) { while (j<=mid && t[j].b<=t[i].b) { add(t[j].c, 1); j++; } ans+=ask(t[i].c); } for (int i=l; i<j; i++) add(t[i].c, -1); return ans; } sort(t+1, t+n+1, [](node x, node y) {return x.a<y.a || x.a==y.a && (x.b<y.b || x.b==y.b && x.c<y.c);}); // 严格小于时需按照 a 升，b 降，c 降来排序 ans=cdq(1, n); ``` ## stl & ext & pb_ds ### bitset - `count()`: 返回 `true` 的数量。 - `size()`: 返回 `bitset` 的大小。 - `test(pos)`: 它和 `vector` 中的 `at()` 的作用是一样的，和 `[]` 运算符的区别就是越界检查。 - `any()`: 若存在某一位是 `true` 则返回 `true`，否则返回 `false`。 - `none()`: 若所有位都是 `false` 则返回 `true`，否则返回 `false`。 - `all()`: 若所有位都是 `true` 则返回 `true`，否则返回 `false`。 - 1. `set()`: 将整个 `bitset` 设置成 `true`。 2. `set(pos, val = true)`: 将某一位设置成 `true`/`false`。 - 1. `reset()`: 将整个 `bitset` 设置成 `false`。 2. `reset(pos)`: 将某一位设置成 `false`。相当于 `set(pos, false)`。 - 1. `flip()`: 翻转每一位。（$0\leftrightarrow1$，相当于异或一个全是 $1$ 的 `bitset`） 2. `flip(pos)`: 翻转某一位。 - `to_string()`: 返回转换成的字符串表达。 - `to_ulong()`: 返回转换成的 `unsigned long` 表达（`long` 在 NT 及 32 位 POSIX 系统下与 `int` 一样，在 64 位 POSIX 下与 `long long` 一样）。 - `to_ullong()`:（**C++11** 起）返回转换成的 `unsigned long long` 表达。 另外，libstdc++ 中有一些较为实用的内部成员函数[^bitset1]： - `_Find_first()`: 返回 `bitset` 第一个 `true` 的下标，若没有 `true` 则返回 `bitset` 的大小。 - `_Find_next(pos)`: 返回 `pos` 后面（下标严格大于 `pos` 的位置）第一个 `true` 的下标，若 `pos` 后面没有 `true` 则返回 `bitset` 的大小。 ### set/multiset/unordered_set/unordered_multiset * `insert(x)` 当容器中没有等价元素的时候，将元素 x 插入到 `set` 中。 * `erase(x)` 删除值为 x 的 **所有** 元素，返回删除元素的个数。 * `erase(pos)` 删除迭代器为 pos 的元素，要求迭代器必须合法。 * `erase(first,last)` 删除迭代器在 [first,last) 范围内的所有元素。 * `clear()` 清空 `set`。 * `count(x)` 返回 `set` 内键为 x 的元素数量。 * `find(x)` 在 `set` 内存在键为 x 的元素时会返回该元素的迭代器，否则返回 `end()`。 * `lower_bound(x)` 返回指向首个不小于给定键的元素的迭代器。如果不存在这样的元素，返回 `end()`。 * `upper_bound(x)` 返回指向首个大于给定键的元素的迭代器。如果不存在这样的元素，返回 `end()`。 **一定要用自带的** * `empty()` 返回容器是否为空。 * `size()` 返回容器内元素个数。 ### map/multimap/unordered_map/unordered_multimap * 可以直接通过下标访问来进行查询或插入操作。例如 `mp["Alan"]=100`。 * 通过向 `map` 中插入一个类型为 `pair<Key, T>` 的值可以达到插入元素的目的，例如 `mp.insert(pair<string,int>("Alan",100));`； * `erase(key)` 函数会删除键为 `key` 的 **所有** 元素。返回值为删除元素的数量。 * `erase(pos)`: 删除迭代器为 pos 的元素，要求迭代器必须合法。 * `erase(first,last)`: 删除迭代器在 [first,last) 范围内的所有元素。 * `clear()` 函数会清空整个容器。 * `count(x)`: 返回容器内键为 x 的元素数量。复杂度为 O(\log(size)+ans)（关于容器大小对数复杂度，加上匹配个数）。 * `find(x)`: 若容器内存在键为 x 的元素，会返回该元素的迭代器；否则返回 `end()`。 * `lower_bound(x)`: 返回指向首个不小于给定键的元素的迭代器。 * `upper_bound(x)`: 返回指向首个大于给定键的元素的迭代器。若容器内所有元素均小于或等于给定键，返回 `end()`。 * `empty()`: 返回容器是否为空。 * `size()`: 返回容器内元素个数。 ### rope ```cpp #include <ext/rope> using namespace __gnu_cxx; ``` - `rope<int> a` 初始化 `rope`（与 `vector` 等容器很相似） - `a.push_back(x)` 在 `a` 的末尾添加元素 `x` - `a.insert(pos, x)` 在 `a` 的 `pos` 个位置添加元素 `x` - `a.erase(pos, x)` 在 `a` 的 `pos` 个位置删除 `x` 个元素 - `a.at(x)` 或 `a[x]` 访问 `a` 的第 `x` 个元素 - `a.length()` 或 `a.size()` 获取 `a` 的大小 - `a.replace(pos, x)` 将 `a` 的 `pos` 个位置的元素修改成 `x` - `a.substr(pos, x)` 从 `a` 的第 `pos` 位开始的 `x` 个元素 ### tree（带排名的平衡树） ```cpp #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; ``` 定义： ```cpp typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; ordered_set t; ``` - `t.insert(x)` / `t.erase(x)` / `t.upper_bound(x)` / `t.lower_bound(x)` 用法与 `set` 一致 - `t.find_by_order(k)` 返回指向排名为 `k` 的元素的**迭代器**（0-indexed，第 0 名为最小） - `t.order_of_key(k)` 返回比 `x` **小**的元素的个数（即 `x` 的排名） **eg**（用 pair 实现对重复数据的处理） 1. 插入 $x$ 数 2. 删除 $x$ 数(若有多个相同的数，应只删除一个) 3. 查询 $x$ 数的排名(排名定义为比当前数小的数的个数 $+1$ ) 4. 查询排名为 $x$ 的数 5. 求 $x$ 的前驱(前驱定义为小于 $x$，且最大的数) 6. 求 $x$ 的后继(后继定义为大于 $x$，且最小的数) ```cpp #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } int n, cnt; tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> t; int main() { n=read(); while (n--) { int op=read(), x=read(); if (op==1) t.insert({x, ++cnt}); if (op==2) t.erase(t.lower_bound({x, 0})); if (op==3) printf("%d\n", t.order_of_key({x, 0})+1); if (op==4) printf("%d\n", t.find_by_order(x-1)->first); if (op==5) printf("%d\n", (--t.lower_bound({x, 0}))->first); if (op==6) printf("%d\n", t.lower_bound({x, cnt+1})->first); } return 0; } ``` ### gp_hash_table / cc_hash_table 哈希表 （与 `unordered_map` 用法相同更快） `gp_hash_table` 更小更快 ```cpp #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; gp_hash_table<string, int> h; ``` ### priority_queue 配对堆（可并堆） ```cpp #include <ext/pb_ds/priority_queue.hpp> using namespace __gnu_pbds; typedef priority_queue<int, less<int>, pairing_heap_tag> pbds_pq; ``` 用法基本和 `stl` 中的 `priority_queue` 相同 合并 `pq2` 到 `pq1`，`pq2` 变为空，时间复杂度 $O(1)$ ```cpp pbds_pq pq1; pq1.push(10); pq1.push(30); pbds_pq pq2; pq2.push(20); pq2.push(40); pq1.join(pq2); ``` ## 数据结构 ### RMQ ```cpp for (int j=1; j<=lg[n]; j++) for (int i=1; i<=n-(1<<j)+1; i++) f[i][j]=max(f[i][j-1], f[i+(1<<j-1)][j-1]); for (int i=1; i<=m; i++) { int x=read(), y=read(), z=lg[y-x]; printf("%d\n", max(f[x][z], f[y-(1<<z)+1][z])); } ``` ### 笛卡尔树 ```cpp for (int i=1; i<=n; i++) { while (!s.empty() && a[s.top()]>a[i]) l[i]=s.top(), s.pop(); if (!s.empty()) r[s.top()]=i; s.push(i); } ``` ### 树状数组 ```cpp struct fenwick { int n, c[N]; void clear(int _n) { n=_n; fill(c+1, c+n+1, 0); } void add(int x, int y) { while (x<=n) { c[x]+=y; x+=x&-x; } } int ask(int x) { int r=0; while (x) { r+=c[x]; x-=x&-x; } return r; } int ask(int l, int r) { return ask(r)-ask(l-1); } int kth(int k) { int x=0, sum=0, step=1; while ((step<<1)<=n) step<<=1; while (step) { int nxt=x+step; if (nxt<=n && sum+c[nxt]<k) { x=nxt; sum+=c[nxt]; } step>>=1; } return x+1; } } C; ``` ### 树状数组 区间加、区间和 ```cpp void addd(int x, int v) { int y=x; while (x<=n) { c1[x]+=v; c2[x]+=(y-1)*v; x+=x&-x; } } int askk(int x) { int r=0, y=x; while (x) { r+=c1[x]*y-c2[x]; x-=x&-x; } return r; } void add(int l, int r, int v) {addd(l, v), addd(r+1, -v);} int ask(int l, int r) {return askk(r)-askk(l-1);} ``` ### 分块 ```cpp void add(int l, int r, int c) { int p1=id[l], p2=id[r]; if (p1==p2) { for (int i=l; i<=r; i++) a[i]+=c, s[p1]+=c; return; } for (int i=l; id[i]==p1; i++) a[i]+=c, s[p1]+=c; for (int i=p1+1; i<=p2-1; i++) b[i]+=c, s[i]+=len*c; for (int i=r; id[i]==p2; i--) a[i]+=c, s[p2]+=c; } int ask(int l, int r, int c) { int p1=id[l], p2=id[r], ans=0; if (p1==p2) { for (int i=l; i<=r; i++) ans=(ans+a[i]+b[p1])%c; return ans; } for (int i=l; id[i]==p1; i++) ans=(ans+a[i]+b[p1])%c; for (int i=p1+1; i<=p2-1; i++) ans=(ans+s[i])%c; for (int i=r; id[i]==p2; i--) ans=(ans+a[i]+b[p2])%c; return ans; } { scanf("%lld", &n), len=sqrt(n); for (int i=1; i<=n; i++) { scanf("%lld", &a[i]); id[i]=(i-1)/len+1; s[id[i]]+=a[i]; } for (int i=1; i<=n; i++) { scanf("%lld%lld%lld%lld", &op, &l, &r, &c); if (op==0) add(l, r, c); else printf("%lld\n", ask(l, r, c+1)); } return 0; } ``` ### 莫队 ```cpp struct node { int l, r, id; bool operator < (const node &b) const { return l/len==b.l/len ? r<b.r : l<b.l; } } a[N]; sort(a+1, a+m+1); for (int i=1, l=1, r=0; i<=m; i++) { while (r<a[i].r) add(c[++r]); while (r>a[i].r) del(c[r--]); while (l<a[i].l) del(c[l++]); while (l>a[i].l) add(c[--l]); } ``` ### 线段树 ```cpp struct seg { int s[N*4], t1[N*4], t2[N*4]; void build(int p, int l, int r) { s[p]=t1[p]=0, t2[p]=1; if (l==r) return s[p]=a[l]%P, void(); int mid=l+r>>1; build(lp, l, mid); build(rp, mid+1, r); s[p]=(s[lp]+s[rp])%P; } void pushdown(int p, int l, int r) { int mid=l+r>>1; s[lp]=(s[lp]*t2[p]+t1[p]*(mid-l+1))%P; s[rp]=(s[rp]*t2[p]+t1[p]*(r-mid))%P; t2[lp]=(t2[lp]*t2[p])%P; t2[rp]=(t2[rp]*t2[p])%P; t1[lp]=(t1[lp]*t2[p]+t1[p])%P; t1[rp]=(t1[rp]*t2[p]+t1[p])%P; t1[p]=0, t2[p]=1; } void mul(int p, int l, int r, int L, int R, int k) { if (L<=l && r<=R) { t1[p]=t1[p]*k%P; t2[p]=t2[p]*k%P; s[p]=s[p]*k%P; return; } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) mul(lp, l, mid, L, R, k); if (R>mid) mul(rp, mid+1, r, L, R, k); s[p]=(s[lp]+s[rp])%P; } void add(int p, int l, int r, int L, int R, int k) { if (L<=l && r<=R) { s[p]=(s[p]+k*(r-l+1))%P; t1[p]=(t1[p]+k)%P; return; } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) add(lp, l, mid, L, R, k); if (R>mid) add(rp, mid+1, r, L, R, k); s[p]=(s[lp]+s[rp])%P; } int ask(int p, int l, int r, int L, int R) { if (L<=l && r<=R) return s[p]; pushdown(p, l, r); int mid=l+r>>1, res=0; if (L<=mid) res+=ask(lp, l, mid, L, R); if (R>mid) res+=ask(rp, mid+1, r, L, R); return res%P; } } S; ``` ### 线段树（区间加、赋值） ```cpp struct seg { int s[N*4], mn[N*4], t1[N*4], t2[N*4]; void pushup(int p) { s[p]=s[lp]+s[rp]; mn[p]=min(mn[lp], mn[rp]); } void build(int p, int l, int r) { t1[p]=-1;//assign lazy tag t2[p]=0;//add lazy tag if (l==r) { s[p]=mn[p]=a[l]; return; } int mid=l+r>>1; build(lp, l, mid); build(rp, mid+1, r); pushup(p); } void pushdown(int p, int l, int r) { int mid=l+r>>1; if (t1[p]!=-1) { Assign(lp, l, mid, t1[p]); Assign(rp, mid+1, r, t1[p]); t1[p]=-1; } if (t2[p]!=0) { Add(lp, l, mid, t2[p]); Add(rp, mid+1, r, t2[p]); t2[p]=0; } } void Assign(int p, int l, int r, int k) { s[p]=k*(r-l+1); mn[p]=t1[p]=k; t2[p]=0; } void assign(int p, int l, int r, int L, int R, int k) { if (L<=l && r<=R) { Assign(p, l, r, k); return; } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) assign(lp, l, mid, L, R, k); if (R>mid) assign(rp, mid+1, r, L, R, k); pushup(p); } void Add(int p, int l, int r, int k) { mn[p]+=k; s[p]+=(r-l+1)*k; t2[p]+=k; } void add(int p, int l, int r, int L, int R, int k) { if (L<=l && r<=R) { Add(p, l, r, k); return; } pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) add(lp, l, mid, L, R, k); if (R>mid) add(rp, mid+1, r, L, R, k); pushup(p); } int ask(int p, int l, int r, int L, int R) { if (L<=l && r<=R) return s[p]; pushdown(p, l, r); int mid=l+r>>1, res=0; if (L<=mid) res=ask(lp, l, mid, L, R); if (R>mid) res+=ask(rp, mid+1, r, L, R); return res; } int ask2(int p, int l, int r, int L, int R) { if (L<=l && r<=R) return mn[p]; pushdown(p, l, r); int mid=l+r>>1, res=1e9; if (L<=mid) res=ask2(lp, l, mid, L, R); if (R>mid) res=min(res, ask2(rp, mid+1, r, L, R)); return res; } } S; ``` ### 动态开点线段树 ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=100000*25; int n, m, lp[N], rp[N], tag[N], s[N], rt, num; void pushdown(int p, int l, int r) { if (!tag[p] || l==r) return; int mid=l+r>>1; if (!lp[p]) lp[p]=++num; if (!rp[p]) rp[p]=++num; tag[lp[p]]+=tag[p]; tag[rp[p]]+=tag[p]; s[lp[p]]+=(mid-l+1)*tag[p]; s[rp[p]]+=(r-mid)*tag[p]; tag[p]=0; } void add(int &p, int l, int r, int L, int R, int v) { if (!p) p=++num; if (L<=l && r<=R) return s[p]+=(r-l+1)*v, tag[p]+=v, void(); pushdown(p, l, r); int mid=l+r>>1; if (L<=mid) add(lp[p], l, mid, L, R, v); if (R>mid) add(rp[p], mid+1, r, L, R, v); s[p]=s[lp[p]]+s[rp[p]]; } int ask(int p, int l, int r, int L, int R) { if (!p) return 0; if (L<=l && R>=r) return s[p]; pushdown(p, l, r); int res=0, mid=(l+r)/2; if (L<=mid) res+=ask(lp[p], l, mid, L, R); if (R>mid) res+=ask(rp[p], mid+1, r, L, R); return res; } signed main() { n=read(), m=read(); for (int i=1; i<=n; i++) add(rt, 1, n, i, i, read()); while (m--) { if (read()==1) { int l=read(), r=read(), v=read(); add(rt, 1, n, l, r, v); } else { int l=read(), r=read(); printf("%lld\n", ask(rt, 1, n, l, r)); } } return 0; } ``` ### 线段树合并 ```cpp int merge(int a, int b, int l, int r) { if (!a || !b) return a|b; if (l==r) { s[a]+=s[b]; return a; } int mid=l+r>>1; ls[a]=merge(ls[a], ls[b], l, mid); rs[a]=merge(rs[a], rs[b], mid+1, r); s[a]=s[ls[a]]+s[rs[a]]; return a; } ``` ## 数学 ### 十二重计数之八 #### 1. 球相同，盒子不同，不能有空盒 **公式**：$\binom{n-1}{m-1}$ **解释**：**隔板法**。$n-1$ 个缝隙插 $m-1$ 块板。 #### 2. 球相同，盒子不同，可以有空盒 **公式**：$\binom{n+m-1}{m-1}$ **解释**：**借球法**。先给 $m$ 个盒子各借 1 球转化为“不能有空盒”。 #### 3. 球不同，盒子不同，可以有空盒 **公式**：$m^n$ **解释**：每个球独立选择 $m$ 个盒子，乘法原理 $m^n$。 #### 4. 球不同，盒子相同，不能有空盒 **基本公式**：第二类斯特林数 $S(n,m)$ **递推公式**： $$ S(n, m) = S(n-1, m-1) + m \cdot S(n-1, m) $$ *解释：第 $n$ 个球独占一盒 $S(n-1, m-1)$，或放入已有 $m$ 盒之一 $m \cdot S(n-1, m)$。* **容斥原理显式**： $$ S(n,m) = \frac{1}{m!} \sum_{k=0}^{m} (-1)^k \binom{m}{k} (m-k)^n $$ *解释：用总映射 $m^n$ 容斥扣掉有空盒情况，再除以 $m!$ 消除盒子顺序。* 补充：上升幂 $x^{\overline{n}} = \prod_{k=0}^{n-1}(x+k)$。 $x^{\overline{n}} = \sum_{k} \left[ \begin{matrix} n \\ k \end{matrix} \right] x^k$ $x^{n} = \sum_{k} \left\{ \begin{matrix} n \\ k \end{matrix} \right\} (-1)^{n-k} x^{\overline{k}}$ 下降幂 $x^{\underline{n}} = \frac{x!}{(x-n)!} = \prod_{k=0}^{n-1}(x-k)$。 $x^{n} = \sum_{k} \left\{ \begin{matrix} n \\ k \end{matrix} \right\} x^{\underline{k}}= \sum_{k} \left\{ \begin{matrix} n \\ k \end{matrix} \right\} \binom{x}{k}k!$ $x^{\underline{n}} = \sum_{k} \left[ \begin{matrix} n \\ k \end{matrix} \right] (-1)^{n-k} x^{k}$ $\left\{ \begin{matrix} n \\ k \end{matrix} \right\}$ 表示**第二类斯特林数**，$\left[ \begin{matrix} n \\ k \end{matrix} \right]$ 表示**无符号第一类斯特林数**。 #### 5. 球不同，盒子不同，不能有空盒 **公式**：$m! \cdot S(n,m)$ **容斥直接求法（满射数）** $$ \sum_{k=0}^{m} (-1)^k \binom{m}{k} (m-k)^n $$ **解释**：在情况 4 基础上乘 $m!$ 给盒子赋予编号；用容斥求即为全集减去有空盒。 #### 6. 球不同，盒子相同，可以有空盒 **公式**：$\sum_{i=1}^{\min(n,m)} S(n,i)$ **解释**：按实际非空盒子数 $i$ 累加。 **贝尔数（当 $m \ge n$ 时，记为 $B_n$）**： **贝尔数递推公式**： $$ B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k $$ *解释：固定第 $n+1$ 个球，假设它所在集合还有 $k$ 个球，从剩下 $n$ 个球选 $k$ 个组合。* #### 7. 球相同，盒子相同，可以有空盒 **记号**：整数拆分 $P(n,m)$ **递推公式**： $$ P(n,m) = P(n,m-1) + P(n-m, m) \quad (n \ge m) $$ **解释**：有空盒扔掉一盒 $P(n,m-1)$；无空盒则每盒先发 1 球 $P(n-m, m)$。 #### 8. 球相同，盒子相同，不能有空盒 **公式**：$P(n-m, m)$ **解释**：每盒先垫 1 个球满足非空，剩下的 $n-m$ 个球转化为“可以有空盒”求解。 ### 组合 ```cpp int fac[N], inv[N]; int power(int x, int y) { int r=1; while (y) { if (y&1) r=r*x%P; x=x*x%P; y>>=1; } return r; } void init(int n) { fac[0]=1; for (int i=1; i<=n; i++) fac[i]=fac[i-1]*i%P; inv[n]=power(fac[n], P-2); for (int i=n-1; ~i; i--) inv[i]=inv[i+1]*(i+1)%P; } int C(int n, int m) { if (n<0 || m<0 || n<m) return 0; return fac[n]*inv[m]%P*inv[n-m]%P; } ``` ### 线性筛 ```cpp void init(int n) { for (int i=2; i<=n; i++) { if (!vis[i]) p[++cnt]=i; for (int j=1; j<=cnt && i*p[j]<=n; j++) { vis[i*p[j]]=1; if (i%p[j]==0) break; } } } ``` ### 狄利克雷前后缀和 前缀和：令 $f_i$ 表示答案为 $i$ 时候的方案数，求答案为 $i$ 的因数时的方案数。 ```cpp for (int i=1; i<=cnt; i++) for (int j=1; j<=n/p[i]; j++) f[j*p[i]]+=f[j]; ``` 后缀和：令 $f_i$ 表示答案为 $i$ 时候的方案数，求答案为 $i$ 的倍数时的方案数。 ```cpp for (int i=1; i<=cnt; i++) for (int j=n/p[i]; j>=1; j--) f[j]+=f[j*p[i]]; ``` 倒前缀和：令 $f_i$ 表示答案为 $i$ 因数时的方案数，求答案为 $i$ 时的方案数。 ```cpp for (int i=cnt; i>=1; i--) for (int j=n/p[i]; j>=1; j--) f[j*p[i]]-=f[j]; ``` 倒后缀和：令 $f_i$ 表示答案为 $i$ 倍数时的方案数，求答案为 $i$ 是的方案数。 ```cpp for (int i=cnt; i>=1; i--) for (int j=1; j<=n/p[i]; j++) f[j]-=f[j*p[i]]; ``` ### 线性基 ```cpp void insert(int x) { for(int i=55; i>=0; i--) { if (!((x>>i)&1)) continue; if(a[i]) { x^=a[i]; if (!x) return; } else { for (int j=i-1; j>=0; j--) if (x>>j&1) x^=a[j]; a[i]=x; for (int j=55; j>i; j--) if (a[j]>>i&1) a[j]^=x; return; } } } ``` ### 整除分块 所有满足 $\lfloor \frac{n}{i} \rfloor = d$ 的整数 $i$ 的取值范围为： $$ \lfloor \frac{n}{d+1} \rfloor + 1 \le i \le \lfloor \frac{n}{d} \rfloor $$ 所有满足 $\lceil \frac{n}{i} \rceil = d$ 的整数 $i$ 的取值范围为： $$ \lceil \frac{n}{d} \rceil \le i \le \lceil \frac{n}{d-1} \rceil - 1 $$ ### 莫比乌斯反演 **积性函数** 若 $\gcd(x,y) = 1$ 且 $f(xy)=f(x)f(y)$，则 $f(n)$ 为积性函数。 若 $f(x)$，$g(x)$均为积性函数，则以下函数也为积性函数： $$ \begin{aligned} & h(x) = f(x^p)\\ & h(x) = f^p(x)\\ & h(x) = f(x)g(x)\\ & h(x) = \sum_{d\mid x} f(d)g\left(\dfrac{x}{d}\right) \end{aligned} $$ **常见积性函数** * 单位函数 $e(n) = [n = 1]$。 * 幂函数 $\operatorname{Id}_{k}(n) = n^k$， $\operatorname{id}_1(n)$ 通常简记为$\operatorname{id}(n)$。 * 常数函数 $1(n) = 1$。 * 因数个数 $\operatorname{d}(n) = \sum\limits_{d\mid n} 1$。 * 除数函数 $\sigma_{k}(n) = \sum\limits_{d\mid n} d^k$。 * 欧拉函数 $\varphi(n) = \sum\limits_{i=1}^{n} [\gcd(i,n) = 1]$。 * 莫比乌斯函数 $$ \mu(n) = \begin{cases} 1 &n=1\\0 &n\ \text{含有平方因子}\\(-1)^k &k\text{为}\ n\ \text{的本质不同质因子个数} \end{cases} $$ **性质** $$ \large \sum_{d\mid n} \mu (d) = [n=1] $$ **反演常用** $$ [\gcd(i,j) = 1] = \sum\limits_{d\mid \gcd(i,j)} {\mu (d)} $$ **狄利克雷卷积** $$ \large(f\ast g) (n) = \sum_{d\mid n} f(d)g\left(\dfrac{n}{d}\right) $$ 1. 满足交换律，结合律，分配律。 * $f \ast g = g \ast f$ * $(f \ast g) \ast h = f\ast (g\ast h)$ * $f\ast (g+h) = f\ast g + f\ast h$ 2. $e$ 为狄利克雷卷积的单位元，有$(f\ast e)(n) = f(n)$。 3. 若 $f,g$ 为积性函数，则 $f\ast g$ 为积性函数。 **单位元** $e$ $$ (\mu\ast\mathbf 1)(n)=\sum_{d\mid n}\mu(d)=e(n)=[n=1] $$ **除数函数与幂函数** 幂函数 $\operatorname{Id}_{k}(n) = n^k$。 除数函数 $\sigma_{k}(n) = \sum\limits_{d\mid n} d^k$。 $$ (\operatorname{Id}_k\ast 1)(n) = \sum_{d\mid n} \operatorname{Id_k}(d) = \sum_{d\mid n} d^k = \sigma_k(n) $$ **欧拉函数与恒等函数** $$ \begin{aligned} \varphi \ast 1 =& \operatorname{Id}\\ \varphi =& \operatorname{Id}\ast \mu \end{aligned} $$ **恒等式** $$ n = \sum_{d\vert{}n} \varphi(d) $$ **莫比乌斯反演** 如果有 $$ f(n)=\sum_{d\mid n}g(d) $$ 那么 $$ g(n) = \sum_{d\mid n}\mu(d)f\left(\frac nd\right) = \sum_{d\mid n}\mu\left(\frac nd\right)f(d) $$ **证明** $$ f=g\ast\mathbf 1 $$ 所以 $$ f\ast\mu = g\ast\mathbf 1\ast\mu = g\ast e = g $$ **一些例子** $$ \begin{aligned} \mu\ast\mathbf 1&=e,\\ \operatorname{id}_k\ast\mathbf 1&=\sigma_k, &\sigma_k\ast\mu&=\operatorname{id}_k,\\ \varphi\ast\mathbf 1&=\operatorname{id}, &\operatorname{id}\ast\mu&=\varphi,\\ \mathbf 1\ast\mathbf 1&=\tau. \end{aligned} $$ **应用举例** $$ \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=1] = \sum_{d=1}^{\min(n,m)} \mu(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor $$ ### 裴蜀定理 $ax+by=c$ 有整数解**当且仅当** $\gcd(a,b)\mid c$ ### 威尔逊定理 当且仅当 $p$ 为质数时满足 $(p-1)!\equiv -1\pmod p$ ### EXGCD ```cpp int exgcd(int a, int b, int &x, int &y) { if (b==0) { x=1; y=0; return a; } int g=exgcd(b, a%b, y, x); y-=a/b*x; return g; } void calc(int a, int b, int c, int &x, int &y) { int g=exgcd(a, b, x, y); if (c%g!=0) { x=y=0; return; } a/=g, b/=g, c/=g; x*=c, y*=c;//任意一组解 int del=((x%b+abs(b))%b-x)/b; x+=del*b; y-=del*a;//x最小自然数解 if (x==0) x+=abs(b), y-=a*b/abs(b);//x最小正整数解 } ``` ### 中国剩余定理 ```cpp M=1, ans=0; for (int i=1; i<=n; i++) { cin>>m[i]>>a[i]; M*=m[i]; } for (int i=1; i<=n; i++) { int k=M/m[i], t, x; int g=exgcd(k, m[i], t, x); t=(t%m[i]+m[i])%m[i]; ans=(ans+(__int128)t*k%M*a[i])%M; } ans=(ans+M)%M; ``` ### EX中国剩余定理 ```cpp int excrt(vector<int> mm, vector<int> aa) { int M=mm[0], A=aa[0]; for (int i=1; i<mm.size(); i++) { int m=mm[i], a=aa[i], k, t; int g=exgcd(M, m, k, t); int c=((a-A)%m+m)%m; if (c%g) return -1; int p=m/g; k=((__int128)c/g*k%p+p)%p; A=(A+(__int128)k*M)%(M*p); M*=p; } return A; } ``` ### 线性求逆元 ```cpp inv[1]=1; for (int i=2; i<N; i++) inv[i]=(P-inv[P%i])*(P/i)%P; for (int i=1; i<=100; i++) printf("%lld %lld\n", inv[i], power(i, P-2)); ``` ### 欧拉函数 ```cpp int phi(int n) { int ans=n; for (int i=2; i*i<=n; i++) if (n%i==0) { ans=ans/i*(i-1); while (n%i==0) n/=i; } if (n>1) ans=ans/n*(n-1); return ans; } ``` #### 线性求欧拉函数 ```cpp void init(int n) { phi[1]=1; for (int i=2; i<=n; i++) { if (!vis[i]) p[++cnt]=i, phi[i]=i-1; for (int j=1; j<=cnt && i*p[j]<=n; j++) { vis[i*p[j]]=1; if (i%p[j]) phi[i*p[j]]=phi[i]*phi[p[j]]; else {phi[i*p[j]]=phi[i]*p[j]; break;} } } } ``` ### 扩展欧拉定理 $$ a^b \equiv \begin{cases} a^{b \bmod \varphi(m)}, &\gcd(a,m) = 1, \\ a^b, &\gcd(a,m)\ne 1, b < \varphi(m), \\ a^{(b \bmod \varphi(m)) + \varphi(m)}, &\gcd(a,m)\ne 1, b \ge \varphi(m). \end{cases} \pmod m $$ ### BSGS $$ a^{i\cdot t-j}\equiv b\pmod p\Rightarrow a^{i\cdot t}\equiv b\cdot a^j\pmod p $$ ```cpp int power(int x, int y, int p) { int r=1; while (y) { if (y&1) r=r*x%p; x=x*x%p; y>>=1; } return r; } int bsgs(int a, int b, int p) { unordered_map<int, int> f; int t=ceil(sqrt(p)); for (int i=1; i<=t; i++) b=b*a%p, f[b]=i; int tmp=power(a, t, p), s=1; for (int i=1; i<=t; i++) { s=s*tmp%p; if (f.count(s)) return i*t-f[s]; } return -1; } ``` ### 高斯消元 ```cpp for (int i=1; i<=n; i++) { int pos=i; for (int j=i+1; j<=n; j++) if (fabs(a[j][i])>fabs(a[pos][i])) pos=j; if (pos!=i) swap(a[pos], a[i]); if (fabs(a[i][i])<1e-9) return puts("No Solution"), 0; for (int j=1; j<=n; j++) { if (i==j) continue; double t=a[j][i]/a[i][i]; for (int k=1; k<=n+1; k++) a[j][k]-=a[i][k]*t; } } //a[i][n+1]/a[i][i] ``` ### 最简行阶梯形 ```cpp int rank=0; for (int j=1; j<=m && rank<n; j++) { int pos=-1; for (int i=rank+1; i<=n; i++) if (a[i][j]==1) {pos=i; break;} if (pos==-1) continue; rank++; swap(a[rank], a[pos]); for (int i=1; i<=n; i++) { if (i==rank || a[i][j]==0) continue; for (int k=1; k<=m; k++) a[i][k]^=a[rank][k]; } } ``` ### 拉格朗日插值 ```cpp int lagrange(int n, int *x, int *y, int X) { int ans=0; for (int i=1; i<=n; i++) { int s1=1, s2=1; for (int j=1; j<=n; j++) { if (i==j) continue; s1=s1*(X-x[j])%p; s2=s2*(x[i]-x[j])%p; } ans=(ans+y[i]*s1%p*power(s2, p-2)%p)%p; } return (ans+p)%p; } ``` ### 矩阵（vector 常数较大） ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int n, k; struct matrix{ int n, m, p=1e9+7; vector<vector<int> > a; matrix(int _n=0, int _m=0) { n=_n, m=_m; if (m==0) m=n; a=vector<vector<int> >(n+1, vector<int> (m+1)); } void mod(int _p) {p=_p;} vector<int>& operator[](int x) & {return a[x];} const vector<int>& operator[](int x) const& {return a[x];} void read() { for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) scanf("%lld", &a[i][j]); } void write() { for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) printf("%lld ", a[i][j]); printf("\n"); } } matrix operator * (const matrix &b) const { assert(m==b.n); matrix r(n, b.m); for (int i=1; i<=n; i++) for (int k=1; k<=m; k++) for (int j=1; j<=b.m; j++) r[i][j]=(r[i][j]+1ll*a[i][k]*b[k][j])%p; return r; } matrix operator ^ (int k) const { assert(n==m || k<=1); matrix r(m), a=*this; for (int i=1; i<=m; i++) r[i][i]=1; while (k) { if (k&1) r=r*a; a=a*a; k>>=1; } return r; } }; signed main() { scanf("%lld%lld", &n, &k); matrix a(n); a.read(); (a^k).write(); return 0; } ``` ### 大素数测试与分解质因数与计算所有因数（Miller-Rabin & Pollard-Rho） 时间复杂度：素性检测：$O(\sqrt{n})$，分解：$O(n^{\frac{1}{4}})$ ```cpp #define int long long namespace price { using i128=__int128; int mul(int a, int b, int m) { return (i128)a*b%m; } int power(int x, int y, int P) { int r=1; while (y) { if (y&1) r=mul(r, x, P); x=mul(x, x, P); y>>=1; } return r; } bool isprime(int n) { if (n<2) return 0; if (n%2==0) return n==2; int d=n-1, s=__builtin_ctzll(d); d>>=s; // 可换成 {2, 325, 9375, 28178, 450775, 9780504, 1795265022} 更快 for (int a:{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) { if (n%a==0) return n==a; int x=power(a, d, n); if (x==1 || x==n-1) continue; for (int i=1; i<s && x!=n-1; i++) x=mul(x, x, n); if (x!=n-1) return 0; } return 1; } int nxt(int x, int n) { return (mul(x, x, n)+1)%n; } int rho(int n) { if (n%2==0) return 2; if (n%3==0) return 3; for (int st=2;; st++) { int x=st, y=st, d=1; int pw=1, len=0, v=1; while (d==1) { y=nxt(y, n); ++len; v=mul(v, abs(x-y), n); if (len%127==0) { d=gcd(v, n); v=1; } if (pw==len) { x=y; pw<<=1; len=0; d=gcd(v, n); v=1; } } if (d!=n) return d; } } vector<int> a; void fac(int n) { if (n<10000) { for (int i=2; i*i<=n; i++) { while (n%i==0) a.push_back(i), n/=i; } if (n>1) a.push_back(n); } else if (isprime(n)) a.push_back(n); else { int d=rho(n); fac(d); fac(n/d); } } vector<int> factorize(int n) { //分解质因数 a.clear(); if (n>1) fac(n); sort(a.begin(), a.end()); return a; } vector<int> divisor(int n) { //所有因数 vector<int> p=factorize(n), d{1}; for (int i=0; i<p.size();) { int j=i, x=1, m=d.size(); while (j<p.size() && p[j]==p[i]) { x*=p[i]; for (int k=0; k<m; k++) d.push_back(d[k]*x); j++; } i=j; } sort(d.begin(), d.end()); return d; } }; ``` ## 图论 ### Pick 定理 给定顶点均为整点的简单多边形，皮克定理说明了其面积 ${\displaystyle A}$ 和内部格点数目 ${\displaystyle i}$、边上格点数目 ${\displaystyle b}$ 的关系：${\displaystyle A=i+{\frac {b}{2}}-1}$． ### 欧拉公式 在一个不和自己交叉的多面体中，面的个数+顶点（角）的个数-棱的个数=2，${\displaystyle V-E+F=2}$ ### 倍增 LCA ```cpp void dfs(int x, int fa) { f[x][0]=fa; dep[x]=dep[fa]+1; for (int i=1; i<=22; i++) f[x][i]=f[f[x][i-1]][i-1]; for (int y:e[x]) if (y!=fa) dfs(y, x); } int lca(int x, int y) { if (dep[x]<dep[y]) swap(x, y); for (int i=22; i>=0; i--) if (dep[f[x][i]]>=dep[y]) x=f[x][i]; if (x==y) return x; for (int i=22; i>=0; i--) if (f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i]; return f[x][0]; } ``` ### Floyd 最短路 ```cpp for (int k=1; k<=n; k++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) f[i][j]=min(f[i][j], f[i][k]+f[k][j]); ``` ### Dijkstra 最短路 ```cpp void dijkstra(int s) { fill(dis+1, dis+n+1, 1e18); fill(vis+1, vis+n+1, 0); dis[s]=0; priority_queue<pair<int, int> > q; q.push({0, s}); while (!q.empty()) { int x=q.top().second; q.pop(); if (vis[x]) continue; vis[x]=1; for (auto [y, z]:e[x]) { if (dis[y]>dis[x]+z) { dis[y]=dis[x]+z; q.push({-dis[y], y}); } } } } ``` ### SPFA 最短路 ```cpp bool spfa(int s) { fill(dis+1, dis+n+1, 1e18); fill(vis+1, vis+n+1, 0); fill(cnt+1, cnt+n+1, 0); dis[s]=0, vis[s]=1; queue<int> q; q.push(s); while (!q.empty()) { int x=q.front(); q.pop(), vis[x]=0; for (auto [y, z]:e[x]) { if (dis[y]>dis[x]+z) { dis[y]=dis[x]+z; cnt[y]=cnt[x]+1; if (cnt[y]>n) return 0; if (!vis[y]) { q.push(y); vis[y]=1; } } } } return 1; } ``` ### Johnson 全源最短路 ```cpp bool spfa(int s) { fill(h, h+n+1, 1e18); fill(vis, vis+n+1, 0); fill(cnt, cnt+n+1, 0); h[s]=0, vis[s]=1; queue<int> q; q.push(s); while (!q.empty()) { int x=q.front(); q.pop(), vis[x]=0; for (auto [y, z]:e[x]) { if (h[y]>h[x]+z) { h[y]=h[x]+z; cnt[y]=cnt[x]+1; if (cnt[y]>n) return 0; if (!vis[y]) { q.push(y); vis[y]=1; } } } } return 1; } void dijkstra(int s) { fill(dis, dis+n+1, 1e18); fill(vis, vis+n+1, 0); dis[s]=0; priority_queue<pair<int, int> > q; q.push({0, s}); while (!q.empty()) { int x=q.top().second; q.pop(); if (vis[x]) continue; vis[x]=1; for (auto [y, z]:e[x]) { if (dis[y]>dis[x]+z) { dis[y]=dis[x]+z; q.push({-dis[y], y}); } } } } void Johnson() { for (int i=1; i<=n; i++) e[0].emplace_back(i, 0); if (!spfa(0)) return puts("-1"), void(); for (int x=1; x<=n; x++) for (auto &[y, z]:e[x]) z+=h[x]-h[y]; for (int i=1; i<=n; i++) { dijkstra(i); for (int j=1; j<=n; j++) dist[i][j]=(dis[j]==1e18 ? 1e18 : dis[j]+h[j]-h[i]); } } ``` ### Kruskal 最小生成树 ```cpp struct node { int x, y, z; bool operator < (const node &a) const { return z<a.z; } } e[M]; int find(int x) {return fa[x]==x ? x : fa[x]=find(fa[x]);} int main() { n=read(), m=read(); for (int i=1; i<=m; i++) e[i].x=read(), e[i].y=read(), e[i].z=read(); sort(e+1, e+m+1); for (int i=1; i<=n; i++) fa[i]=i; int cnt=0; for (int i=1; i<=m; i++) { int x=find(e[i].x), y=find(e[i].y); if (x==y) continue; ans+=e[i].z; fa[x]=y; cnt++; if (cnt==n-1) break; } if (cnt<n-1) printf("orz\n"); else printf("%d\n", ans); return 0; } ``` ### PRIM 最小生成树 ```cpp for (int i=1; i<=m; i++) { int x=read(), y=read(), z=read(); e[x].emplace_back(y, z); e[y].emplace_back(x, z); } fill(dis, dis+n+1, 1e9); dis[1]=0; for (int i=1; i<=n; i++) { int x=0; for (int j=1; j<=n; j++) if (!vis[j] && dis[j]<dis[x]) x=j; if (!x) return puts("orz"), 0; vis[x]=1; ans+=dis[x]; for (auto [y, z] : e[x]) if (!vis[y] && z<dis[y]) dis[y]=z; } ``` ### Boruvka 最小生成树 ```cpp int boruvka() { fill(vis+1, vis+m+1, 0); iota(fa+1, fa+n+1, 1); int cnt=0, status=1; while (status) { status=0; fill(best+1, best+n+1, 0); for (int i=1; i<=m; i++) { if (vis[i]) continue; int x=find(e[i].x), y=find(e[i].y); if (x==y) continue; if (best[x]==0 || e[i].z<e[best[x]].z) best[x]=i; if (best[y]==0 || e[i].z<e[best[y]].z) best[y]=i; } for (int i=1; i<=n; i++) if (best[i] && !vis[best[i]]) { status=1; cnt++; ans+=e[best[i]].z; vis[best[i]]=1; int x=find(e[best[i]].x); int y=find(e[best[i]].y); fa[x]=y; } } if (cnt==n-1) return ans; return -1; } ``` ### 树上启发式合并 ```cpp void dfs1(int x, int fa) { sz[x]=1, big[x]=0; for (int y:e[x]) { if (y==fa) continue; dfs1(y, x); sz[x]+=sz[y]; if (sz[y]>sz[big[x]]) big[x]=y; } } void add(int x, int fa, int v) { if (v==1) { cnt[c[x]]++; if (cnt[c[x]]==1) sum++; } else { cnt[c[x]]--; if (cnt[c[x]]==0) sum--; } for (int y:e[x]) if (y!=fa) add(y, x, v); } void dfs2(int x, int fa, bool keep) { for (int y:e[x]) if (y!=fa && y!=big[x]) dfs2(y, x, 0); if (big[x]) dfs2(big[x], x, 1); cnt[c[x]]++; if (cnt[c[x]]==1) sum++; for (int y:e[x]) if (y!=fa && y!=big[x]) add(y, x, 1); ans[x]=sum; if (!keep) add(x, fa, -1); } dfs1(1, 0); dfs2(1, 0, true); ``` ### 点分治（eg.树上是否存在距离为k的点对） ```cpp #include <bits/stdc++.h> using namespace std; const int N=1e4+10; int n, m, rt, q[N], cnt, tot, sz[N], mx[N], dis[N], num[N], tmp[N], maxq; bool vis[N], ans[N]; vector<char> flag; vector<pair<int, int> > e[N]; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } void dfsroot(int x, int fa) { sz[x]=1, mx[x]=0; for (auto [y, z]:e[x]) { if (y==fa || vis[y]) continue; dfsroot(y, x); sz[x]+=sz[y]; mx[x]=max(mx[x], sz[y]); } mx[x]=max(mx[x], tot-sz[x]); if (mx[x]<mx[rt]) rt=x; } void dfssize(int x, int fa) { sz[x]=1; for (auto [y, z]:e[x]) { if (y==fa || vis[y]) continue; dfssize(y, x); sz[x]+=sz[y]; } } void dfs(int x, int fa) { if (dis[x]>maxq) return; num[++cnt]=dis[x]; for (auto [y, z]:e[x]) { if (y==fa || vis[y]) continue; dis[y]=dis[x]+z; dfs(y, x); } } void calc(int x) { int t=0; for (auto [y, z]:e[x]) { if (vis[y]) continue; cnt=0; dis[y]=z; dfs(y, x); for (int j=1; j<=cnt; j++) for (int k=1; k<=m; k++) if (q[k]>=num[j]) ans[k]|=flag[q[k]-num[j]]; for (int j=1; j<=cnt; j++) { flag[num[j]]=1; tmp[++t]=num[j]; } } for (int i=1; i<=t; i++) flag[tmp[i]]=0; } void dfz(int x) { dfssize(x, 0); vis[x]=1; flag[0]=1; calc(x); for (auto [y, z]:e[x]) { if (vis[y]) continue; tot=sz[y]; mx[rt=0]=1e9; dfsroot(y, x); dfz(rt); } } int main() { n=read(), m=read(); for (int i=1; i<n; i++) { int x=read(), y=read(), z=read(); e[x].emplace_back(y, z); e[y].emplace_back(x, z); } for (int i=1; i<=m; i++) q[i]=read(), maxq=max(maxq, q[i]); flag.assign(maxq+1, 0); tot=n, mx[rt]=1e9; dfsroot(1, 0), dfz(rt); for (int i=1; i<=m; i++) printf(ans[i] ? "AYE\n" : "NAY\n"); return 0; } ``` ### tarjan SCC（有向图缩点）（注：scc编号为反拓扑序） ```cpp void tarjan(int x) { dfn[x]=low[x]=++num; s.push(x); ins[x]=1; for (int y:e[x]) { if (!dfn[y]) { tarjan(y); low[x]=min(low[x], low[y]); } else if (ins[y]) low[x]=min(low[x], dfn[y]); } if (dfn[x]==low[x]) { int y; cnt++; do { y=s.top(); s.pop(); ins[y]=0; bel[y]=cnt, scc[cnt].push_back(y); } while (x!=y); } } for (int i=1; i<=n; i++) if (!dfn[i]) tarjan(i); for (int x=1; x<=n; x++) for (int y:e[x]) if (bel[x]!=bel[y]) add_c(bel[x], bel[y]); ``` ### tarjan V-DCC（无向图割点+割点缩点） ```cpp void tarjan(int x, int rt) { dfn[x]=low[x]=++num; s.push(x); if (x==rt && e[x].empty()) return dcc[++cnt].push_back(x), void(); int flag=0; for (int y:e[x]) { if (!dfn[y]) { tarjan(y, rt); low[x]=min(low[x], low[y]); if (low[y]>=dfn[x]) { if (x!=rt || (++flag)>1) cut[x]=1; int z; cnt++; do { z=s.top(); s.pop(); dcc[cnt].push_back(z); } while (z!=y); dcc[cnt].push_back(x); } } else low[x]=min(low[x], dfn[y]); } } for (int i=1; i<=n; i++) if (!dfn[i]) tarjan(i, i); ``` #### 圆方树 ```cpp void tarjan(int x, int rt) { dfn[x]=low[x]=++num; s.push(x); if (x==rt && e[x].empty()) { cnt++; E[n+cnt].push_back(x); E[x].push_back(n+cnt); return; } int flag=0; for (int y:e[x]) { if (!dfn[y]) { tarjan(y, rt); low[x]=min(low[x], low[y]); if (low[y]>=dfn[x]) { int z; cnt++; do { z=s.top(); s.pop(); E[n+cnt].push_back(z); E[z].push_back(n+cnt); } while (z!=y); E[n+cnt].push_back(x); E[x].push_back(n+cnt); } } else low[x]=min(low[x], dfn[y]); } } ``` #### 记录每个点双中的边 ```cpp void tarjan(int x, int fa, int rt) { dfn[x]=low[x]=++num; s.push(x); if (x==rt && e[x].empty()) return dcc[++cnt].push_back(x), void(); int flag=0; for (int y:e[x]) { if (y==fa) continue; if (!dfn[y]) { se.push({x, y}); tarjan(y, x, rt); low[x]=min(low[x], low[y]); if (low[y]>=dfn[x]) { if (x!=rt || (++flag)>1) cut[x]=1; int z; cnt++; pair<int, int> ze; do { ze=se.top(); se.pop(); ecc[cnt].push_back(ze); } while (ze!=make_pair(x, y)); do { z=s.top(); s.pop(); dcc[cnt].push_back(z); } while (z!=y); dcc[cnt].push_back(x); } } else { low[x]=min(low[x], dfn[y]); if (dfn[y]<dfn[x]) se.push({x, y}); } } } for (int i=1; i<=n; i++) if (!dfn[i]) tarjan(i, 0, i); ``` ### tarjan E-BCC（无向图割边+割边缩点） ```cpp void tarjan(int x, int fa) { dfn[x]=low[x]=++num; s.push(x), ins[x]=1; for (int y:e[x]) { if (!dfn[y]) { tarjan(y, x); low[x]=min(low[x], low[y]); if (low[y]>dfn[x]) bridge.push_back({x, y});//割边 } else if (y!=fa) low[x]=min(low[x], dfn[y]); } if (low[x]==dfn[x]) {//缩点 int y; cnt++; do { y=s.top(); s.pop(); ins[y]=0; bel[y]=cnt, bcc[cnt].push_back(y); } while (x!=y); } } for (int i=1; i<=n; i++) if (!dfn[i]) tarjan(i, 0); ``` #### 链式前向星写法 ```cpp int tot=1; void add(int x, int y) { ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot; } void tarjan(int x, int id) { dfn[x]=low[x]=++num; for (int i=head[x]; i; i=nxt[i]) { int y=ver[i]; if (!dfn[y]) { tarjan(y, i); low[x]=min(low[x], low[y]); if (low[y]>dfn[x]) bridge[i]=bridge[i^1]=1; } else if (i!=(id^1)) low[x]=min(low[x], dfn[y]); } } ``` ### 欧拉路径 ```cpp void dfs(int x) { while (!e[x].empty()) { auto [y, id]=e[x].back(); e[x].pop_back(); if (!vis[id]) { vis[id]=1; dfs(y); ans.push_back(id); } } } ``` ```cpp int n, m, st, in[N], out[N], cur[N]; vector<int> e[N]; stack<int> s; void dfs(int x) { while (cur[x]<e[x].size()) { int y=e[x][cur[x]++]; dfs(y); s.push(y); } } int main() { n=read(), m=read(); for (int i=1; i<=m; i++) { int x=read(), y=read(); e[x].push_back(y); in[y]++; out[x]++; } for (int i=1; i<=n; i++) sort(e[i].begin(), e[i].end()); st=1; int tot=0, flag=0; for (int i=1; i<=n; i++) { if (abs(in[i]-out[i])) tot++; if (abs(in[i]-out[i])>1) flag=1; } if (tot>2 || flag) return puts("No"), 0; for (int i=1; i<=n; i++) if (out[i]==in[i]+1) {st=i; break;} dfs(st); s.push(st); while (!s.empty()) printf("%d ", s.top()), s.pop(); return 0; } ``` ### 网络最大流 时间复杂度：$O(kE)\sim O(V^2E)$ 二分图：$O(E\sqrt V)$ ```cpp #define ll long long namespace flow { int n, s, t, d[N], cnt=1, head[N], cur[N], to[M], nxt[M]; ll val[M]; void addedge(int x, int y, ll z) { to[++cnt]=y; val[cnt]=z; nxt[cnt]=head[x]; head[x]=cnt; } void add(int x, int y, ll z) { addedge(x, y, z); addedge(y, x, 0); } void init(int _n, int _s, int _t) { cnt=1, n=_n, s=_s, t=_t; fill(head+1, head+n+1, 0); } bool bfs() { for (int i=1; i<=n; i++) cur[i]=head[i], d[i]=0; queue<int> q; q.push(s), d[s]=1; while (!q.empty()) { int x=q.front(); q.pop(); for (int i=head[x]; i; i=nxt[i]) { int y=to[i]; if (d[y] || !val[i]) continue; d[y]=d[x]+1; q.push(y); if (y==t) return 1; } } return 0; } ll dinic(int x, ll flow) { if (x==t) return flow; ll rest=flow; for (int &i=cur[x]; i; i=nxt[i]) { int y=to[i]; if (d[y]!=d[x]+1 || !val[i]) continue; ll k=dinic(y, min(rest, val[i])); if (!k) d[y]=0; val[i]-=k; val[i^1]+=k; rest-=k; if (!rest) break; } return flow-rest; } ll maxflow() { ll res=0; while (bfs()) res+=dinic(s, INF); return res; } }; ``` ### 最小费用最大流 最坏情况：$O(VE+KE\log V)$ ```cpp #define ll long long namespace flow { struct node { int y, e; } p[N]; int head[N], vis[N], to[M], nxt[M]; ll dis[N], h[N], val[M], cost[M]; int n, s, t, cnt=1; void addedge(int x, int y, ll f, ll c) { to[++cnt]=y; val[cnt]=f; cost[cnt]=c; nxt[cnt]=head[x]; head[x]=cnt; } void add(int x, int y, ll f, ll c) { addedge(x, y, f, c); addedge(y, x, 0, -c); } void init(int _n, int _s, int _t) { n=_n, s=_s, t=_t, cnt=1; fill(head+1, head+n+1, 0); } bool dijkstra() { priority_queue<pair<ll, int> > q; for (int i=1; i<=n; i++) dis[i]=INF; for (int i=1; i<=n; i++) vis[i]=0; dis[s]=0; q.push({0, s}); while (!q.empty()) { int x=q.top().second; q.pop(); if (vis[x]) continue; vis[x]=1; for (int i=head[x]; i; i=nxt[i]) { int y=to[i]; ll nc=cost[i]+h[x]-h[y]; if (val[i] && dis[y]>dis[x]+nc) { dis[y]=dis[x]+nc; p[y].y=x; p[y].e=i; if (!vis[y]) q.push({-dis[y], y}); } } } return dis[t]!=INF; } void spfa() { queue<int> q; fill(h+1, h+n+1, INF); fill(vis+1, vis+n+1, 0); h[s]=0, vis[s]=1; q.push(s); while (!q.empty()) { int x=q.front(); q.pop(); vis[x]=0; for (int i=head[x]; i; i=nxt[i]) { int y=to[i]; if (val[i] && h[y]>h[x]+cost[i]) { h[y]=h[x]+cost[i]; if (!vis[y]) { vis[y]=1; q.push(y); } } } } } pair<ll, ll> calc(ll lim=INF) { if (s==t || lim<=0) return {0, 0}; ll maxf=0, minc=0; spfa(); /* 若没有负数费用，可将 spfa(); 替换成 fill(h+1, h+n+1, 0); */ while (maxf<lim && dijkstra()) { ll minf=lim-maxf; for (int i=1; i<=n; i++) if (dis[i]!=INF) h[i]+=dis[i]; for (int i=t; i!=s; i=p[i].y) minf=min(minf, val[p[i].e]); for (int i=t; i!=s; i=p[i].y) { val[p[i].e]-=minf; val[p[i].e^1]+=minf; } maxf+=minf; minc+=minf*h[t]; } return {maxf, minc}; } }; ``` ### 重链剖分 ```cpp #include <cstdio> #include <cctype> #include <vector> #include <algorithm> #define int long long using namespace std; const int N=4e5+10; int fa[N], dep[N], siz[N], son[N], top[N], dfn[N], rnk[N]; int n, m, rt, mod, a[N], cnt; int l[N], r[N], s[N], t[N]; vector<int> e[N]; int read() { int x=0, f=0; char ch=getchar(); while (!isdigit(ch)) {f|=ch=='-'; ch=getchar();} while (isdigit(ch)) {x=(x<<3)+(x<<1)+(ch^48); ch=getchar();} return f?-x:x; } void dfs1(int x) { dep[x]=dep[fa[x]]+1; siz[x]=1; for (int i=0; i<e[x].size(); i++) { int y=e[x][i]; if (y==fa[x]) continue; fa[y]=x; dfs1(y); siz[x]+=siz[y]; if (siz[y]>siz[son[x]]) son[x]=y; } } void dfs2(int x, int t) { top[x]=t; dfn[x]=++cnt; rnk[cnt]=x; if (!son[x]) return; dfs2(son[x], t); for (int i=0; i<e[x].size(); i++) if(e[x][i]!=fa[x] && e[x][i]!=son[x]) dfs2(e[x][i], e[x][i]); } int lca(int x, int y) { while (top[x]!=top[y]) if (dep[top[x]]>dep[top[y]]) x=fa[top[x]]; else y=fa[top[y]]; return dep[x]<dep[y] ? x : y; } #define lp p<<1 #define rp p<<1|1 void build(int p, int L, int R) { l[p]=L, r[p]=R; if (L==R) { s[p]=a[rnk[L]]; return; } int mid=L+R>>1; build(lp, L, mid); build(rp, mid+1, R); s[p]=(s[lp]+s[rp])%mod; } void pushdown(int p) { s[lp]=(s[lp]+(r[lp]-l[lp]+1)*t[p])%mod; s[rp]=(s[rp]+(r[rp]-l[rp]+1)*t[p])%mod; t[lp]=(t[lp]+t[p])%mod, t[rp]=(t[rp]+t[p])%mod, t[p]=0; } void change(int p, int L, int R, int v) { if (L<=l[p] && r[p]<=R) { t[p]=(t[p]+v)%mod; s[p]=(s[p]+(r[p]-l[p]+1)*v)%mod; return; } pushdown(p); int mid=l[p]+r[p]>>1; if (L<=mid) change(lp, L, R, v); if (R>mid) change(rp, L, R, v); s[p]=(s[lp]+s[rp])%mod; } int query(int p, int L, int R) { if (L<=l[p] && r[p]<=R) return s[p]; pushdown(p); int mid=l[p]+r[p]>>1, r=0; if (L<=mid) r=(r+query(lp, L, R))%mod; if (R>mid) r=(r+query(rp, L, R))%mod; return r; } void change_tree(int x, int v) { change(1, dfn[x], dfn[x]+siz[x]-1, v); } int query_tree(int x) { return query(1, dfn[x], dfn[x]+siz[x]-1); } void change_chain(int x, int y, int z) { int fx=top[x], fy=top[y]; while (fx!=fy) { if (dep[fx]>=dep[fy]) change(1, dfn[fx], dfn[x], z), x=fa[fx]; else change(1, dfn[fy], dfn[y], z), y=fa[fy]; fx=top[x], fy=top[y]; } change(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), z); } int query_chain(int x, int y) { int res=0, fx=top[x], fy=top[y]; while (fx!=fy) { if (dep[fx]>=dep[fy]) res=(res+query(1, dfn[fx], dfn[x]))%mod, x=fa[fx]; else res=(res+query(1, dfn[fy], dfn[y]))%mod, y=fa[fy]; fx=top[x], fy=top[y]; } res=(res+query(1, min(dfn[x], dfn[y]), max(dfn[x], dfn[y])))%mod; return res; } signed main() { n=read(), m=read(), rt=read(), mod=read(); for (int i=1; i<=n; i++) a[i]=read(); for (int i=1; i<n; i++) { int x=read(), y=read(); e[x].push_back(y); e[y].push_back(x); } dfs1(rt); dfs2(rt, rt); build(1, 1, n); while (m--) { int opt=read(); if (opt==1) { int x=read(), y=read(), z=read();; change_chain(x, y, z); } else if (opt==2) { int x=read(), y=read(); printf("%lld\n", query_chain(x, y)); } else if (opt==3) { int x=read(), z=read(); change_tree(x, z); } else { int x=read(); printf("%lld\n", query_tree(x)); } } return 0; } ``` ### 长链条剖分求 k 级祖先 ```cpp void dfs1(int x, int fa) { dep[x]=dep[fa]+1; f[x][0] = fa; for (int i=1; i<=20; i++) f[x][i]=f[f[x][i-1]][i-1]; for (int y:e[x]) { if (y==fa) continue; dfs1(y, x); if (len[y]>len[son[x]]) son[x]=y; } len[x] = len[son[x]] + 1; } void dfs2(int x, int tp) { top[x]=tp; if (x==tp) { for (int y=x, i=0; y&&i<len[x]; i++, y=f[y][0]) up[x].push_back(y); for (int y=x, i=0; y&&i<len[x]; i++, y=son[y]) down[x].push_back(y); } if (son[x]) dfs2(son[x], tp); for (int y:e[x]) if (y!=f[x][0] && y!=son[x]) dfs2(y, y); } int query(int x, int k) { if (k==0) return x; if (k>=dep[x]) return 0; int i=__lg(k); x=f[x][i], k-=(1<<i); int tp=top[x]; if (dep[x]-dep[tp]>=k) return down[tp][dep[x]-dep[tp]-k]; else return up[tp][k-(dep[x]-dep[tp])]; } ``` ### 长链剖分优化DP（eg.CF1009F，求每个点子树中深度为多少的点最多，注意存储方式） ```cpp #include <bits/stdc++.h> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=1e6+10; int n, buf[N], *now=buf, *f[N], ans[N]; int len[N], son[N]; vector<int> e[N]; void dfs1(int x, int fa) { for (int y:e[x]) { if (y==fa) continue; dfs1(y, x); if (len[y]>len[son[x]]) son[x]=y; } len[x]=len[son[x]]+1; } void dfs2(int x, int fa) { f[x][0]=1; if (son[x]) { f[son[x]]=f[x]+1; dfs2(son[x], x); ans[x]=ans[son[x]]+1; } for (int y:e[x]) { if (y==fa || y==son[x]) continue; f[y]=now, now+=len[y]; dfs2(y, x); for (int i=1; i<=len[y]; i++) { f[x][i]+=f[y][i-1]; if (f[x][i]>f[x][ans[x]] || f[x][i]==f[x][ans[x]] && i<ans[x]) ans[x]=i; } } if (f[x][ans[x]]==1) ans[x]=0; } signed main() { n=read(); for (int i=1; i<n; i++) { int x=read(), y=read(); e[x].push_back(y); e[y].push_back(x); } dfs1(1, 0); f[1]=now, now+=len[1]; dfs2(1, 0); for (int i=1; i<=n; i++) printf("%d\n", ans[i]); return 0; } ``` ## 字符串 ### 字典树（trie） ```cpp struct trie { int cnt=1, tr[M][26], sum[M], vis[M]; void clear() { for (int i=1; i<=cnt; i++) { sum[i]=0, vis[i]=0; for (int j=0; j<26; j++) tr[i][j]=0; } cnt=1; } void insert(char *s) { int l=strlen(s), p=1; for (int i=0; i<l; i++) { int c=s[i]-'a'; if (!tr[p][c]) tr[p][c]=++cnt; p=tr[p][c]; } vis[p]=1; } bool find(char *s) { int l=strlen(s), p=1; for (int i=0; i<l; i++) { int c=s[i]-'a'; if (!tr[p][c]) return 0; p=tr[p][c]; } return vis[p]; } } tr; ``` ### Hash 哈希 ```cpp const int base=2333; const int P1=1000000053; const int P2=1000000097; struct Hash { int h1[N], h2[N]; int p1[N], p2[N]; void init(string s) { int n=s.size(); p1[0]=p2[0]=1; h1[0]=h2[0]=0; for (int i=0; i<n; i++) { p1[i+1]=(1ll*p1[i]*base)%P1; p2[i+1]=(1ll*p2[i]*base)%P2; h1[i+1]=(1ll*h1[i]*base+s[i])%P1; h2[i+1]=(1ll*h2[i]*base+s[i])%P2; } } // 查询区间 [l, r] (0-based) pair<int, int> query(int l, int r) { int len=r-l+1; int r1=(h1[r+1]-1ll*h1[l]*p1[len]%P1+P1)%P1; int r2=(h2[r+1]-1ll*h2[l]*p2[len]%P2+P2)%P2; return {r1, r2}; } } sh; ``` ### KMP $s2[1\to next[i]]=s2[i-next[i]+1\to i]$ $s2[1\to f[i]]=s1[i-f[i]+1\to i]$ ```cpp n=strlen(s2+1), m=strlen(s1+1); nxt[1]=0; for (int i=2, j=0; i<=n; i++) { while (j>0 && s2[i]!=s2[j+1]) j=nxt[j]; if (s2[i]==s2[j+1]) j++; nxt[i]=j; } for (int i=1, j=0; i<=m; i++) { while (j>0 && (j==n || s1[i]!=s2[j+1])) j=nxt[j]; if (s1[i]==s2[j+1]) j++; if ((f[i]=j)==n) printf("%d\n", i-n+1); } ``` ### exKMP/Z 函数 $t[1\to z[i]]=t[i\to i+z[i]-1]$ $t[1\to p[i]]=s[i\to i+p[i]-1]$ ```cpp int n=strlen(s+1), m=strlen(t+1); z[1]=m; for (int i=2, l=0; i<=m; i++) { z[i]=0; if (l+z[l]>i) z[i]=min(z[i-l+1], l+z[l]-i); while (i+z[i]<=m && t[z[i]+1]==t[i+z[i]]) z[i]++; if (i+z[i]>l+z[l]) l=i; } for (int i=1, l=0; i<=n; i++) { p[i]=0; if (l+p[l]>i) p[i]=min(z[i-l+1], l+p[l]-i); while (i+p[i]<=n && p[i]<m && t[p[i]+1]==s[i+p[i]]) p[i]++; if (i+p[i]>l+p[l]) l=i; } ``` ### 马拉车/Manacher ```cpp int init(char *s) { int len=strlen(s+1), j=0; st[j++]='$', st[j++]='#'; for (int i=1; i<=len; i++) { st[j++]=s[i]; st[j++]='#'; } st[j++]='^'; st[j]='\0'; return j; } int manacher(char *s) { int ans=0, len=init(s); for (int i=1, mid=0, r=0; i<len; i++) { p[i]=(i<=r) ? min(r-i, p[2*mid-i]) : 0; while (st[i+p[i]+1]==st[i-p[i]-1]) p[i]++; if (i+p[i]>r) r=i+p[i], mid=i; ans=max(ans, p[i]); } return ans; } ``` ### 最小表示法 ```cpp int findmin(char *s) { int k=0, i=1, j=2; while (k<n && i<=n && j<=n) { if (s[(i+k-1)%n+1]==s[(j+k-1)%n+1]) k++; else { if (s[(i+k-1)%n+1]>s[(j+k-1)%n+1]) i=i+k+1; else j=j+k+1; if (i==j) i++; k=0; } } return min(i, j); } ``` ## 多项式 ### NTT ```cpp #include <bits/stdc++.h> using namespace std; namespace NTT { const int N=1<<21, P=998244353, G=3, Gi=(P+1)/3; int rev[N], A[N], B[N]; int power(int x, int y) { int r=1; while (y) { if (y&1) r=1ll*r*x%P; x=1ll*x*x%P, y>>=1; } return r; } void ntt(int *a, int n, int inv) { for (int i=0; i<n; i++) { rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0); if (i<rev[i]) swap(a[i], a[rev[i]]); } for (int len=1; len<n; len<<=1) { int wn=power(inv==1 ? G : Gi, (P-1)/(len<<1)); for (int i=0; i<n; i+=(len<<1)) { for (int j=0, w=1; j<len; j++, w=1ll*w*wn%P) { int x=a[i+j], y=1ll*w*a[i+j+len]%P; a[i+j]=(x+y)%P; a[i+j+len]=(x-y+P)%P; } } } if (inv==-1) { int invn=power(n, P-2); for (int i=0; i<n; i++) a[i]=1ll*a[i]*invn%P; } } void mul(int *a, int n, int *b, int m, int *r) { int L=1; while (L<n+m-1) L<<=1; for (int i=0; i<L; i++) A[i]=i<n ? a[i] : 0; for (int i=0; i<L; i++) B[i]=i<m ? b[i] : 0; ntt(A, L, 1), ntt(B, L, 1); for (int i=0; i<L; i++) A[i]=1ll*A[i]*B[i]%P; ntt(A, L, -1); for (int i=0; i<n+m-1; i++) r[i]=A[i]; } } int a[9]={1, 2, 3}; int b[9]={4, 5, 6}; int main() { int n=3, m=3; NTT::mul(a, n, b, m, a); for (int i=0; i<n+m-1; i++) printf("%d ", a[i]); puts(""); return 0; } ``` #### vector 实现 ```cpp #include <bits/stdc++.h> using namespace std; const int P=998244353, G=3; namespace NTT { int power(int x, int y) { int r=1; while (y) { if (y&1) r=1ll*r*x%P; x=1ll*x*x%P, y>>=1; } return r; } void ntt(vector<int> &a, bool inv) { int n=a.size(); for (int i=0, j=0; i<n; i++) { if (i<j) swap(a[i], a[j]); for (int k=n>>1; (j^=k)<k; k>>=1); } for (int len=2; len<=n; len<<=1) { int wlen=power(G, (P-1)/len); if (inv) wlen=power(wlen, P-2); for (int i=0; i<n; i+=len) { int w=1; for (int j=0; j<len/2; j++) { int u=a[i+j], v=1ll*w*a[i+j+len/2]%P; a[i+j]=(u+v)%P; a[i+j+len/2]=(u-v+P)%P; w=1ll*w*wlen%P; } } } if (inv) { int invn=power(n, P-2); for (int i=0; i<n; i++) a[i]=1ll*a[i]*invn%P; } } vector<int> mul(vector<int> a, vector<int> b) { int n=1; while (n<a.size()+b.size()) n<<=1; int len=a.size()+b.size()-1; a.resize(n); b.resize(n); ntt(a, 0), ntt(b, 0); for (int i=0; i<n; i++) a[i]=1ll*a[i]*b[i]%P; ntt(a, 1); a.resize(len); return a; } }; int main() { vector<int> a={1, 2, 3}; vector<int> b={4, 5, 6}; vector<int> c=NTT::mul(a, b); for (int i:c) printf("%d ", i); puts(""); return 0; } ``` ### 牛顿恒等式 初等对称多项式 * $e_0 = 1$ * $e_1 = x_1 + x_2 + \dots + x_n$ * $e_2 = x_1x_2 + x_1x_3 + \dots + x_{n-1}x_n$ * $e_n = x_1x_2\dots x_n$ (注意：当 $k > n$ 时，$e_k = 0$) 幂和对称多项式 * $p_1 = x_1 + x_2 + \dots + x_n$ * $p_2 = x_1^2 + x_2^2 + \dots + x_n^2$ * $p_k = x_1^k + x_2^k + \dots + x_n^k$ 有 $$ k e_k = \sum_{i=1}^{k} (-1)^{i-1} e_{k-i} p_i $$ 和 $$ p_k = (-1)^{k-1} k e_k + \sum_{i=1}^{k-1} (-1)^{i-1} e_i p_{k-i} $$ #### 多项式优化 - **初等多项式 $E(x)$**：$E[i] = e_i$ （规定 $E[0] = 1$） - **辅助多项式 $A(x)$**：$A[i] = \frac{(-1)^{i-1} p_i}{i} \pmod M$ （规定 $A[0] = 0$） 核心恒等式：$E(x) \equiv \exp(A(x)) \pmod{x^{k+1}}$ $p \to e$ 1. **构造 $A(x)$**：令 $A[0] = 0$。对于 $i \in [1, k]$，计算 $A[i] = (-1)^{i-1} \cdot p_i \cdot i^{-1} \pmod M$。 2. **跑多项式 $\exp$**：计算 $E(x) = \exp(A(x)) \pmod{x^{k+1}}$。 3. **提取答案**：$e_i = E[i]$。 $e \to p$ 1. **构造 $E(x)$**：令 $E[0] = 1$。对于 $i \in [1, k]$，将 $e_i$ 直接填入 $E[i]$。 2. **跑多项式 $\ln$**：计算 $A(x) = \ln(E(x)) \pmod{x^{k+1}}$。 - (Ln 通过 $\int \frac{E'(x)}{E(x)} dx$) 3. **提取答案**：对于 $i \in [1, k]$，计算 $p_i = (-1)^{i-1} \cdot i \cdot A_i\pmod M$。 最后修改：2026 年 09 月 04 日 © 允许规范转载 赞 7 如果觉得我的文章对你有用，请随意赞赏
1 条评论
wow！！(´இ皿இ｀)