补一下之前欠的两道题：2022-12-15 #13 放眼望去 无论是哪一颗星星 都比自己美丽。
71 CFgym104053F Equations
不会做，数论好难啊，感谢裙友教我。
注意到 \(f(a,b,m)\) 的 \(a,m\) 的地位是大致等价的，因为其对应二元不定方程 \(ax+my=b\) 的 \(x\) 最小自然数解。
我们想交换两维，这样我们可以应用 \(f(a\bmod m,b,m)=f(a,b,m)\) 使得枚举量降到 \(O(a)\)，于是我们对称地考察 \(y\) 最小自然数解，即 \(f(m,b,a)\)。
记 \(f(a,b,m)=x_0,f(m,b,a)=y_0\)。
若方程无 \(x,y\) 均非负整数解，其一定满足：
\[ax_0+my_0=b+\operatorname{lcm}(a,m) \]证明：不妨考虑 \(\gcd(a,m)=1\) 的情况，取到 \(y=y_0\) 时 \(x\) 为负数，而 \(y=y_0-a<0\) 时 \(x\) 一定为正。两者只差一个调整单位（\(y\) 减去 \(a\)，\(x\) 加上 \(m\)），因此此时 \(x\) 为最小自然数解 \(x_0\)，即 \(ax_0+m(y_0-a)=b\)。
枚举 \(i_0=i\bmod a\)，那么容易计算出 \(y_0\)，若满足上述条件，则有：
\[x_0=\frac{b+\operatorname{lcm}(a,i)-iy_0}{a} \]由于 \(i=ka+i_0\)，\(\gcd(a,i)\) 不会变，因此合法 \(x_0\) 是一个等差数列，容易计算。
不满足上述条件时至少有 \(iy_0\leqslant b\)，若 \(y_0>0\)，我们暴力枚举 \(i\) 直到其满足条件，枚举量是 \(O(a\times\frac ba=b)\) 的。
若 \(y_0=0\)，则 \(x_0=\frac ba\bmod\frac{i}{\gcd(i,a)}\)，枚举 \(i_0\) 则 \(\gcd(i,a)\) 固定，取模转整除做整除分块就好了。
复杂度 \(O(V\log V)\)（\(V=\max(a,b)\)）。
72 CFgym104053K Middle Point Graph
题意就是让我们考虑特殊几何结构的共面，讨论一下。
- 无中点：共面概率为 \(0\)；
- 一个中点：选择这条边对应两个顶点，那么另一个顶点可以任选。
- 两个中点：
- 选择一条边以及其两个顶点，再任选一条边；
- 选择一个三元环上两个点以及上面两条边，注意不能和上面重复，因此我们只能选择两条共顶点的边以及非公共顶点的两个顶点；
- 三个中点：三元环的三条边以及上面一个点；
- 四个中点：四元环。
三元环和四元环计数都是 \(O(m\sqrt m)\) 的。
295 2022 集训队互测 Round 11 C 卡牌游戏
296 CF1810H Last Number
297 CF1804G Flow Control
298 CF1804H Code Lock
很神秘的题。
很容易发现串是没有用的，我们只用得知任意两个字母之间来回的次数。
先考虑 \(k\) 为偶数的情况，考虑拆贡献，我们发现一对相对的边的经过次数相较于一条边的经过次数更容易刻画，其经过次数和一定是跨越两个半圆的字母对数量。
我们枚举所有大小为 \(\frac k2\) 的集合 \(s\) 作为初始集合，考虑类似旋转卡壳地移动一对边（一加一删）来遍历每个半圆并 dp 出答案。内部可以继续使用一个状压 dp 来记录哪些边状态与初始状态不同，转移 \(O(k)\) 枚举一下边即可。
上面的 dp 看起来状态数就很少（由于是加一条边删一条边，状压的集合与 \(s\) 交的大小只有两种），官方题解说 dp 有效状态数只有 \(82818450\) 种。
注意要实现精细一点，比如钦定加入的第一条边是 \(1\)，不这样写状态数还会带上 \(k\)。
\(k\) 为奇数做法没有什么不同，可以发现距离为 \(\lfloor\frac k2\rfloor\) 的边可以代替上面所说的相对边，我们类似地枚举初始集合并加/删边算一下答案即可。
标签：frac,gcd,49,bmod,枚举,dp,2023,20,顶点 From： https://www.cnblogs.com/xiaoziyao/p/17333790.html