https://wiki.cvbbacm.com/ 2026-04-29T23:32:08+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-08-07T14:27:05+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%8D%8A%E5%B9%B3%E9%9D%A2%E4%BA%A4&rev=1596781625&do=diff 半平面交 给定n个形如 $ax+by+c\le0$ 的半平面，找到所有满足它们的点所组成的额点集，称为半平面交。 相交后的区域可能是直线、射线、线段或者点，甚至也有可能是空集。 求解算法 排序增量法 把半平面分成两部分，一部分是极角范围内的 $(-\frac{\pi}{2},\frac{\pi}{2})$$(-\frac{\pi}{2},\frac{\pi}{2})$$n$ text/html 2020-05-13T17:49:25+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E7%BA%BF%E6%AE%B5%E6%A0%91&rev=1589363365&do=diff 可持久化线段树 一道例题 洛谷p3919 你需要维护一个长度为$N$的数组，支持对历史版本单点的修改和查询。 每次操作都把历史版本的线段树复制一遍？时间复杂度$O(nm)$，显然会超时。 我们发现，其实大部分的节点都是可以重复利用的，只需要对修改节点时所途径的节点复制即可。这大概就是可持久化的思想。 text/html 2020-05-11T17:28:25+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%9B%A2%E9%98%9F%E4%BC%9A%E8%AE%AE%E8%AE%B0%E5%BD%95&rev=1589189305&do=diff 2020/05/08 1.讨论了每周比赛的时间 2.选定了本周的比赛 3.讨论了比赛的策略 text/html 2020-07-16T22:24:30+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%89%8D%E7%BC%80%E5%87%BD%E6%95%B0%E4%B8%8E_kmp_%E7%AE%97%E6%B3%95_lgwza&rev=1594909470&do=diff 前缀函数与 KMP 算法 字符串前缀和后缀定义 关于字符串前缀、真前缀，后缀、真后缀的定义详见 字符串基础 前缀函数定义 给定一个长度为 $n$ 的字符串 $s$，其前缀函数被定义为一个长度为 $n$$\pi$$\pi[i]$$s[0\ldots i]$$s[0\ldots k-1]$$s[i-(k-1)\ldots i]$$\pi[i]$$\pi[i]=k$$\pi[i]$$\pi[i]=0$$\pi[i]$$s[0\ldots i]$$$ \pi[i]=\max_{k=0\ldots i}\{k:s[0\ldots k-1]=s[i-(k-1)\ldots i]\} $$$\pi[0]=0$$\pi[0]=0$$0$$\pi[1]=0$$\pi[2]=0$$\pi[3]=1$$1$$\pi[4]=2$$2$$\pi[5]=3$$3$$\pi[6]=0$$[0,1,0,1,2,2,3]$$i=1\rightarrow n-1$$\pi[i]$$\pi[0]$$0$$\pi[i]$$j$$i$$\pi[i]$$j$$1$$j=0$$j=0$$\pi[i]=0$$i+1$$O(… text/html 2020-07-24T16:17:27+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84_lgwza&rev=1595578647&do=diff 后缀数组(SA) 一些约定 字符串相关的定义请参考字符串基础 字符串下标从 $1$ 开始。 “后缀 $i$”代指以第 $i$ 个字符开头的后缀。 后缀数组是什么？ 后缀数组(Suffix Array)主要是两个数组：$sa$ 和 $rk$$sa[i]$$i$$rk[i]$$i$$sa[rk[i]]=rk[sa[i]]=i$$O(n)$$O(n^2\log n)$$1$$w$$rk_w[1..n]$$rk_w[i]$$s[i..\min(i+w-1,n)]$$\{s[x..\min(x+w-1,n)]|x\in[1,n]\}$$rk_w[i]$$rk_w[i+w]$$i+w>n$$rk_w[i+w]$$rk_{2w}[1..n]$$O(n\log^2n)$$O(n\log^2n)$$O(n\log n)$$O(n)$$O(n\log n)$$O(n)$$O(n)$$s[i+w..i+2w-1]$$rk$$p$$p$$rk$$O(n\log n)$$O(n)$$S$$SS$$T$$S$$T$$S$$T$$S$$S$$T$$T$$sa$$S$$O(|S|)$$O(|S|\log … text/html 2021-02-24T06:40:56+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%91%A8%E6%8A%A5%E6%A8%A1%E6%9D%BF_legal_string&rev=1614120056&do=diff 2021/xx/xx--2021/xx/xx 周报 团队训练 姜一凡 专题 比赛 题目 蒋贤蒙 专题 比赛 题目 王赵安 专题 比赛 题目 本周推荐 姜一凡 蒋贤蒙 王赵安 text/html 2020-07-16T22:13:29+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%AD%97%E5%85%B8%E6%A0%91_trie_lgwza&rev=1594908809&do=diff 字典树(Trie) 字典树，英文名 trie。顾名思义，就是一个像字典一样的树。 简介 先放一张图： [ trie1] 可以发现，这棵字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。举个例子， $1\rightarrow4\rightarrow8\rightarrow12$$\delta(u,c)$$u$$c$$u$$c$$c$$0\sim26$$n$$m$$1\le n\le 10^4,1\le m\le 10^5$$50$$\{0,1\}$$(u,v)$$u$$v$$10^5$$[0,2^{31})$$root$$T(u,v)$$u$$v$$T(u,v)=T(root,u)\oplus T(root,v)$$T(root,u)$$T(root,u)$$T(root,v)$$T(root,u)$$1$$0$${0,1}$$V_1,V_2,V_3,\cdots,V_n$$V_1+1,V_2+1,V_3+1,\cdots,V_n+1$… text/html 2020-07-15T18:44:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D_lgwza&rev=1594809840&do=diff 字符串匹配 字符串匹配问题 单串匹配 一个模式串(pattern)，一个待匹配串，找出前者在后者中的所有出现位置。 多串匹配 多个模式串，一个待匹配串（多个待匹配串可以直接连起来）。$O(nm)$$O(n)$$O(n)$ text/html 2020-07-15T18:42:37+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%9F%BA%E7%A1%80_lgwza&rev=1594809757&do=diff 字符串基础 定义 字符集 一个字符集 $\sum$ 是一个建立了全序关系的集合，也就是说，$\sum$ 中的任意两个不同的元素 $\alpha$ 和 $\beta$ 都可以比较大小，要么 $\alpha<\beta$，要么 $\beta<\alpha$。字符集 $\sum$ 中的元素称为字符。 字符串 一个$n$$n$$S$$|S|$$S$$i$$S[i]$$S[i-1]$$i$$S$$S[i..j]$$i\le j$$S$$i$$j$$S[i],S[i+1],\cdots,S[j]$$S[i..j],i>j$$S$$S$$S[p_1],S[p_2],\cdots,S[p_k],1\le p_1<p_2<\cdots<p_k\le |S|$$i$$S$$i$$Suffix(S,i)$$Suffix(S,i)=S[i..|S|-1]$$S$$S$$i$$S$$i$$Prefix(S,i)$$Prefix(S,i)=S[0..i]$$S$$S$$i$$i$$a<aa$$\forall~1\le i\le|S|,S[i]=s[|S|+1-i]$$S$… text/html 2020-07-15T18:49:20+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%93%88%E5%B8%8C_lgwza&rev=1594810160&do=diff 字符串哈希 Hash 的思想 Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。 " 这里的“值域较小”在不同情况下意义不同。 在哈希表中，值域需要小到能够接受线性的空间与时间复杂度。$10^9、10^{18}$$f$$f$$f$$f(s)=\sum s[i]\times b^i\pmod{M}$$b$$M$$b$$M$$[0,M)$$\frac 1 M$$n$$\frac{1}{M}$$1-(1-\frac1M)^n$$M=10^9+7,n=10^6$$\frac1{1000}$$O(n)$$n$$b$$M$$f_i(s)$$f(s[1..i])$$f(s[l..r])=\frac{f_r(s)-f_{l-1}(s)}{b^{l-1}}$$b^{l-1}$$b$$O(n)$$O(1)$$O(n\log n)$$O(n)$… text/html 2020-07-03T22:25:50+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E6%95%B0%E8%AE%BA%E6%A6%82%E8%AE%BA%E5%AD%A6%E4%B9%A0%E5%B0%8F%E7%BB%93_lgwza&rev=1593786350&do=diff 数论概论学习小结 第5章 整除性与最大公因数 定理 5.1 （欧几里得算法） 要计算两个整数 $a$ 与 $b$ 的最大公因数，先令 $r_{-1}=a$ 且 $r_{0}=b$， 然后计算相继的商和余数 $$ r_{i-1}=q_{i+1} \times r_i+r_{i+1} (i = 0,1,2,\dots) $$ 直到某余数 $r_{n+1}$ 为 $0$. 最后的非零余数 $r_n$ 就是 $a$$b$$a$$b$$g=gcd(a,b).$$$ax+by=g$$$(x_1,y_1)$$$( x_1+k\cdot\frac{b}{g},y_1-k\cdot\frac{a}{g} )$$$k$$p$$p$$ab$$p$$a$$p$$b$$p$$a$$b$$p$$a_1a_2\dots a_r$$p$$a_1,a_2,\dots,a_r$$n \ge 2$$$ n=p_1p_2\dots p_r $$$m$$a-b$$a$$b$$m$$$ a \equiv b \pmod{m} $$$m$$$ a_1 \equiv b_1 \pmod{m}, a_2 \equiv b_2 \… text/html 2020-08-04T22:21:08+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E6%A0%91%E9%93%BE%E5%89%96%E5%88%86_lgwza&rev=1596550868&do=diff 树链剖分 树链剖分的思想及能解决的问题 树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。 具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。$O(\log n)$$O(\log n)$$$ \begin{array}{l}\text{TREE-BUILD}(u,dep)\\ \begin{array}{ll} 1 & u.hson\gets 0\\ 2&u.hson.size\gets 0\\ 3 & u.deep\gets dep\\ 4&u.size\gets 1\\ 5 & \textbf{for}\ \text{each}\ u\text{'s son}\ v\\ 6 & \qquad u.size\gets u.size+\text{TREE-BUILD}(v,dep+1)\\ 7 & \qquad v.father\gets u\\ 8 & \qquad \textbf{if}\ v.size>u.hson.size\\ 9 & \qquad\qquad u.hson\gets v\\ 10 & \textbf{retur… text/html 2021-01-27T16:28:44+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0_lgwza&rev=1611736124&do=diff 欧拉函数 定义 $1\sim N$ 中与 $N$ 互质的数的个数叫欧拉函数, 记为 $\varphi(N)$ 对 $N$ 分解质因数 $N=p_1^{c_1}\times p_2^{c_2}\times\cdots\times p_k^{c_k}$ 特别地, $\varphi(1)=1$ 性质 * $\varphi(N)=N\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times\cdots\times(1-\frac{1}{p_k})$ * 若有 $p\ |\ N$, 且满足 $p^2\ |\ N$, 则 $\varphi(N)=\varphi(N/p)*p$ * 若有 $p\ |\ N$, 且一定不满足 $p^2\ |\ N$, 则 $\varphi(N)=\varphi(N/p)*(p-1)$ * $\forall N>1, 1\sim N$ 中与 $N$ 互质的数的和为 $N*\varphi(N)/2$ * 当 $a,b$ 互质时, 有 $\varphi(a*b)=\varphi(a)*\varph… text/html 2022-08-08T09:56:10+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%8E%8B%E6%99%BA%E5%BD%AA&rev=1659923770&do=diff back 知识点 字符串 AC自动机 后缀平衡树 后缀数组 后缀自动机 回文自动机 序列自动机 exKMP 多项式 FFT NTT FWT 多项式求逆 常系数齐次线性递推 计算几何 扫描线 反演 新计算几何总结 其余项 网络流入门 数理知识 博弈论 博弈论新总结 类欧几里得算法 缓冲区 数论 比赛 Educational Codeforces Round 111 text/html 2020-07-08T20:21:26+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%BA%BF%E6%80%A7%E7%AD%9B_lgwza&rev=1594210886&do=diff 线性筛素数、欧拉函数、莫比乌斯函数、约数个数、约数和 #include<bits/stdc++.h> using namespace std; const int N=1e7+5; int p[N];//质数表 int phi[N];//欧拉函数 int mu[N];//莫比乌斯函数 int d[N];//约数个数 int mi[N];//最小质因子次数 int sigma[N];//约数和 int mp[N];//由最小质因子组成的数的约数和 bool b[N];//是否为质数 int main(){ // freopen("num.txt","w",stdout); b[0]=b[1]=phi[1]=mu[1]=d[1]=mi[1]=sigma[1]=mp[1]=1; for(int i=2;i<=N-5;i++){ if(!b[i]){ p[++p[0]]=i;phi[i]=i-1;mu[i]=-1;d[i]=2; mi[i]=1;sigma[i]=1+i;mp[i]=1+i; … text/html 2020-08-04T12:10:12+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%BA%BF%E6%AE%B5%E6%A0%91&rev=1596514212&do=diff 格式：不要使用换行符，会引入一个空格。注意公式和两边的汉字之间空一格。 内容：挺好的。 线段树基础 简介 考虑这样一个问题：假设我们有一个长度为 $n$ 的整数数列，每次给出一个区间 $[L,R]$$L$$R$$[L,R]$$m$$O(nm)$$[L,R]$$O(\log n)$$O(\log n)$$n$$\{a_n\}$$a_x$$y$$a_x$$y$$\sum_{i=l}^ra_i$$1\le n,q\le 10^5$$n$$\{a_n\}$$a_x(l\le x \le r)$$y$$\sum_{i=l}^ra_i$$1\le n,q\le 10^5$$n$$\{a_n\}$$a_x(l\le x \le r)$$y$$a_x(l\le x \le r)$$y$$a_x(l\le x \le r)$$y$$\sum_{i=l}^ra_i$$1\le n,q\le 10^5$… text/html 2021-10-11T17:09:09+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E7%BB%84%E9%98%9F%E8%AE%AD%E7%BB%83%E6%AF%94%E8%B5%9B%E8%AE%B0%E5%BD%95&rev=1633943349&do=diff back 比赛时间 比赛名称 赛中过题 总计过题 总题目数 排名 2020.05.09 2020, XIII Samara Regional Intercollegiate Programming Contest 11 12 13 N/A 2021.07.10 2020 CCPC Wannafly Winter Camp Day7 8 11 12 2/169 2021.07.17 2021牛客暑期多校训练营1 6 10 11 84/1378 2021.07.19 2021牛客暑期多校训练营2 5 10 text/html 2020-07-03T22:38:53+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E8%8E%AB%E6%AF%94%E4%B9%8C%E6%96%AF%E5%8F%8D%E6%BC%94_lgwza&rev=1593787133&do=diff 莫比乌斯反演 简介 莫比乌斯反演是数论中的重要内容. 对于一些函数 $f(n)$, 如果很难直接求出它的值, 而容易求出其倍数和或约数和 $g(n)$, 那么可以通过莫比乌斯反演简化运算, 求得 $f(n)$ 的值 开始学习莫比乌斯反演前, 我们需要一些前置知识: 积性函数、Dirichlet 卷积、莫比乌斯函数.$$ \forall a,b,c\in Z,\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor $$$$ \forall n\in N,\left|\left\{\left\lfloor\frac{n}{d}\right\rfloor|d\in N\right\}\right|\le\left\lfloor2\sqrt{n}\right\rfloor $$$|V|$$V$$\left\lfloor\frac{n}{i}\right\rfloor$$n$$i$$i\le n$$j$$i\le j\le n$… text/html 2020-07-17T10:01:26+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95&rev=1594951286&do=diff 计算几何 1.基础知识 向量的点积叉积。在涉及二维平面的题目上，叉积的方向只有z轴向上以及向下。故可以省略地用有符号数字来表示。 模板 #define eps 1e-8 #define MAXN 1e9 #define defAng auto si=sin(angle);\ auto co=cos(angle); class vec { public: vec(double xx=0,double yy=0):x(xx),y(yy) { } double x,y; double len() { return sqrt(x*x+y*y); } bool operator ==(const vec &a) { return a.x==x&&a.y==y; } vec unit()//单位向量 { auto l=len(); return vec(x/l,y/l); } vec normal()/… text/html 2021-07-07T21:51:18+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:%E9%98%9F%E4%BC%8D%E6%8A%80%E8%83%BD%E6%A0%91&rev=1625665878&do=diff back 0-不会；1-只会模板题；2-会写题 算法基础 姜一凡 蒋贤蒙 王赵安 算法基础 2 2 枚举 2 2 模拟 2 text/html 2021-07-11T19:37:28+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:2020%E5%B9%B4%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95&rev=1626003448&do=diff 周报 周报模板 2020/05/02--2020/05/08 周报 2020/05/09--2020/05/15 周报 2020/05/16--2020/05/22 周报 2020/05/23--2020/05/29 周报 2020/05/30--2020/06/05 周报 2020/06/06--2020/06/12 周报 2020/06/13--2020/06/19 周报 2020/06/20--2020/06/26 周报 2020/06/27--2020/07/03 周报 2020/07/04--2020/07/10 周报 2020/07/11--2020/07/17 周报 2020/07/18--2020/07/24 周报 2020/07/25--2020/07/31 周报 2020/08/01--2020/08/07 周报 2020/08/08--2020/08/14 周报 2020/08/15--2020/08/21 周报 2020/08/22--2020/08/28 周报 2020/08/29--2020/09/04 周报 2020… text/html 2021-10-09T22:05:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:2021%E5%B9%B4%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95&rev=1633788300&do=diff 周报 周报模板 2021/01/14--2021/01/20 周报 2021/01/21--2021/01/27 周报 2021/01/28--2021/02/03 周报 2021/02/04--2021/02/10 周报 2021/02/11--2021/02/17 周报 2021/02/18--2021/02/24 周报 2021/02/25--2021/03/03 周报 2021/03/04--2021/03/10 周报 2021/03/11--2021/03/17 周报 2021/03/18--2021/03/31 半月报 2021/04/01--2021/04/30 月报 2021/05/01--2021/05/31 月报 2021/06/01--2021/06/30 月报 2021/07/01--2021/07/31 月报 2021/08/01--2021/08/15 半月报 2021/08/16--2021/08/31 半月报 2021/09/01--2021/09/30 月报 2021/10/01--2021/10/31 月报… text/html 2020-07-31T10:19:55+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:ac_%E8%87%AA%E5%8A%A8%E6%9C%BA_lgwza&rev=1596161995&do=diff AC 自动机 概述 AC 自动机是以 Trie 的结构为基础，结合KMP 的思想建立的。 简单来说，建立一个 AC 自动机有两个步骤： * 基础的 Trie 结构：将所有的模式串构成一棵 Trie。 * KMP 的思想：对 Trie 树上所有的结点构造失配指针。$s_1,s_2,\cdots,s_n$$Q$$u$$v$$v\in Q$$v$$u$$u$$u$$p$$p$$u$$trie[p,c]=u$$u$$trie[fail[p],c]$$u$$trie[fail[p],c]$$p$$fail[p]$$u$$fail[u]$$trie[fail[p],c]$$trie[fail[fail[p]],c]$$fail[u]$$u$$fail[5]=10$$fail[10]=0$$fail[6]=7$$trie[u,c]$$u$$trans(u,c)$$u$$fail[u]$$u$$trans[u][i]$$trans[u][i]$$trans[fail[u]][i]$$trans[u][i]$$trans[fail[u]][i]$$S$$trans[S][c]$$S$$S… text/html 2020-07-26T20:21:43+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:bsgs&rev=1595766103&do=diff BSGS算法 用于求解 $A^x=B(mod C)$ 这样的方程 当A与C互质时，令 $x=im+j$ , 原式可化为 $A^j=B\cdot A^{-mi}(mod C)$ ，然后循环遍历j，并把 $(A^{j}\%C,j)$ 加入哈希表中，然后枚举左边 $B\cdot A^{-mi}\%C$，从哈希表中查找，若存在，则得到一组解 代码 #define MOD 76543 int hs[MOD],head[MOD],next[MOD],id[MOD],top; void insert(int x, int y) { int k = x%MOD; hs[top] = x, id[top] = y, next[top] = head[k], head[k] = top++; } int find(int x) { int k = x%MOD; for(int i = head[k]; i != -1; i = next[i]) if(hs[i] == x) return id[i]; return … text/html 2020-05-07T17:26:54+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:cf639_div1_a_b&rev=1588843614&do=diff Q:为什么只有A、B的题解呢 A:当然因为我太菜了，2个小时就做出来两道题 再给我两个小时估计也只能做出来这两道题 A. Hilbert’s Hotel 通过简单的证明，我们可知，只需验证$\{x|x=(a_i+i)mod\; n\}(0\le i< n)$是否就是集合$\{0,1,\ldots,n-1\}$即可 text/html 2020-05-13T17:55:28+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:cf641&rev=1589363728&do=diff Codeforces Round #641 (Div. 2) A. Orac and Factors 大致题意:$f(n)$为n除1外的最小约数，令$g(n)=f(n)+n$，求$g_k(n)$ 易证，$f(n)$与$n$同奇偶，所以$f(n)+n$必为偶数。又$f(2k)=2,k\in N$，所以我们只需先计算$f(n)+n$，然后加$k-1$个2即可。 代码： #include <stdio.h> int main() { int t; scanf("%d",&t); for (int kkk=1;kkk<=t;kkk++) { int n,k; scanf("%d%d",&n,&k); if (n%2==0) printf("%d\n",n+k*2); else { int i; for (i=2;i<=n;i++) if (n%i==0) bre… text/html 2020-05-21T15:24:05+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:cf643&rev=1590045845&do=diff Codeforces Round #643 (Div. 2) A. Sequence with Digits 大致题意：$a_{n+1}=a_n+\min \{D_{a_n}\}+max\{D_{a_n}\}$，$D_n$是n的各位数字组成的集合。求$a_n$。 盲猜多求几个就会带有数字0 代码: #include <stdio.h> #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int T; scanf("%d",&T); auto f=[](long long now){ vector<long long> vec; while (now!=0) { vec.push_back(now%10); now/=10; } return vec; }; auto minn=[&](long long now) … text/html 2020-05-27T01:01:44+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:cf_643_div._2&rev=1590512504&do=diff 比赛链接 text/html 2020-05-27T01:01:56+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:cf_644_div._3&rev=1590512516&do=diff 比赛链接 text/html 2020-06-25T10:24:50+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:cf_652_div._2&rev=1593051890&do=diff 比赛链接 text/html 2020-06-26T12:46:47+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:cf_edu_90&rev=1593146807&do=diff 比赛链接 text/html 2020-05-07T11:10:31+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:code&rev=1588821031&do=diff back #include<bits/stdc++.h> using namespace std; const int N=500005; typedef long long ll; ll tr[N*4],a[N]; inline int ls(int o){ return o<<1; } inline int rs(int o){ return o<<1|1; } void push_up(int o){ tr[o]=tr[ls(o)]+tr[rs(o)]; } void build(int o,int l,int r){ if(l==r){ tr[o]=a[l]; return; } int mid=l+r>>1; build(ls(o),l,mid); build(rs(o),mid+1,r); push_up(o); } void xg(int o,int pos,int l,int r,ll k,int op){ if(l==r){ if(op==1) tr[o]+=k; else tr[o]=k; return; } int… text/html 2020-05-07T11:12:13+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:code1&rev=1588821133&do=diff back #include<bits/stdc++.h> using namespace std; const int N=500005; typedef long long ll; ll tr[N*4],a[N]; inline int ls(int o){ return o<<1; } inline int rs(int o){ return o<<1|1; } void push_up(int o){ tr[o]=tr[ls(o)]+tr[rs(o)]; } void build(int o,int l,int r){ if(l==r){ tr[o]=a[l]; return; } int mid=l+r>>1; build(ls(o),l,mid); build(rs(o),mid+1,r); push_up(o); } void xg(int o,int pos,int l,int r,ll k,int op){ if(l==r){ if(op==1) tr[o]+=k; else tr[o]=k; return; } int… text/html 2020-05-07T11:12:49+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:code2&rev=1588821169&do=diff back #include<bits/stdc++.h> using namespace std; const int N=100005; typedef long long ll; ll tr[N*4],tag[N*4],a[N]; inline int ls(int o){ return o<<1; } inline int rs(int o){ return o<<1|1; } void push_up(int o){ tr[o]=tr[ls(o)]+tr[rs(o)]; } void build(int o,int l,int r){ if(l==r){ tr[o]=a[l]; return; } int mid=l+r>>1; build(ls(o),l,mid); build(rs(o),mid+1,r); push_up(o); } void f(int o,int l,int r,ll k){ tag[o]+=k; tr[o]+=(r-l+1)*k; } void push_down(int o,int l,int r){ int … text/html 2020-05-07T11:13:35+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:code3&rev=1588821215&do=diff back #include<bits/stdc++.h> using namespace std; const int N=100005; typedef long long ll; int n,m,p; ll tr[N*4],mul[N*4],add[N*4],asi[N*4],a[N]; inline int ls(int o){ return o<<1; } inline int rs(int o){ return o<<1|1; } void push_up(int o){ tr[o]=tr[ls(o)]+tr[rs(o)]; } void build(int o,int l,int r){ mul[o]=1; asi[o]=-1; if(l==r){ tr[o]=a[l]; return; } int mid=l+r>>1; build(ls(o),l,mid); build(rs(o),mid+1,r); push_up(o); } void f(int o,int l,int r,ll k){ tr[o]=(tr[o]+(r-l+1)… text/html 2020-07-23T10:30:22+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:codeforces_round&rev=1595471422&do=diff 比赛链接 text/html 2020-07-07T11:07:50+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:contest4&rev=1594091270&do=diff 比赛链接 题解 A. Island Travels 题解 $\text{bfs}$ 求一下连通块，再 $\text{bfs}$ 求一下最短路，最后一个状压 $\text{dp}$ 就好了。 比赛的时候把最后的 $\text{dp}$ 当成 $\text{TSP}$ 问题了，但其实可以走重复的路，不然会漏解。 于是补了个 $\text{Floyd}$ 算法，就 $\text{AC}$$+$$\text{depth}$$+$$\text{Trie}$$\text{Trie}$$26$ text/html 2020-06-19T21:04:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:dft&rev=1592571840&do=diff DFT 作用：把一个多项式 $f(x)$ 转化成点值表示 $\{(x_0,f(x_0)),(x_1,f(x_1)),\ldots,(x_n,f(x_n))\}$ 的形式。 推导过程： 记 $\omega_k^n=e^{\frac{2k\pi}{n}}$ 若 $f(x)=\sum_{i=0}^{n-1}a_ix^i$ 将 $f(x)$ 按奇偶次拆开 $f(x)=(a_0+a_2x^2+\ldots+a_{n-2}x^{n-2})+x(a_1+a_3x^2+\ldots+a_{n-1}x^{n-2})=f_1(x^2)+xf_2(x^2)$ 其中 $f_1(x)=a_0+a_2x+a_4x^4+\ldots+a_{n-2}x^{\frac{n}{2}-1},f2(x)=a_1+a_3x+\ldots+a_{n-1}x^{\frac{n}{2}-1}$ 代入 ${\omega}_k^n$ ，得 $f({\omega}_n^k)=f_1({\omega}_n^{2k})+{\omega}_n^kf_2({\omega}_n^{2k})=f_1({\omega}_{\frac{n}… text/html 2020-06-02T20:58:57+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:dp%E7%9A%84%E4%BC%98%E5%8C%96&rev=1591102737&do=diff 格式：max 使用 \max，sum 使用 \text{sum}，代码使用 <hidden></hidden> 隐藏，均已修改。学会使用 \begin{cases}\end{cases} 来表示不同的 case，不需要自己设计格式。 内容：内容过于简单！可尝试从读者的角度想想能否看懂。$(1\le j <i)$$l_{i}\le j\le r_{i}$$l_{i}$$r_{i}$$i$$dp[i]=\max\{dp[j]\}+C[i](1\le j <i)$$dp[i]$$$ dp[i]= \begin{cases} &\text{sum}[i]&i\le k\\ &\max\{dp[j-1]+\text{sum}[i]-\text{sum}[j]\}&i-k \le j\le i,i>k \end{cases} $$$\text{ans}=\max\{dp[i]\}$$O(nk)$$\text{sum}[i]$$dp[i]=\max\{dp[j]\}+\text{sum}[i]$$dp[i]$$O(n)$… text/html 2021-07-10T17:06:58+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:front_page&rev=1625908018&do=diff 2020年度训练计划及训练记录 2021年度训练计划及训练记录 队伍技能树 组队训练比赛记录 团队会议记录 lgwza jxm2001 王智彪 qgjyf2001(已退役) test text/html 2021-10-09T19:13:28+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001&rev=1633778008&do=diff back 知识点 图论 centroid_decomposition 静态点分治 重链剖分 LCT 长链剖分 点分树 图论 1(最短路与连通分量) 图论 2(网络流) 图论 3(网络流例题) 矩阵树定理 树上启发式合并 树同构 Prufer 序列 重构树 最小斯坦纳树 数据结构优化建图 三元环计数 基环树 支配树 圆方树 ETT LGV引理 同余最短路 数据结构 可持久化数据结构 1 可持久化数据结构 2 可持久化数据结构 3 替罪羊树 KD Tree 笛卡尔树 线段树合并/分裂 fhq treap 左偏树/可并堆 树套树 拓展域并查集 线段树分治 吉司机线段树 数据结构练习 1 李超线段树 猫树 数学 线性基 数论 1 数论 2 数论 3 数论 4 数论 5 多项式 1 多项式 2 多项式 3 多项式 4 生成函数 1 生成函数 2 二项式反演 斯特林数 多项式应用 万能欧几里得算法 基于值域预处理的快速 GCD 动态规划 数位DP 二进制/单调队列/斜率优化… text/html 2020-06-06T20:41:33+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:lgwza--contest1&rev=1591447293&do=diff 比赛链接 text/html 2020-06-06T20:42:06+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:lgwza--contest2&rev=1591447326&do=diff 比赛链接 text/html 2021-09-17T11:06:59+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:lgwza&rev=1631848019&do=diff back 学习笔记 数学 数论概论学习小结 欧拉函数 莫比乌斯反演 线性筛模板 二次剩余模板 杜教筛 拉格朗日插值 博弈论 二次剩余 扩展中国剩余定理 扩展 BSGS 生成函数理论 1——基本定义 生成函数理论 2——基本例子 快速傅里叶变换(FFT) 快速数论变换(NTT) 生成函数理论 3——普通生成函数 生成函数理论 4——指数型生成函数 生成函数理论 5——一些例子 Stirling 数——理论 动态规划 状压 DP 数位 DP 可逆背包 字符串 字符串基础 字符串匹配 字符串哈希 字典树(Trie) 后缀数组 AC 自动机 Manacher 算法 回文树 序列自动机 图论 图匹配 增广路定理 Dinic 算法 类 Dinic 算法 最小割 一般图最大匹配 SPFA+Dijkstra 最短路模板 强连通分量——Tarjan 算法模板 2-SAT 拆点 虚树 割点和桥 数据结构 线段树基础 树链剖分 Splay 可持久化数组 主席树 扫描线问题 其他 普通莫队算法 … text/html 2020-07-31T10:57:10+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:polya%E5%AE%9A%E7%90%86&rev=1596164230&do=diff polya定理 概念 设 $G=\{P_1,P_2,\ldots,P_g\}$ 是n个对象的一个置换群， $C(P_k)$ 是置换 $P_k$ 的循环个数。用 $m$ 种颜色对 $n$ 个对象着色，着色方案数为 $\frac{1}{|G|}(m^{C(P_1)}+m^{C(P_2)}+\ldots+m^{C(P_g)})$ 例题 洛谷p4980 首先由polya定理，首先存在 $n$ 个置换群，分别对应着旋转0个，旋转1个….旋转 $n-1$$k$$P_k$$C(P_k)=gcd(k,n)$$\frac{1}{n}\sum_{k=1}^{n}n^{\gcd(k,n)}$$gcd(k,n)$$\frac{1}{n}\sum_{d|n}n^d\phi(\frac{n}{d})$$O(Tn^{\frac{3}{4}})$… text/html 2020-08-07T14:26:41+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:qgjyf2001&rev=1596781601&do=diff back 我太菜了 专题 dp的优化 可持久化线段树 DFT 计算几何 BSGS Polya定理 半平面交 题解 Cf639 Div1 A、B Cf641 Cf643 text/html 2021-08-28T17:05:59+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:test&rev=1630141559&do=diff back test_2 这里有一个公式：$\sqrt\frac{2}{3}\lim_{x\to \infty}{\frac{x}{e^x}=0}$ 这里有一段代码 #include <con> #include <iostream> #include <set> int main() { std::set<int> s; for (int i=1;i<=1000;i++) s.insert(i*i%1234); for (auto i:s) std::cout<<i<<std::endl; return 0; } $O(n^2)$$O(1)$$O(nlogn)$$O(1)$ text/html 2020-05-06T14:41:35+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:wza&rev=1588747295&do=diff $a+b=1$