# 2021-9-16 Test

100 + 0 + 0 + 30
T1 由于高中数学知识有点忘了，写了 2h+
T2 并不知道这个奇妙的 MO 结论
T3 没开
T4 一直在考虑转换贡献贪心，没有想到网络流
总之就是知识树不够广，思维不够活跃

# Raster

三维空间中很多三角形，全在 $xy$ 平面上方，每次询问一条端点在 $xy$ 平面上，垂直与 $xy$ 平面的一条射线穿过的若干三角形中，哪个三角形到端点最近。

$$n,Q\le 1000$$

# Sol:

无脑 $\mathrm O(nq)$ ，每个三角形求个法向量，这样就能表示平面方程了，然后求出每条射线与每个三角形平面的交点看是不是在三角形内部，这个解个平面方程在用叉积看一看就好，调试上的细节是如果复制了两个差不多的代码段前一个有错那后裔个一定有错

# Binom

给定一个质数 $p$ ，和一个整数 $n$ ，对所有 $0\le k\le K$ 求有多少 $0\le m\le n$ 使得 \binom{n}{m}\equiv 0\pmod

$$n\le 10^{1000}, K\le 3000, p\le 10^9$$

# Sol:

这种 $n$ 贼大的看到就只有两种出路…
要不高精搞，要不数位 dp。 见识少极易被打脸
UPD: 对了，还可能与其无关

这题要利用一个 MO 结论， $kummer$ 定理： $\binom{n + m}{n} \equiv 0\pmod{p^k}$ 若成立，则 $n,m$ 在 $p$ 进制下的加法进了 $k$ 次位。
知道这一点后先把给出的 $n$ 当做 $n+m$ 转成 $p$ 进制，然后套路地设 $dp_{i,j,0/1,0/1}$ 表示从高到低第 $i$ 位，已经进了 $j$ 位，上一位进了 / 没进，当前有 / 无顶上界的方案数，转移有亿点点细节～
此时我们得出的是 $x,y \le n$ 的方案数，我们要求的是 $x+y = n$ 的答案，于是我们把 $n--$ 再做一遍容斥掉即可。

# CRC

给定一些模 $2$ 意义下的多项式，给出一些 $a$ ，给定 $c$， 求出 $b$ ，满足 $c = a \mod b$

$$n\le 3000, |\sum| \le 3000$$

# Sol:

发现模 $2$ 意义下，多项式减法就是异或啦
然后把每个 $a$ 先减去 $c$
然后直接做一个多项式 $\gcd$
考虑把普通的 $\gcd$ 放到多项式上，发现就是模拟一个大除法的过程
用 $bitset$ 优化以下即可通过此题。

# Food

若干城市形成一张有向图，每个城市有一些产能 $e_i$ 可正可负，每座城市有个权值 $d_i$ ，其贡献为 $d_i|e_i|$ ，有 $m$ 条路 $(u,v,c,w)$ ，每条路可以花费 $w$ 使得 $e_u--, e_v++$ 最多用 $c$ 次，最小化贡献和

$$n\le 200, m, d, |e|, c\le 4000$$

# Sol:

发现走一条路的效果是 $e_u--, e_v++$ ，很像流量守恒，于是考虑网络流
原来的路边我们保留，那么网络上流量的意义就是产能 $e$ 了
发现流量很多是负的并不好处理，于是我们整体加上一个大数 $\mathrm MAX$ 此时 $MAX$ 为 $0$ 了
源点向每个点连一条 $M + e_i$ 的边表示每个点初始的产能，然后发现这些流量是可以在点之间流流流的，每个点最终流量 $f$ 考虑在它流到汇点时统计答案

若 $f\ge \mathrm MAX$ ，我们认为此时此城市的最终产能是要大于 $0$ 的，贡献应为 $(f-\mathrm MAX) \times d_i$
而 $f < \mathrm MAX$ ，贡献应为 $(\mathrm MAX - f) \times d_i$
考虑用两条边来模拟这个过程，对于每个点，我们向汇点连一条容量为 $\mathrm MAX$ ，费用为 $-d_i$ 的边，这里我们是把第二个柿子拆开来看的，预先把常数 $\mathrm MAX \times d_i$ 加入答案里，那每流一次就自然会减掉 $d_i$ ，类似的，我们还向汇点连一条容量为 $INF$ ，费用为 $d_i$ 的边，由于我们 $MCMF$ 的过程是跑最短路的，所以我们优先会流 $-d_i$ 的路，流满后不难发现就是上面那个过程