0%

Topcoder-566

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

solution

250

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

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

然后枚举就可以了。

500

第一眼:不会做。

第二眼:好像可以矩乘。

第三眼:好像矩乘会超。

第四眼:不会做。

第五眼:优化掉一维?貌似可做了。

恩,大概就是这样。


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

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

但是暴力矩乘是会超的。观察后发现,我们并不一定要记录若干步后从 ij 的方案数,只需记录 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。

秋锅过了第一题。