给出
- 对60%的数据,
- 对100%的数据,
先看看 是什么东西, 尝试把 拆开.
解特征根方程
考虑求
即, 给一个集合, 从中选
隐约看到了递推关系. 60分的DP呼之欲出: 设
这个式子看起来没啥前途......可不可以分治呢?
分治FFT!
但是模数99991不是很支持......我并不知道怎么做任意模数的NTT. 尝试了半天, 99991除了是个素数, 好像没啥好用的性质......难道正解不是FFT?
离考试结束还有15分钟的时候, 我突然想到, 省选D1T3直接FFT精度不炸, 是因为数值比较小. 嗯, 99991的一个性质是比较小......long double直接上......
就这样, 我在NTT这棵树上吊死了......TAT
代码在雅礼的校内OJ上, 忘记自己保存一份啦. -_-b