A
哇，直接一个 CF*3000。
要求的即为图 2,5，可以用总方案数（ \(\binom{n}{3}\)）减去图 1,3,4。
对于图 1，只要求出一根线左边有多少不与它相交的线，右边有多少线，记为 \(l_i\) 和 \(r_i\)。对答案的贡献为 \(l_i \times r_i\)。
对于图 3,4，两图的共同点为三条线中有两条满足另外的两条线一条与其相交，一条与其相离。
对每条线计算 \(\text{与它相离的线数} \times \text{与它相交的线数}\)，那么每个图 3,4 会被算两次，最后除以二即算出图 3,4 的总数。
现在要求 \(l_i, r_i\)。
对于弦 \((x, y), (x < y)\)。在其左边的条件是：\((x' < x \wedge y' < x) \vee (x' < x \wedge y' > y) \vee (x' > y \wedge y' > y)\)。
在其右边的条件：\(x' > x \wedge y' < y\)。
可以二维偏序求解。
B
正男则反。倒着考虑。
求从终止局面到初始局面移除石子的方案数。
在终止局面每一段石子的方案数是独立的，操作之间的顺序也是独立的。
记 \(cnt_i\) 表示只考虑连续一段有 \(i\) 颗石子的方案数。转移时枚举最后一颗填在哪：
\[cnt_i = \sum_{j=1}^i (i - j + 1) \times \binom{i - 1}{j - 1} \times cnt_{j - 1}\times cnt_{i - j} \]边界 \(cnt_0 = 1\)。
连着位置 \(1\) 的石子要特殊考虑。设 \(pre_{i, j}\) 表示石子从 \(1\) 填到 \(i\)，失败了 \(j\) 次的方案数，转移同样枚举断点：
\[pre_{i, j} = i \times pre_{i, j - 1} + \sum_{k = 2} ^ i(i - k + 1) \times \binom{i + j - 2}{i - k} \times cnt_{i - k} \times pre_{k - 1, j} \]边界 \(pre_{1, 0} = 1\)。
然后把后面的石子的答案统计起来。\(suf_{i, j}\) 表示从 \(i\) 到 \(n\)，有 \(j\) 颗石子的方案数。
\[suf_{i, j} = \sum_{k = 0} ^ {j} \binom{j}{k} \times cnt_k \times suf_{i + k + 1, j - k} \]边界为 \(suf_{n + 1, 0} = 0\)，把过程中下标大于 \(n\) 的位置都归到 \(n + 1\)。
最后答案为
\[ans = \sum_{i = 1} ^ n \binom{m}{i + p - 1} \times pre_{i, p} \times suf_{i + 2,m - p - i + 1} \]C
由于谢直接 \(O(n^2)\) 过了，所以没人好好改了哈哈。
卡常小技巧之 memset 只初始化用得到的数组范围。
P2568
\[\begin{aligned} &\sum_{p \operatorname{is prime}}\sum_{x = 1}^{n}\sum_{y = 1}^{n}[\gcd(x, y)=p]\\ =&\sum_{p \operatorname{is prime}}\sum_{x = 1}^{n/p}\sum_{y = 1}^{n/p}[\gcd(x, y)=1]\\ =&\sum_{p \operatorname{is prime}}\left(2\left(\sum_{x = 1}^{n/p} \varphi\left(x\right)\right) - 1\right) \end{aligned} \]筛个 \(\varphi\) 再求个前缀和就好了。
好吧当时我第二个等号后面变成了 \(\sum_{p}\sum_{x=1}^{n/p}\varphi(x)\) 算出来发现不对然后考虑到是个方阵应该乘二再减去对角线。
P2152
【模板】gcd，但是值域 \(10^{10000}\)。
进行了半个小时高精实现更相减损法哦是叫 Stein算法，T 的死死的又不会写压位。
然后成为语言大师：
x,y=gets.to_i,gets.to_i
while y!=0
x,y=y,x%y
end
print x
P3861
因数个数一般认为是三次根号量级。
求出所有因数，从小到大排序，设 \(f_{i, j}\) 表示把第 \(i\) 个因数分解成 \(\le\) 第 \(j\) 个因数的乘积的方案数。
\[f_{i, j} = \begin{cases} f_{i, j - 1} & d_j \nmid d_i \\ f_{i, j - 1} + f_{pos_{d_i/d_j}, j - 1} & d_j \mid d_i \end{cases} \]边界是 \(f_{1, 1} = 1\)，最后答案为 \(f_{dcnt, dcnt} - 1\)，减去没拆分的。
P6583
\(\dfrac{x}{y}\) 可以表示为十进制有限小数的充要条件是 \(\dfrac{y}{\gcd(x, y)}\) 不含有 \(2, 5\) 以外的质因数。
然后我只会 \(O(n^2\log n)\) 还不如小学的小 Z。
那么 \(\dfrac{x}{y}\) 是可以被表示成 \(\dfrac{bc}{ac}\)，其中 \(a\) 不含有 \(2, 5\) 以外的质因数，\(c\) 不含有 \(2, 5\) 的质因数，\(b\) 任意。
首先是可以找到 \(\le n\) 的所有 \(a\) 的。
对于 \(\dfrac{bc}{ac}\)，先枚举 \(c\)，那么 \(b \in [1, \lfloor\frac{n}{c}\rfloor]\) 取任意数，\(a \in [1, \lfloor \frac{n}{c} \rfloor]\) 只含有质因数 \(2, 5\)。
那么这个范围是一个经典整除分块的范围，\(a\) 的数量随着 \(c\) 增大单调不增，可以用一个指针指着 \(a\) 当前的下标单调前移。
但是 \(c\) 并不取范围内所有数，而是不含质因数 \(2, 5\) 的数，这个可以差分算 \([1, l - 1],[1, r]\) 中的个数，算一个前缀的个数则可以容斥。
LL g(LL x) {return x - x / 2 - x / 5 + x / 10;}
LL g(LL l, LL r) {return g(r) - g(l - 1);}
P5505
容斥。
令 \(f_i\) 表示钦定 \(i\) 人没分到（剩下的不管）的方案，那么对每个特产分开考虑是插板法，再用乘法原理乘起来。
\(f_i = \binom{n}{i}\prod_{j = 1}^m \binom{a_j + n - i - 1}{n - i - 1}\)。
然后容斥 \(ans = \sum_{i = 0}^{n - 1} (-1)^i f_i\)。
标签：pre,cnt,21,sum,石子,24.10,times,binom From： https://www.cnblogs.com/KinNa-Sky/p/18491550