WORIA

数学   大整数    加减乘除，取模，逻辑运算符，输入，输出，绝对值，幂   1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891 ...

E. 找出最少动作数   https://acm.ecnu.edu.cn/contest/636/problem/E/ 题意：一个堆栈中可以存 1 到 nnn 的整数，定义某时刻堆栈的状态为此时堆栈中数值 1 到 nnn 的个数 {cnt1,cnt2,⋯ ,cntn}\{cnt_1, cnt_2,\cdots, cnt_n\}{cnt1​,cnt2​,⋯,cntn​}。初始时堆栈为空，给定 mmm 个状态，要求仅使用 push，pop 操作，使堆栈依次遍历这 mmm 个状态，并最终变为空，求最少操作次数。 区间dp 考虑可以把一些永远用不到数压在栈底。从一个状态转移到另一个状态时，可以有 k1k_1k1​ 个数值1被压在栈底，k1k_1k1​ 为状态 LLL 到 RRR 中数值 1 的个数的最小值，这些 111 永远不会被用到，所以压在栈底是最优的。对于数值 2,⋯ ,n2,\cdots,n2,⋯,n 也类似。 记一个虚拟状态，其具有状态区间 LLL 到 RRR 中各数值的个数的最小值，记为 LRLRLR 的基础状态。记 LRLRLR 的基础状态下各数值的个数之和为 s[L][R]s[ ...

E. 找出最少动作数   https://acm.ecnu.edu.cn/contest/636/problem/E/ 题意：一个堆栈中可以存 1 到 nnn 的整数，定义某时刻堆栈的状态为此时堆栈中数值 1 到 nnn 的个数 {cnt1,cnt2,⋯ ,cntn}\{cnt_1, cnt_2,\cdots, cnt_n\}{cnt1​,cnt2​,⋯,cntn​}。初始时堆栈为空，给定 mmm 个状态，要求仅使用 push，pop 操作，使堆栈依次遍历这 mmm 个状态，并最终变为空，求最少操作次数。 区间dp 考虑可以把一些永远用不到数压在栈底。从一个状态转移到另一个状态时，可以有 k1k_1k1​ 个数值1被压在栈底，k1k_1k1​ 为状态 LLL 到 RRR 中数值 1 的个数的最小值，这些 111 永远不会被用到，所以压在栈底是最优的。对于数值 2,⋯ ,n2,\cdots,n2,⋯,n 也类似。 记一个虚拟状态，其具有状态区间 LLL 到 RRR 中各数值的个数的最小值，记为 LRLRLR 的基础状态。记 LRLRLR 的基础状态下各数值的个数之和为 s[L][R]s[ ...

表示 布洛赫球表面的任何一点表示一个量子比特的状态，换句话说，任何一个量子比特的状态 ∣ψ⟩\ket{\psi}∣ψ⟩ 都可以用三个参数 γ,θ,φ\gamma,\theta,\varphiγ,θ,φ 来表示： ∣ψ⟩=eiγ(cos⁡θ2∣0⟩+sin⁡θ2eiφ∣1⟩)\ket{\psi}=e^{i\gamma}(\cos\frac{\theta}{2}\ket{0}+\sin\frac{\theta}{2}e^{i\varphi}\ket{1}) ∣ψ⟩=eiγ(cos2θ​∣0⟩+sin2θ​eiφ∣1⟩) 其中全局相位因子 eiγe^{i\gamma}eiγ 在实验中是不可观测的。 运算 基础 转置：∣ψ⟩,⟨ψ∣\ket{\psi},\bra{\psi}∣ψ⟩,⟨ψ∣ 共轭转置。 内积：⟨ψ1∣ψ2⟩\braket{\psi_1|\psi_2}⟨ψ1​∣ψ2​⟩ 得到复数值。 ∥∣ψ⟩∥=⟨ψ∣ψ⟩\|\ket{\psi}\|=\sqrt{\braket{\psi|\psi}}∥∣ψ⟩∥=⟨ψ∣ψ⟩​，如果 ∣ψ⟩\ket{\psi}∣ψ⟩ 是一个量子态，那么一定有 ⟨ψ ...

矩阵 以下运算中矩阵的秩不变： 某列乘以非零标量 交换列次序 加入一列其他列的线性组合 转置（所以以上列可替换为行） 行列式： 方阵才有行列式，是各列的线性函数（见P10下） 不满秩等价于行列式为零 一列加上另一列行列式不变 转置行列式不变 交换列次序，行列式符号改变 奇异/非奇异矩阵一定是方阵。 方阵下有： 行列式非零   ⟺  \iff⟺ 满秩   ⟺  \iff⟺ 可逆   ⟺  \iff⟺ 非奇异 柯西-施瓦茨不等式：∣⟨x,y⟩∣≤∥x∥∥y∥|\braket{\boldsymbol{x},\boldsymbol{y}}|\le\|\boldsymbol{x}\|\|\boldsymbol{y}\|∣⟨x,y⟩∣≤∥x∥∥y∥，等号当且仅当 x,y\boldsymbol{x},\boldsymbol{y}x,y 共线时成立。 实数空间范数性质： 非负性：∥x∥≥0\|\boldsymbol{x}\|\ge 0∥x∥≥0，当且仅当 x=0\boldsymbol{x}=\boldsymbol0x=0 等号成立。 齐次性：∥rx∥=∣r∣∥x∥,r∈R ...

为什么要EM EM是极大似然估计的强化版，用于估计当模型中包含不可观测节点（即隐变量）时的似然函数，准确地说是估计似然函数的下界。 举例说明EM的必要性： 假设一个由 KKK 个正态分布组成的高斯混合模型（GMM），NNN 个样本，都不知道属于哪个正态分布，令变量 zzz 代表所属的正态分布，即 zzz 是隐变量。 则似然函数为 ∏i=1Np(xi)\prod_{i=1}^Np(x_i)∏i=1N​p(xi​)，一般转为对数似然，即 L=∑i=1Nlog⁡p(xi)L=\sum_{i=1}^N\log p(x_i)L=∑i=1N​logp(xi​)，由于隐变量 zzz 无法被观测，因此不能将 p(x)p(x)p(x) 写成某个正态分布形式，只能展开为 L=∑i=1Nlog⁡∑k=1Kπzkp(xi∣zk)L=\sum_{i=1}^N\log \sum_{k=1}^K\pi_{z_k}p(x_i|z_k)L=∑i=1N​log∑k=1K​πzk​​p(xi​∣zk​)，在极大似然估计中，令似然函数对各参数求导等于零，联立方程组，解得各参数。假设我们对 p(xi∣z1)p(x_i|z_1) ...

https://codeforces.com/contest/1659 D. Reverse Sort Sum   题意：有一个长为 nnn 的数组 AAA，共操作 nnn 轮，第 iii 轮操作对 AAA 中前 iii 个元素排序，把这 nnn 轮得到的 nnn 个数组对应位置相加，得到数组 CCC，先给定数组 CCC，要求还原出数组 AAA。 双指针 目的是找出 AAA 中所有 000 的位置。 一个指针指向当前轮的第一个 111，另一个指针指向当前知道的最后一个 000。 现在移动指向 000 的那个指针，若下一个位置是 111，则得到的数组和上一轮相同，那么指向第一个 111 的指针所在位置上的元素和+1（因为它这一轮还是 111）；若下一个位置是 000，则指向第一个 111 的指针所在位置上的元素和从此以后不再增加（因为它以后将始终是 000），所以只要看指向第一个 111 的指针相比于初始状态增加了几，就能知道指向 000 的指针移动了几次后找到了下一个 000​。 为了比较指向第一个 111 的指针相比于初始状态增加了几，就要把所有历史轮次操作组成的矩阵填充成右上部分全 ...

https://codeforces.com/contest/1654 D. Potion Brewing Class   题意：有长为 nnn 的正整数数组 aaa，给定 n−1n-1n−1 个条件，每个条件要求 ai/aj=x/ya_i/a_j=x/yai​/aj​=x/y，问数组所有元素的和，mod 998244353。 dfs nnn 个点，n−1n-1n−1 个条件，刚好建成一棵树，每条边为儿子与父亲的比值，根为 a1a_1a1​，则 ai=a1a_i=a_1ai​=a1​乘 iii 到根的路径上边权的的积。aia_iai​ 是正整数说明 a1a_1a1​ 是所有分母的lcm。求出 a1a_1a1​ 后再遍历求和即可。 但是要取模，无法求lcm。所以质因数分解，记录每个质数的最大出现次数，乘起来就是lcm。 分子要用来约分，所以同样要一路记下来。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626 ...

https://codeforces.com/contest/1647 E. Madoka and the Sixth-graders   题意：房间里有 nnn 个座位，第 iii 个座位上的人的编号为 bi∈{1,2,⋯ ,n}b_i\in\{1,2,\cdots,n\}bi​∈{1,2,⋯,n}，每一轮座位 iii 上的人移动到座位 pi∈{1,2,⋯ ,n}p_i\in \{1, 2,\cdots,n\}pi​∈{1,2,⋯,n}，若多个人移到同一个座位，则编号最小的人留下，其他人永远离开游戏。房间外有无限多的人，编号为 n+1,n+2,⋯n+1,n+2,\cdotsn+1,n+2,⋯，每一轮移动后必定空出座位，房间外的人按编号顺序坐到空座位上。经过若干轮后，最终座位 iii 上的人的编号为 aia_iai​。给定 ai,pia_i,p_iai​,pi​，问初始排列 bib_ibi​，保证有解，输出字典序最小的解。 倍增 把 ppp 建成图，入度为 000 的就是空座位，且每轮都一样。通过空座位上的人的编号可以知道游戏进行了几轮，记为 CCC。 倍增得到 CCC 轮后初始每个座 ...

https://codeforces.com/contest/1658 B. Marin and Anti-coprime Permutation   题意：给定 nnn，问有几种 nnn 的排列 ppp，使得 gcd⁡(1⋅p1, 2⋅p2, …, n⋅pn)>1\gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) > 1gcd(1⋅p1​,2⋅p2​,…,n⋅pn​)>1. 数论 gcd只可能是1或2. 假设 gcd=k，则 111 到 nnn 中所有非 kkk 的倍数都必须与 kkk 的倍数相乘。而总共有 ⌊nk⌋\lfloor\frac{n}{k}\rfloor⌊kn​⌋ 个 kkk 倍数，所以必须要 2⋅⌊nk⌋≥n2\cdot\lfloor\frac{n}{k}\rfloor \geq n2⋅⌊kn​⌋≥n，则 k≤2k\le 2k≤2。 1234567891011121314151617181920212223242526272829303132333435363738394041424 ...