Topcoder-566

嘛，今天 rp 蛮好的，于是 rank 11 了。 rating 怒 += 139。

Solution

250

直觉告诉我合法的方案只有几种特定情况。

枚举后发现是 4 种： 1. 一条边都不选 2. 选一条边 3. 选一个点，然后选这个点的若干条邻边 4. 选一个三角形

然后枚举就可以了。

500

第一眼：不会做。

第二眼：好像可以矩乘。

第三眼：好像矩乘会超。

第四眼：不会做。

第五眼：优化掉一维？貌似可做了。

恩，大概就是这样。

---

如果你没看懂，还是解释一下吧。

一个 \(O(n^3 \log d)\) 的矩阵乘法是显然的。 \(n\) 一定是一个循环节，预处理 \(n\) 步之后到达各个位置的方案数，然后就可以直接矩乘了。

但是暴力矩乘是会超的。观察后发现，我们并不一定要记录若干步后从 \(i\) 到 \(j\) 的方案数，只需记录 \(i - j\) 为一特定 \(\delta\) 时的方案数即可。即，矩阵中 \(i - j\) 相同的若干个元素一定相同。于是需要维护的量从矩阵降为一个向量，然后暴力乘过去就可以了。如果你足够牛且特别想装 13 ，你还可以写个 FFT/NTT 啥的。

1000

不会做，挖坑中。

现场居然没人做出来？似乎 lyrically 上手就做 1000 结果爆零了。

situation

一看 250 蛮简单的嘛，水掉。

一看 500 似乎也不难，水掉。

然后觉得没啥可做的了， 1000 目测想不出来，而且样例都特别强，cha 人基本上没啥希望，于是到一边玩去了。

然后考手速混到了 rank 11 ？ 根据 RP 守恒定律，目测下次 CF 要跌了……T_T

others

（正当我准备看其他人做的肿么样的时候，TC 连接不上了= =||）

XLk 晚了一步，没能报上名。

ryz rank 53 也不错了。

xiaodao 第一题交的很慢于是分数很低。

大叔由于找笔耽误了几秒，导致 250 没调出来，于是凄婉爆零。momo。

秋锅过了第一题。