1001
1002
题意：给定一个n个点的完全图，边权为lcm(i+1,j+1)，求最小生成树。
考虑这样一个构造方法
所有数字都向自身的最小质因数连边
这样可以保证每个数字的贡献都是其本身，达到了理论最小。（lcm一定比自己本身要大）
然后就有了k棵以质数为根的树
然后考虑连接这k棵树
显然质数之间的lcm就是它们的乘积
所以所有根都和2连边即可
考虑计算答案
记(tot)为2到n+1的所有素数的和
考虑如何计算tot
这是一个min25模板题，不再赘述
实际上，也可以通过分块打表的方法通过此题。
1003
签到题
显然最后一个用距离出口最近的即可。
1007
题意：给出一个字符串，将其重新排列，使得该字符串的border最大
比较显然的构造是出现次数最多的字母全部放在开头，然后border就是该字母出现的次数
由border的简单性质可知答案不可能比这个大，因此具有正确性
1010
签到题
按照题意模拟即可
1013
题意：给定一个多项式，操作n-1次。第k次操作为令(f(x)=B_k*f'(x)+C_k*f(x))。求操作n-1次后的多项式。
考虑算贡献
显然原多项式的高次项会对最终答案的低次项产生贡献
考虑怎么算xk对xi的贡献
首先贡献系数的话
如果(bk=ck=1)的话显然就是一个NE-Latice-Path问题
贡献系数也就是一个组合数
既然有了系数
那么只需要模拟NE-Latice-Path的计算过程
设一个生成函数#h_k(x)=B_k*x+C_k
把这n-1个单项式乘起来即可得到关于贡献系数的多项式
这一步需要通过类似线段树分治的分治NTT实现
这里一定要注意写的常数小一些
不要采取封装多项式的写法
这里我采用了类似
除此之外还要考虑求导本身产生的系数
简单推导发现(x^k)对(x^i)产生的贡献是(frac{k!}{i!})
整理一下
设：
最终多项式的系数为(f_k)
求导k次的贡献系数为(g_k)
发现这是一个下标差为定值的的卷积
是一个经典套路题
翻转数组后即可转化为正常形式的卷积
大力NTT即可
总复杂度(O(nlog^2n))