https://wiki.cvbbacm.com/ 2026-04-30T02:17:58+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2021-04-01T21:33:05+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:big_fac_mod_prime&rev=1617283985&do=diff 大阶乘模质数学习笔记 以下参考了这篇博客。 求 $n!\mod{p}(n<p)$，其中 $p$ 为质数，可以在 $\mathcal{O}(\sqrt{n}\log n)$ 的复杂度下完成。 考虑根号分块。定义 $f_{u}(x)=\prod_{i=1}^{u}(x+i)$。设 $v=\lfloor\sqrt{n}\rfloor$，那么显然答案为 $\prod_{i=0}^{v-1}f_{v}(iv)\prod_{i=v^{2}+1}^{n}i$。 已有的办法是先分治求出 $f_{v}(x)$，然后多点求值，这样的复杂度是 $\mathcal{O}(\sqrt{n}\log^{2}n)$$f_{v}(0),f_{v}(v),\cdots,f_{v}(v^{2})$$f_{1}(0),f_{1}(v)$$f_{v}$$f_{d}(0),f_{d}(v),\cdots,f_{d}(dv)$$f_{2d}(x)=f_{d}(x)f_{d}(x+d)$$f_{d}((d+1)v),\cdots,f_{d}(2dv)$$f_{d}(d),f_{d}(d+v),\cdots,f_{d}(d+… text/html 2021-04-01T21:34:19+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:big_fac_mod_prime_pow&rev=1617284059&do=diff 大阶乘模质数的幂学习笔记 以下参考了这篇博客。 求 $n!\mod{p^{e}}$（包括 $p$ 的幂次和互质部分的模），其中 $p$ 为质数，可以在 $\mathcal{O}(pe+e\log_{p}n)$ 下完成（不考虑大整数部分的复杂度）。 定义 $f(m)=\prod_{i=1,\text{gcd}(i,m)=1}i$。那么有 $n!=f(n)\cdot p^{\lfloor\frac{n}{p}\rfloor}\cdot\lfloor\frac{n}{p}\rfloor!$，也就是说我们可以通过 $\log_{p}n$$f$$n=up+v(0\le v<p)$$f(n)$$$ \begin{aligned} f(n)&=\left(\prod_{i=0}^{u-1}\prod_{j=1}^{p-1}(ip+j)\right)\cdot\prod_{j=1}^{v}(up+j)\\ \end{aligned} $$$$ \begin{aligned} \prod_{i=1}^{x}(t+i)&=\sum_{i=0}^{x+1}\frac{\begin{bmatrix}x+… text/html 2022-03-04T21:45:49+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:bipartite_matching_weighted&rev=1646401549&do=diff 这个算法大家都写了很多，这里只想证明 KM 算法有局部最优性。即第 $i$ 轮求出的匹配是 $\text{size}=i$ 的最大权匹配。 对通常流传的 KM 算法需要做一定修改，即将所有 $U$ 部全体未盖点均作为 $S$ 点。设一轮结束后，$U$$U_{1}$$U_{2}$$V$$V_{1}$$V_{2}$$U_{2}\subset S$$V_{2}\subset T'$$T$$0$$U_{1}$$V_{1}$$\text{size}=i$$$ \le\sum_{j\in U_{1}}y_{j}+\sum_{j\in V_{1}}y_{j}=\text{current answer} $$ text/html 2020-05-25T12:14:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:bm&rev=1590380040&do=diff Berlekamp-Massey 算法 算法介绍 设域 $F$ 上有一无限数列 $s_{0},s_{1},\cdots$，我们想要对某个有限的 $n$，找到一个尽可能短的数列 $c_{1},\cdots,c_{L}$，使得 $s_{j}=-\sum_{i=1}^{L}c_{i}s_{j-i}$ 对 $j=L,L+1,\cdots,n-1$ 成立。特别地，若 $L=0$，意味着 $s_{0}=s_{1}=\cdots=s_{n-1}=0$。记 $s_{0},\cdots,s_{n-1}$ 为 $s^{(n)}$，这样的数列 $c$ 称为 $s^{(n)}$ 的递推式。由定义可以看出，任意 $L\ge n$$c$$s^{(n)}$$L$$c$$s^{(n)}$$s^{(n+1)}$$L'$$c'$$s^{(n+1)}$$L'\ge n+1-L$$L'\le n-L$$$ \begin{aligned} s_{n}&=-\sum_{i=1}^{L'}c'_{i}s_{n-i}\\ &=-\sum_{i=1}^{L'}c'_{i}\left(-\sum_{j=1}^{L}c_{j}s_{n… text/html 2020-10-09T01:00:24+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:codeforces_global_round_10&rev=1602176424&do=diff A. Omkar and Password 签到题。 B. Omkar and Infinity Clock 签到题。 C. Omkar and Waterslide 签到题。 D. Omkar and Bed Wars 不 WA 就是签到题。 E. Omkar and Duck 题目大意：给一个 $n\times n$ 的网格，要求你给每个点一个权，使得从左上角仅往右往下的所有 ${2n-2\choose n-1}$$\le10^{15}$$x+y=k$$(x,y)$${x+y\choose x}$$0$$(x,y)$$(x-1,y)$$(x,y-1)$$(x-1,y)$$(x,y-1)$$(x-1,y)$$(x,y-1)$$(x,y)$$(x,y)$$n$$h$$h_{i}\le h_{i+1}-2$$h_{i}$$h_{i+1}$$h_{i}\le h_{i+1}-2$$h_{1},h_{2}-h_{1},\cdots,h_{n}-h_{n-1}$$+1,-2,+1$$\alpha$$\alpha$$\alpha$$1$$n$$i$$h_{i}>=h_{i-1}… text/html 2021-03-14T20:21:23+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:codeforces_global_round_12&rev=1615724483&do=diff H. Multithreading 题目大意：一个圆上有 $2n$ 颗珠子，每颗珠子为黑色或白色，且每种颜色的数量均为偶数。将所有同色的珠子两两匹配，所得的线段会产生一些交点，仅考虑其中白线和黑线相交的交点。定义 $f$$2n$$s$$f$$s$$m$$f$$\frac{1}{4}$$b_{e},b_{o}$$f=\frac{1}{2}|b_{e}-b_{o}|$$p_{e},p_{o}$$p=p_{e}+p_{o}$$$ \begin{aligned} &\frac{1}{2^{p}}\sum_{i=-\infty}^{+\infty}[i+b_{e}-b_{o}\equiv 0\pmod 2]|i+b_{e}-b_{o}|\sum_{t=-\infty}^{+\infty}{p_{e}\choose t}{p_{o}\choose t-i}\\ =&\frac{1}{2^{p}}\sum_{i=-\infty}^{+\infty}[i+b_{e}-b_{o}\equiv 0\pmod 2]|i+b_{e}-b_{o}|{p\choose p_{o}+i}\\ =&\frac{1}… text/html 2020-05-17T21:38:54+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_432_div._1&rev=1589722734&do=diff Contest Info practice link Solutions F. Rainbow Balls 题目大意：一个袋子里有一些球，有 $n$ 种颜色，第 $i$ 种有 $a_{i}$ 个。每回合从中依次摸出两个球，然后将第二个球的颜色变为第一个球的颜色，然后再放回。直到所有球的颜色相同为止。求回合数的期望。$S$$E_{x}$$x$$0$$1$$S$$p_{x}$$$ \begin{aligned} p_{0}&=0\\ p_{S}&=1\\ p_{x}&=\frac{1}{2}(p_{x+1}+p_{x-1}) \end{aligned} $$$p_{x}=xp_{1}$$p_{1}=\frac{1}{S}$$x$$$ \begin{aligned} E_{x}&=\frac{x(S-x)}{S(S-1)}(E_{x+1}+E_{x-1})+(1-2\frac{x(S-x)}{S(S-1)})E_{x}+\frac{x}{S}\\ 2E_{x}&=E_{x+1}+E_{x-1}+\frac{(S-1)}{(S-x)}\\ E_{x+1}-E_{x}&=E_{x}-E_… text/html 2020-05-09T11:55:15+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_635_div._1&rev=1588996515&do=diff Contest Info practice link Solutions A B E. Chiori and Doll Picking 题目大意：给你 $n$ 个 $m$ 位整数，对于 $\forall i,0\le i\le m$，统计 $2^{n}$ 个子集的异或和中 bitcnt 为 $i$ 的数量。 题解：考虑这 $n$ 个整数的一组基 $A$。定义 $S(A)$ 表示 $A$ 的所有子集异或和组成的集合。$\forall s\in S(A)$$A$$A$$s$$A$$2^{n-|A|}$$|A|=k$$k\le\frac{m}{2}$$2^{k}$$A$$\mathcal{O}(k^{2}2^{m-k})$$A$$A$$2^{m}$$A_{i}=1\text{ iff }i\in S(A)$$\forall i,0\le i\le m$$P_{i}$$2^{m}$$P_{ij}=1\text{ iff }\text{bitcnt}(j)=i$$\text{ans}_{i}$$A$$P_{i}$$0$$f$$f(A)$$f(P_{i})$$2^{m}$$f(A)$… text/html 2020-05-09T11:56:15+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_639_div._1&rev=1588996575&do=diff Contest Info practice link Solutions A. Hilbert’s Hotel 签到题。 B. Monopole Magnets 签到题。 C. Quantifier Question 题目大意：给定一个逻辑命题 $?x_{1}?x_{2}\cdots?x_{n}\bigwedge_{i=1}^{m}(x_{i_{1}}<x_{i_{2}})$，其中每个 $?$ 填上 $\forall$ 或 $\exists$，使得命题成立。求 $\forall$ 的最大数量。 题解：建图。如果有环显然无解。否则，对于一个 $i$$j<i$$j\to i$$i\to j$$i$$\exists$$j$$i$$\sum_{i=1}^{n}b_{i}(a_{i}-b^{2}_{i})$$b_{i}\in[0,a_{i}]\cup\mathbb{Z}$$\sum_{i=1}^{n}b_{i}=k$$b_{i}\ge0$$m$$1$$1$$t_{1},t_{2}$$[t_{1}+1,t_{2}]$$R,Y,B$$n$$m$$R,Y$$R=1,Y=2,B=3$$… text/html 2020-05-17T21:34:08+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_641_div._1&rev=1589722448&do=diff Contest Info practice link Solutions D. Slime and Biscuits 题目大意：有 $n$ 个口袋，每个口袋有 $a_{i}$ 个球。每次等概率随机一个球，将其等概率随机移动到另外 $n-1$ 个口袋中的一个。当所有球在同一个口袋时结束。问期望移动次数。$E_{i}=\sum_{j=0}^{+\infty}jP_{ij}$$P_{ij}$$j$$i$$E_{i}$$1$$\sum_{i=1}^{n}E_{i}$$E'_{i}$$i$$P_{i}=\sum_{j=0}^{+\infty}P_{ij}$$\sum_{i=1}^{n}P_{i}=1$$E_{i}=E'_{i}-\sum_{j=1,j\neq i}^{n}(P_{j}E+E_{i})$$E$$i$$j(i\neq j)$$i,j$$n$$n\cdot\text{ans}=\sum_{i=1}^{n}E'_{i}-(n-1)E$$E$$E'_{i}$$\mathcal{O}(\left(\sum_{i=1}^{n}a_{i}\right)\log\sum_{i=1}^{n}… text/html 2020-07-24T15:13:32+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_658_div._1&rev=1595574812&do=diff A. Prefix Flip 题目大意：给你两个 01 串 $a,b$，每次操作可以将 $a$ 的一个前缀 flip 并 reverse。要求在 $2n$ 次内将 $a$ 变成 $b$。 题解：注意到该操作的逆操作为自己。于是我们可以将 $a,b$ 变为全 0/全 1。每次找到第一个 $a[i]\neq a[i+1]$$i$$2n$$n$$p[i]$$p[i]$$n$$a$$b$$a,b$$x$$y$$[1,n+1]$$x$$n-y$$n+1$$L$$<L$$<L$$<L$$\ge L$$<L$$<L$$L$$\ge L$$\ge L$$\ge L$ text/html 2021-03-29T13:12:44+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_698_div._1&rev=1616994764&do=diff A. Nezzar and Board 题目大意：给你 $n$ 个整数，每次操作可以选取两个整数 $x,y$，将 $2x-y$ 加到集合中。问能否凑出 $k$。 题解：注意到可以将所有数加上一个常数，结果不变。不妨将所有数减去 $x_{1}$。现在显然能构造出所有数的倍数。如果 $k-x_{1}$$\gcd$$u,v$$\gcd$$ux+vy=\gcd$$x,y$$ux'+vy'=0$$(x',y')=1$$x',y'$$(x',y')$$(x,y)$$2x-y$$s,t$$m$$[l_{i},r_{i}]$$s[l_{i},r_{i}]$$s$$t$$t$$n$$\angle A_{i}A_{i+1}A_{i+2}$$m$$(l_{i},r_{i})$$1\sim n$$p_{l_{i}},p_{r_{i}}$$q_{l_{i}},q_{r_{i}}$$(p_{l_{i}}-p_{r_{i}})(q_{l_{i}}-q_{r_{i}})>0$$p,q$$1$$1,2,\ldots,n$$n,1,2,\ldots,n-1$$a_{1},\ldots,a_{n}$$b_{1},\ld… text/html 2021-03-26T11:41:45+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:conclusion&rev=1616730105&do=diff 部分链接尚未搬运~ 博弈论 威佐夫游戏 有两堆石子，两人轮流取，每次可以从一堆中取若干颗石子，也可以从两堆中取一样多的石子。负态为 $\{\lfloor k\cdot\frac{1+\sqrt{5}}{2}\rfloor, k+\lfloor k\cdot\frac{1+\sqrt{5}}{2}\rfloor\}(k = 0,1,2,\cdots)$ 翻硬币游戏 翻硬币游戏是指这样的一种组合游戏：有 $n$$sg$$sg$$sg(THHTTH)=sg(TH)\oplus sg(TTH)\oplus sg(TTTTTH)$$a\otimes b=\text{mex}\{a'\otimes b\oplus a\otimes b'\oplus a'\otimes b'|0\le a'<a,0\le b'<b\}$$sg$$0\otimes x=x\otimes0=0$$x\otimes y=0$$x=0\lor y=0$$1\otimes x=x\otimes1=x$$n$$[0,2^{2^{n}}-1]$$n$$2^{2^{n}}\otimes x=2^{2^{n}}\times… text/html 2021-03-15T13:52:12+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:dominator_tree&rev=1615787532&do=diff 支配树学习笔记 给一个有向图 $G=<V,E>$，给定一个起点 $s$，对于两点 $x,y$，若删去 $x$ 后，$s$ 不能到达 $y$，那么 $x$ 是 $y$ 的支配点。$s$ 和 $y$ 是两个平凡的支配点。 支配点之间形成了一棵树的关系，称为支配树。 定理 1$x,y$$z$$s\to x\to y\to z$$s\to y\to x\to z$$x$$y$$s\to y\to z$$s\to y$$x$$y\to z$$x$$x$$z$$z$$\Box$$u$$\text{idom}(u)$$s$$u$$\text{sdom}(u)=\min\{v|\exists v\to v_{1}\to\cdots\to v_{t}\to u,v_{1},\cdots,v_{t}>u\}$$v$$v$$u$$u,v$$u$$u$$u$$u$$v:=\text{sdom}(u)$$u$$fa_u<u$$v<u$$v$$u$$u$$v$$\Box$$\text{sdom}(u)\to u$$G'$$G'$$x$$y\Rightarrow G$$x$$y$$1\to\cdots\to … text/html 2021-07-10T00:20:13+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:finite_two_person_zero_sum_game&rev=1625847613&do=diff 有限二人零和博弈 设 $A\in\mathbb{R}^{n\times m}$，$X=\{1,2,\cdots,n\}$，$Y=\{1,2,\cdots,m\}$（即 $X$，$Y$ 均为有限集），$X$ 表示玩家 I 的（纯）策略集合，$Y$ 表示玩家 II 的（纯）策略集合。若玩家 I 选择纯策略 $i\in X$，玩家 II 选择纯策略 $j\in Y$，那么玩家 I 将获得 $A_{ij}$ 的收益，玩家 II 将获得 $-A_{ij}$$A$$X^{*}$$Y^{*}$$$ X^{*}=\{\boldsymbol{p}=(p_{1},p_{2},\cdots,p_{n})^{T}:p_{i}\ge0\land\sum_{i=1}^{n}p_{i}=1\}\\ Y^{*}=\{\boldsymbol{q}=(q_{1},q_{2},\cdots,q_{m})^{T}:q_{i}\ge0\land\sum_{i=1}^{m}q_{i}=1\} $$$p_{i}$$i$$\boldsymbol{p}$$\boldsymbol{p}^{T}A\boldsymbol{q}$$\bol… text/html 2022-05-09T22:09:57+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:front_page&rev=1652105397&do=diff 个人训练 2021.01.28 Codeforces Round 698 (Div. 1) pro:6/6 DONE 2020.12.06 Codeforces Global Round 12 pro:10/10 DONE 2020.09.30 Grakn Forces 2020 pro:9/9 DONE 2020.08.16 Codeforces Global Round 10 pro:9/9 DONE 2020.07.21 Codeforces Round 658 (Div. 1) pro:6/6 2020.05.12 Codeforces Round 641 (Div. 1) pro:4/7 2020.05.06 Codeforces Round 639 (Div. 1) pro:6/6 DONE 2020.04.15 Codeforces Round 635 (Div. 1) pro:6/7 2017.09.04 Codeforces Round 432 (Div. 1) pro:5/6 总结 开坑记录一些奇怪的结论 高合成数表 NTT 模数 BM算… text/html 2021-07-05T09:17:25+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:games&rev=1625447845&do=diff 例题 来源：Part I, 1.5.3–Ferguson 题目大意：有一堆 $31$ 颗的石子，每次可以取 $1\sim6$ 颗，但是每种数量至多取 $4$ 次。问胜负情况。 题解：不妨先不考虑 $4$ 个的限制。这个比较简单，模 $7$ 余 $0$ 的状态是负态。然而如果先手按这种策略操作，只要后手一直取 $4$$3$$5$$5$$2$$4$$5$$3$$2$$5$$5$$5$$7$$0$$1\times1$$n$$k\ge0$$2^{k+1}$$2^{k}$$\le2^{k}$$k=0$$1$$1$$\le k$$k+1$$x<2^{k+1}$$\text{lowbit}(x)$$\le\text{lowbit}(x)$$2^{k+1}$$2^{k+1}$$2$$\text{lowbit}$$\text{lowbit}$$a_{1}+\cdots+a_{n},a_{1}>\cdots>a_{n}$$n\ge2$$a_{n}$$a_{n-1}>2a_{n}$$a_{n-1}$$b_{1}+\cdots+b_{m}=a_{n-1}-x$$2x\ge b_{m}$$2x<b_{m}… text/html 2021-07-09T20:28:44+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:general_matching_weighted&rev=1625833724&do=diff 一般图最大权（最大）匹配 建议首先搞懂二分图最大匹配、二分图最大权（最大）匹配、一般图最大匹配这几个 special case。另外可以先阅读参考文献，其中 [1] 讲的是最好的。 问题描述 给定一个带权无向图 $<V,E>$$u$$y_u$$B$$z_{B}$$uv$$yz_{uv}=y_{u}+y_{v}+\sum_{u,v\in B}z_{B}-w_{uv}$$z$$z$$\delta$$z_{B}$$2\delta$$z_{B},yz_{uv}\ge0$$uv$$yz_{uv}=0$$B$$\frac{|B|-1}{2}$$z_{B}$$y_{u}$$\frac{\max w}{2}$$z_{B}$$0$$yz=0$$S$$\text{free}$$T$$T$$S$$z$$0$$\mathcal{O}(n)$$3$$1$$S/T$$S$$\delta$$T$$\delta$$S$$z$$2\delta$$T$$z$$2\delta$$S$$z\ge0$$\delta>0$$y$$\frac{1}{2}$$\delta$$\frac{1}{2}$$z_{B}\ge0$$z$… text/html 2020-10-03T12:28:54+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:grakn_forces_2020&rev=1601699334&do=diff A. Circle Coloring 签到题。 B. Arrays Sum 不 FST 就是签到题。 C. Discrete Acceleration 签到题。 D. Searchlights 签到题。 E. Avoid Rainbow Cycles 题目大意：给你 $m$ 个集合，每个集合有若干 $1\sim n$ 的元素，删除某个元素需要耗费一定的代价。删除后，对第 $i$$i$$i$$j$$f: \mathbb{N}\times\mathbb{N}\to\mathbb{N}$$n\le1.5\times10^{4}$$a_{i}=i$$q\le5\times10^{5}$$x,y$$a_{x}:=a_{y}:=f(x,y)$$f$$a$$2$$2$$2$$x$$x$$x$$\le x$$x$$x$$x$$n$$a_{1},a_{2},\cdots,a_{n}$$m$$\{(u_{i},v_{i},w_{i})\}$$a_{u_{i}}=a_{w_{i}}=0$$a_{v_{i}}>0$$u_{i}<v_{i}<w_{i}$$a_{v_{i}}$$u_{i},v_… text/html 2021-04-01T21:35:37+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:grid_gauss&rev=1617284137&do=diff 四（八）连通网格图上的高斯消元 假设我们在一个网格图上定义了一些转移，我们要对这个线性方程组做高斯消元。注意到这个矩阵非常稀疏，即每个方程至多只有 $5(9)$ 个变元。因此我们可以只维护非零的系数。我们证明，如果按照 $(0,0),\cdots,(0,m-1),\cdots,(n-1,0),\cdots,(n-1,m-1)$$\mathcal{O}(nm^{3})$$\mathcal{O}(m)$$(x,y)$$(x,y),(x,y+1),\cdots,(x,m-1),(x+1,0),(x+1,1),\cdots,(x+1,y)$$(x+1,y+1)$$\mathcal{O}(m)$$2m$$\mathcal{O}(nm^{3})$$\mathcal{O}(nm\min^{2}(n,m))$… text/html 2020-11-21T21:46:11+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:hcn&rev=1605966371&do=diff 高合成数 约数个数 高合成数 约数个数 $ 1 $ $ 1 $ $ 2 $ $ 2 $ $ 4 $ $ 3 $ $ 6 $ $ 4 $ $ 12 $ $ 6 $ $ 24 $ $ 8 $ $ 36 $ $ 9 $ $ 48 $ $ 10 $ $ 60 $ $ 12 $ $ 120 $ $ 16… text/html 2020-09-13T22:04:10+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:lyndon_factorization&rev=1600005850&do=diff Lyndon 分解学习 首先介绍 Lyndon 串。设有串 $w$，若对于所有 $w=uv,u,v\neq\varepsilon$，有 $w<vu$，称该串为 Lyndon 串。 性质 1 Lyndon 串不存在一个真子串，既是前缀又是后缀。 证明：设 $u$ 是这样的一个串，那么 $w=uv'$ 且 $w=v''u$。那么由定义我们有 $w<v'u$$w<uv''$$uv'<uv''$$v''u<v'u$$v'<v''$$v''<v'$$w$$v$$w<v$$v$$w<v$$w=uv$$uv<v$$uv<vu$$w$$uv<vu$$v$$w$$uv<v$$u,v$$uv$$u<v$$uv$$u<uv<v$$u<v$$s$$uv$$s=u'v$$s=v$$s=v'$$u',v'$$u,v$$u<u'$$u$$u'$$uv<u'v$$u$$v$$u<v$$uv<v$$u$$v$$v=uv''$$v''$$v$$v<v''$$uv<uv''=v$$uv<v$$uv<v<v'$$u,v$$u<v$$k_{1},k_{2}\ge1$$u^{k_{1}}v^{k_{2}}$$u^{k_{… text/html 2021-04-01T21:30:51+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:min_25&rev=1617283851&do=diff Min_25筛学习笔记 以下参考了这篇博客。 大概就是洲阁筛的好写版本。复杂度并没有降低。 设 $f(x)$ 是一个积性函数，且 $f(p)$ 是一个关于 $p$ 的多项式。要求 $\sum_{i=1}^{n}f(i)$。 定义 $g_{k}(x)=\sum_{i=1,i\text{ is prime}\lor\min_{i}> p_{k}}^{x}f(i)$。那么所有质数的 $f(p)$ 之和就是 $g_{m}(n)$，其中 $m$ 是不大于 $\sqrt{n}$$g_{0}(x)$$$ \begin{cases} &g_{k-1}(x)-f(p_{k})(g_{k-1}(\frac{x}{p_{k}})-g_{k-1}(p_{k}-1))&(x\ge p_{k}^{2})\\ &g_{k-1}(x)&(x<p_{k}^{2}) \end{cases} $$$\displaystyle{\mathcal{O}(\frac{n^{\frac{3}{4}}}{\log n}})$$h_{k}(x)=\sum_{i=2,\min_{i}>p_{k}}^{x}f(i)$$h_{0}(… text/html 2022-05-02T16:48:41+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:ntt&rev=1651481321&do=diff NTT 模数 表达式 原根 NTT 模数 表达式 原根 $12289$ $3\times2^{12}+1$ $11$ $13313$ $13\times2^{10}+1$ $3$ $15361$ $15\times2^{10}+1$ $7$ $18433$ $9\times2^{11}+1$ $5$ $19457$ $19\times2^{10}+1$ $3$ $25601$ $25\times2^{10}+1$ $3$ $37889$ $37\times2^{10}+1$ $3$ $39937$ $39\times2^{10}+1$ $5$ $40961$ $5\times2^{13}+1$ $3$ $50177$ $49\times2^{10}+1$$3$$58369$… text/html 2021-04-02T15:25:23+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:prime_pow_sqrt&rev=1617348323&do=diff 非质数二次剩余 解方程 $x^{2}\equiv a\pmod{p^{n}}$，这里先讨论 $p$ 是奇质数，且 $(a,p)=1$ 的情况。 若 $x^{2}\equiv a\pmod{p}$ 无解，那么显然原方程也无解。否则设 $r$ 是一个根，那么 $(r^{2}-a)^{n}\equiv0\pmod{p^{n}}$。又由于 $(r-\sqrt{a})^{n}=t-s\sqrt{a}$，$(r+\sqrt{a})^{n}=t+s\sqrt{a}$，因此 $t^{2}-s^{2}a\equiv0\pmod{p^{n}}$。同时可以证明，$t,s$ 总是 $2$ 的幂乘上 $r,a$ 的多项式，因此 $t,s$$p$$t^{2}\cdot s^{-2}$$\frac{(p-1)p^{n-1}}{2}$$(a,p)\neq1$$a$$p$$p=2$$x^{2}\equiv a\pmod{p^{1},p^{2},\ldots,p^{n}}$$p$$2$$O(2)$… text/html 2021-02-20T21:05:40+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:project_euler&rev=1613826340&do=diff 152. Writing 1/2 as a sum of inverse squares 题目大意：问有多少种方式将 $\frac{1}{2}$ 表示成 $2\sim80$ 之间的不同数的倒数平方和。 题解：感觉除了暴力没啥好的性质。首先将所有倒数平方乘上 $\text{lcm}(2^{2},\cdots,80^{2})$，就转成了一个 meet-in-middle 问题。但是将近 $80$$\text{lcm}$$0$$0$$2^{n}$$0$$30$$a^{2}-ab+b^{2}=c^{2}$$$ \begin{aligned} &|a-b\omega|^{2}\\ =&|a-\frac{b}{2}-\frac{b\sqrt{3}}{2}i|\\ =&a^{2}-ab+b^{2} \end{aligned} $$$\omega=\frac{1+\sqrt{3}i}{2}$$\omega^{3}+1=0$$$ \begin{aligned} &(a^{2}-ab+b^{2})^{2}\\ =&|a-b\omega|^{4}\\ =&|a^{2}-2ab\omega+b^{2}\o… text/html 2021-01-24T15:13:41+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:random_string&rev=1611472421&do=diff 随机串包含给定串的期望长度 设有一串 $S$，从一个空串开始，每次等概率随机往后面加一个字符，包含 $S$ 时停止，求串长度的期望。 设 $F(x)$ 表示恰在长度为 $x$ 停止的概率生成函数，$G(x)$ 表示长度为 $x$$$ \begin{aligned} 1+xG(x)&=F(x)+G(x)\\ G(x)\cdot\frac{x^{n}}{|\Sigma|^{n}}&=F(x)\sum_{i=1}^{|S|}[1..i\text{ is border}]\frac{x^{n-i}}{|\Sigma|^{n-i}} \end{aligned} $$$F'(1)$$1$$G(x)+xG'(x)=F'(x)+G'(x)$$F'(1)=G(1)$$2$$x=1$ text/html 2021-03-31T22:26:47+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:random_walk&rev=1617200807&do=diff 随机游走 有一类随机游走问题定义如下：在数轴中 $[0,n]$ 之间的整点上随机走动，走到 $0$ 或点 $n$ 时停止。否则，在点 $i$ 处，分别有 $f(i),g(i),h(i)$ 的概率向左走一步，不动，或者向右走一步，其中 $f(i)+g(i)+h(i)=1$。 首先可以计算出 $P(i)$$i$$n$$$ P(i)= \begin{cases} &0&(i=0)\\ &f(i)P(i-1)+g(i)P(i)+h(i)P(i+1)&(0<i<n)\\ &1&(i=n)\\ \end{cases} $$$$ \begin{aligned} (f(i)+h(i))P(i)=&f(i)P(i-1)+h(i)P(i+1)\\ f(i)(P(i)-P(i-1))=&h(i)(P(i+1)-P(i))\\ P(i+1)-P(i)=&\frac{f(i)}{h(i)}(P(i)-P(i-1))\\ \end{aligned} $$$$ P(i)=P(1)\cdot\sum_{j=0}^{i-1}\frac{\prod_{k=1}^{j}f(k)}{\prod_{k=1}^{j}h(k)… text/html 2020-05-25T12:13:08+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:rs&rev=1590379988&do=diff Reeds-Sloane 算法 算法介绍 Reeds-Sloane 算法是 BM 算法的拓展，可以处理模任意正整数的递推式。 设环 $\mathbb{Z}/m\mathbb{Z}$ 上有一数列 $s_{0},s_{1},\cdots,s_{n-1}$，我们想要找到一个尽可能短的数列 $a_{0}=1,a_{1},\cdots,a_{l}$，使得 $\sum_{i=0}^{l}a_{i}s_{j-i}=0$ 对 $j=l,l+1,\cdots,n-1$ 成立。 不妨用多项式的语言来简单地定义一下递推式的长度：设 $a(x)=\sum_{i=0}^{l}a_{i}x^{i}$$S(x)=\sum_{i=0}^{n-1}s_{i}x^{i}$$a(x)S(x)\equiv b(x)\pmod{x^{n}}$$A=(a(x),b(x))$$L(A)=\max\{\deg(a(x)),\deg(b(x))+1\}$$\deg(a(x))\le\deg(b(x))$$a$$0$$m=\prod p_{i}^{e_{i}}$$p_{i}^{e_{i}}$$m$$p^{e}$$\eta=0,1… text/html 2021-11-14T22:18:46+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:sequence_sum_v5&rev=1636899526&do=diff 序列求和V5学习及拓展 首先膜鎕~~ 问题很简单，求 $\sum_{i=1}^{n}i^{k}b^{i}$。原问题是对一个质数取模，这里我们拓展为对一个质数的幂 $p^{e}$ 取模。下面分为三类讨论： 若 $b\equiv0\pmod{p}$，那么我们至多只需要求前 $e$ 项即可。 若 $b\equiv1\pmod{p}$$b=up+1$$$ \begin{aligned} &\sum_{i=1}^{n}i^{k}(up+1)^{i}\\ =&\sum_{i=1}^{n}i^{k}\sum_{j=0}^{i}{i\choose j}(up)^{j}\\ =&\sum_{i=1}^{n}i^{k}\sum_{j=0}^{e-1}{i\choose j}(up)^{j}\\ =&\sum_{j=0}^{e-1}(up)^{j}\sum_{i=1}^{n}i^{k}{i\choose j} \end{aligned} $$${i\choose j}$$i$$j$$i$$k+e$$\mathcal{O}(k+e+\log_{p}x)$$f(n)$$f(n)=b^{n}F(n)-F(… text/html 2022-05-09T22:10:43+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:sequence_sum_v5_v2&rev=1652105443&do=diff 先看看 序列求和 V5。 先介绍一些前置知识。对于形式幂级数 $f(x)$ 可定义形式微分算子 $D$，即 $Df(x)=\sum_{i=1}^{+\infty}if_{i}x^{i-1}$。可对 $D$ 定义形式幂级数 $A(D)$，即 $A(D)f(x)=\sum_{i=0}^{+\infty}a_{i}D^{i}f(x)$。显然 $D$ 的形式幂级数满足加法的分配率，即 $A(D)f(x)+B(D)f(x)=(A(D)+B(D))f(x)$。它还满足乘法的结合率，即 $A(D)(B(D)f(x))=(A(D)B(D))f(x)$，这一点可以从定义中看出。根据以上性质，还可以定义微分算子形式幂级数的逆，即 $A(D)f(x)=g(x)\Leftrightarrow A^{-1}(D)(A(D)f(x))=f(x)=A^{-1}(D)g(x)$$f(x)$$f(x+1)=e^{D}f(x)$$F(x)$$k$$b^{n}F(n)-F(0)=\sum_{i=1}^{n}i^{k}b^{i}$$$ \begin{aligned} b^{n+1}F(n+1)-F(0)&=\sum_{i=… text/html 2021-04-01T23:08:28+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:set_counting&rev=1617289708&do=diff 设有两个集合 $A,B\subset\mathbb{N}$，且 $0\in A,1\in B,|A|=n,|B|=m$。定义 $A+B=\{x+y|x\in A,y\in B\}$，若 $A+B=[1,nm]\cap\mathbb{N}^{+}$，则称 $(A,B)$ 是好的。问这样的集合对有多少个。 解：若 $n=1$ 或 $m=1$，方案显然是唯一的。下面讨论 $n>1$ 且 $m>1$ 的情况： 若 $2\notin B$，那么必有 $1\in A$，否则 $2\notin A+B$，矛盾。这种情况下，我们把 $A$$1$$B$$1$$n,m$$1\in B,2\in B$$B$$A$$A$$A$$0$$A+B$$\{1,2,\cdots,nm\}\subset A+B$$\{1,2,\cdots,nm\}$$A+B$$x$$x-1$$A$$x-1\notin A$$t>1,t\in B$$x-t$$A$$x-t+1$$x-t$$(x-t)+(1)$$A$$B$$A$$t$$l$$\{x_{i}\},\{y_{i}\}$$t>1$$x_{i}>1(1\le i\le l)$$… text/html 2023-09-07T20:55:52+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:similar_euclid&rev=1694091352&do=diff 设 $f(a,b,c,n,t_{1},t_{2})=\sum_{i=0}^{n}i^{t_{1}}\lfloor\frac{ai+b}{c}\rfloor^{t_{2}}$，求解这一函数值的算法因类似于欧几里得算法而得名类欧几里得算法。为了方便，这里仅讨论 $6$ 个参数均为非负整数的情况。另外我们定义 $0^{0}=1$。现将该算法描述如下： 定义 $m=\lfloor\frac{an+b}{c}\rfloor$，$g_{t}(x)=(x+1)^{t}-x^{t}=\sum_{i=0}^{t-1}g_{ti}x^{i}$，$h_{t}(x)=\sum_{i=1}^{x}i^{t}=\sum_{i=0}^{t+1}h_{ti}x^{i}$。 首先描述几种特殊情况：$t_{2}=0$$$ \begin{aligned} 原式&=\sum_{i=0}^{n}i^{t_{1}}\\ &=h_{t_{1}}(n)+[t_{1}=0] \end{aligned} $$$m=0$$$ 原式=0 $$$a=0$$$ \begin{aligned} 原式&=\sum_{i=0}^{n}i^{t_{… text/html 2021-04-01T23:16:03+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:slopt_opt&rev=1617290163&do=diff 斜率优化模板详解 //优化形如dp[i]=max(b[j]*a[i]+c[j])的dp，不要求b[j]单调，min时取反即可 //动态维护一个下凸壳，复杂度O(nlogn) //适用于int，无精度误差 #include<bits/stdc++.h> typedef long long ll; const ll INF = LLONG_MAX; inline ll divide(ll a, ll b){return a / b - ((a ^ b) < 0 && a % b);}//严格向下取整，适用于负数 class L{ public: static bool isquery; //mutable的作用在于使multiset的const_iterator也能修改它所指向的元素，如果不加则不能修改 mutable ll k, b, p; //p是该条线段的右端点 L (ll k = 0, ll b = 0, ll p = 0):k(k), b(b), p(p){} bool operator < (const L… text/html 2021-09-16T21:11:29+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:some_antichain&rev=1631797889&do=diff 某个最大反链问题 给定一个非负整数数列 $\{t_{i}\}$，定义偏序集 $S=\prod_{i=1}^{n}\{x|0\le x\le t_{i},x\in\mathbb{Z}\}$，其中 $\vec{x}\preceq\vec{y}$ 当且仅当 $\forall 1\le i\le n,x_{i}\le y_{i}$。那么 $S$ 的最大反链的大小等于关于 $x_{i}$ 的不定方程 $\displaystyle{\sum_{i=1}^{n}x_{i}=\lfloor\frac{\sum_{i=1}^{n}t_{i}}{2}\rfloor}$ 满足 $\forall 1\le i\le n, 0\le x_{i}\le t_{i}$ 的整数解的个数。 证明：将该问题用整除来描述：设有整数 $n$$S$$x\preceq y$$x\mid y$$\deg x$$\deg n=m$$C=\{x|\deg x=\lfloor\frac{m}{2}\rfloor\}$$S$$|C|$$C$$d_{1},d_{2},\cdots,d_{h}$$\deg d_{1}+\deg d_{h}… text/html 2021-04-01T21:50:39+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:intrepidsword:zhongzihao:tournament_graph&rev=1617285039&do=diff 竞赛图的性质 竞赛图是指任意两点间恰有一条有向边的有向图。简记 $u\to v$ 表示 $u$ 到 $v$ 存在一条有向边。 性质 1 任意竞赛图都存在一条哈密顿通路。 证明：$n=1$ 时显然。$n\ge2$ 时，考虑归纳法，设 $n-1$ 时的哈密顿通路为 $p_{1},p_{2},\cdots,p_{n-1}$$n$$i$$p_{i}\to n$$n\to p_{i+1}$$n$$p_{i}$$n$$n$$p_{n-1}$$p_{n-1}\to n$$n\to p_{1}$$p_{2},\cdots,p_{n-1},n,p_{1}$$n\le3$$n\ge4$$n-1$$p_{1},p_{2},\cdots,p_{n-1}$$n$$i$$p_{i}\to n$$n\to p_{i+1}$$n$$p_{i}$$n$$n$$p_{n-1}\to n$$n\to p_{1}$$p_{2},\cdots,p_{n-1},n,p_{1}$$n(n\ge4)$$n-1$$p_{1},\cdots,p_{n}$$p_{i}\to p_{i+2}$$p_{i+1}$$p_{1}$$p_{…