#include <Seter> - using namespace Orz;

2114: 完美数

RunID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
185268	Seter	2114	Accepted	776 kb	20 ms	C/Edit	998 B	2012-01-02 19:48:39

今天又学到新东西了——如何求比x大的第n个回文数？答案就是，给每个回文数从小到大用自然数连续编号。

我们假设0的编号是1，按照回文数，回文节（前一半位数），编号列表：

RunID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
175346	Seter	2179	Accepted	1756 kb	1120 ms	C/Edit	1597 B	2011-11-22 19:17:39

于是花了3个小时写了个分治版的大数乘法……压9位后常数果然巨小，60000位时比FFT还快一点！膜拜AC大神208MS稳居榜首！

用FFT过掉后看到TIM是用分治的……于是回去想了好久……终于想出来了……

坑了个爹的FFT……原理只了解到卷积那一步……怎么转换成整系数而非sincos乱搞的系数那个完全不了解……权当背代码了……

其实代码灰常好写……根本不像我想像的那样超级复杂！代码的关键在于如何选P（[tex]$P=C*2^{\log n}+1$[/tex]）……

作为一套NOIP2008的卷子AK表示亚历山大。

1.统计N!末尾0的个数。正整数N<10^1000

2.要求支持三个操作：插入给定的字母串。删除给定的字母串。查询给定的仅含?与字母的正则表达式能匹配上的串数。操作数Q<3000，字符串长度<=20