FFT NTT小结

一个问题

给定$a_i,b_i$,定义$c_n=\sum_{i=0}^n a_ib_{n-i}$,求$c$序列。

HN省队集训D1T3 Or

生地会考后发现自己连NTT的板子都不会打了….

果然是好久没写代码了…

准备重新学习FFT和NTT和FWT

HNOI2017 礼物

题目传送门

显然,我参加了这次HNOI。

然而并没有什么用,只拿了纯良心的70pts暴力。

30%的数据满足n≤500, m≤10;

70%的数据满足n≤5000;

100%的数据满足1≤n≤50000, 1≤m≤100, 1≤ai≤m。

并不知道在$30pts$ $m\le 10$的基础上,为什么$100 pts$ $m\le 100$,包括$70 pts$ $m\le 100$,然而后面两个部分分真的m可以开到很大。

题解

显然手环2亮度减c和手环1亮度+c是等价的,所以修改相当于在手环2亮度+c$(|c| \le m)$(显然)

假设下标从0开始到n-1(原题为从1到n)

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×