暂无

一场cf edu, 好惨好惨

暂无

无

cf div2

暂无

无

打了atcoder，rating小涨。

无

补题+学习

补题+整理板子

补题，学点新东西

HDU 6061

多项式卷积,NTT

先给定一个$f(x)=\sum_{i=0}^{n}c_{i}x^{i}$,然后求解$g(x)=f(x-\sum_{i}a_{i})=\sum_{i=0}^{n}b_{i}x^{i}$

输出$b_{i}$

$A=-sum{a[i]}$并取模变成求解$f(x+A)$少去正负计算

然后按$f(x+A)$每一项进行一个展开(会成一个三角表)

目标多项式系数$b_j=\sum_{i \geq j} c_i A^{i-j} C_i^j$

化解后有$j!A^jb_j=\sum_{i=j}^{n} \frac{c_{i}i!A^i}{(i-j)!}$

整体上$g(x)=\sum_{i=0}^{n}\frac{x^{i}}{A^{i}i!}\sum_{j=0}^{n-i}\frac{c_{i+j}(i+j)!A^{i+j}}{j!}$

这里令$k=n-(i+j),g(x)=\sum_{i=0}^{n}\frac{x^{i}}{A^{i}i!}\sum_{j+k=n-i}\frac{c_{n-k}(n-k)!A^{n-k}}{j!} =\sum_{k=0}^{n}\frac{x^{k}}{A^{k}k!}\sum_{n+k=i+j}\frac{c_{i}(i)!A^{i}}{(n-j)!}$

将$\frac{1}{j!}$当作一个翻转(两者都可),求$\sum_{i}c_{i}i!A^{i}x^{i}$与$\sum_{i}\frac{1}{(n-i)!}x^{i}$的卷积,然后取结果$n+i$项系数即可

D - Moving Piece

枚举，贪心

给定步数和诸多环，求在某个环上走的最大收益。

枚举每个点作为起点然后分类讨论，如果步数不够一圈就模拟一下找一个最大值。

如果够一圈则在模拟走一圈内的最大值和走多圈和余下步数的最大值取个最大值即可。

分类没有处理好WA了很多发，这种简单题也要注意细节。