比赛链接:http://acm.hdu.edu.cn/contests/contest_show.php?cid=909

B – Graph Theory Class

令 $f(n)$ 为小于等于 $n$ 的质数个数,答案其实就是

$$\sum_{i=3}^{n+1}i+f(n+1)-1$$

然后用 min_25 求 $f(n)$ 即可

代码链接

E – Lunch

设只有一根长度为 $l_i$ 的巧克力局面的 SG 值为 $SG(l_i)$

那么当前局面 SG 值就为 $\bigoplus_{i=1}^{n} SG(l_i)$

令 $pri$ 为任意不为 $2$ 的质数,那么 $SG(x\cdot pri)=SG(pri)+1$。当 $x$ 为奇数时,类似的有 $SG(x\cdot 2)=SG(x)+1$;当 $x$ 为偶数时,考虑 $x$ 获得 $SG(x)$ 级胜态的策略,$1$ 级胜态的局面为奇数根长度为 $2$ 的巧克力,如果 $SG(x*2)$ 采取相同的策略,最后的局面则为奇数根长度为 $4$ 的巧克力,此时 SG 值仍然为 $1$。因此 $x\cdot 2$ 不存在获得 $SG(x)+1$ 级胜态的策略,即此时 $SG(x\cdot 2)=SG(X)$。

代码链接

F – Robotic Class

考虑每个区间的临界点,将其分别放入左右区间的路径上去模拟,如果到达 $n$ 点的数值不同,则函数不连续。

模拟其实用 DFS 和 BFS 均可,下面代码是我用 BFS 的写法。

代码链接

M – Residual Polynomial

对分治 FFT 的理解还不够到位,比赛时没有想出来。

先考虑 $a_i$ 对 $w_{i-j}$ 的贡献。感性理解一下, $f_{1}$ 经过了 $j$ 次求导和 $n-j$ 次平移后,$a_i$ 的贡献才能加在 $w_{i-j}$ 上。因此我们令 $d_j$ 为 $\prod_{i=2}^{n}(b_ix+c_i)$ 的第 $j$ 项系数,那么 $a_i$ 对 $w_{i-j}$ 的贡献就为 $a_i\cdot d_j\cdot i!/(i-j)!$ 。

令 $a_i\cdot i!$ 的母函数为 $f(x)$,$d_{n-i}$ 的母函数为 $g(x)$,那么 $f(x)\cdot g(x)$ 就是 $w_{i+n}\cdot i!$ 的母函数。

代码链接

发表评论

电子邮件地址不会被公开。 必填项已用*标注