WORIA

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

矩阵 以下运算中矩阵的秩不变： 某列乘以非零标量 交换列次序 加入一列其他列的线性组合 转置（所以以上列可替换为行） 行列式： 方阵才有行列式，是各列的线性函数（见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 ...

https://acm.ecnu.edu.cn/contest/497/ C. Paint   题意：一个长为 nnn 的数组，初始全为0，mmm 次操作，两种：1. 把最后 xxx 个元素全部变为 yyy；2. 查询当前有几个不同的数。 栈 用栈模拟，同时记录每种颜色的出现次数。 1234567891011121314151617181920212223242526272829303132333435363738#include <bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e6 + 10;const int INF = 0x3f3f3f3f;typedef pair<int, int> pii;int n, m;int cnt[N];int ans = 1;stack<pii>st;int main() { scanf("%d%d", &n, &m); st.push({1, 0 ...

https://acm.ecnu.edu.cn/contest/463/ D. 赌怪   题意：A，B两人轮流从 [1,1018][1, 10^{18}][1,1018] 各抽取 nnn 张牌，可能重复。抽完后，A 先打出一张牌，B 必须打出一张比 A 大的牌。打出就丢掉。若 B 无法出牌则 A 赢，否则 B 赢。问 A 赢的概率。 卡特兰数 数字范围很大，可以近似认为不会抽到重复的牌。 把 A，B 抽到的牌放一起从小到大排序，必须满足在任意位置 p，从开始位置到位置 p 这个区间中，A 牌的个数大于等于 B 牌的个数。也可以说 A 的最小的牌小于 B 的最小的牌，A 的次小牌小于 B 的次小牌。这两种说法等价。 这其实就和括号序列的合法性是一样的。A 视为左括号，B 为右括号。 所以牌的排列方式个数就是 n 对括号的合法序列数，也就是卡特兰数。 ans=1n+1(2nn)(2nn)=1n+1ans=\frac{\frac 1{n+1}\binom {2n}n}{\binom {2n}n}=\frac{1}{n+1} ans=(n2n​)n+11​(n2n​)​=n+11​ 12345 ...

仅为考试复习，非笔记！ 曲线积分 第一型曲线积分∫Lf(x,y)ds\int_L f(x,y){\rm d}s∫L​f(x,y)ds： 解法： 参数方程：x=ϕ(t)\phi(t)ϕ(t) , y=φ(t)\varphi(t)φ(t). =∫baf(ϕ(t),φ(t))ϕ(t)2+φ(t)2dt=\int ^a_b f(\phi(t),\varphi(t))\sqrt{\phi(t)^2+\varphi(t)^2}{\rm d}t=∫ba​f(ϕ(t),φ(t))ϕ(t)2+φ(t)2​dt 非参数方程： 将x作为参数，同理。 第二型曲线积分∫LP(x,y)dx+Q(x,y)dy\int_L P(x,y){\rm d}x+Q(x,y){\rm d}y∫L​P(x,y)dx+Q(x,y)dy： 解法： 参数方程：x=ϕ(t)\phi(t)ϕ(t) , y=φ(t)\varphi(t)φ(t). =∫ba[P[ϕ(t),φ(t)]ϕ′(t)+Q[ϕ(t),φ(t)]φ′(t)]dt=\int ^a_b [P[\phi(t),\varphi(t)]\phi&#x ...