去学军中学培训了两个星期，感觉自己水平太差了。而且消耗在其他地方的时间太多，OI学的太少。
而且消耗在其他地方的时间太多，OI学的太少。回来以后，把这次去培训做的一些题总结一下，可能不太全面，因为很多题我水平太差，连讲解都听不懂。并给自己一个未来的计划。今年的自招政策要改，可能降不了多少分了，不过既然选择了OI，就不要让自己后悔，还是努力一点吧。
用E表示考试的编号，T表示题号。
E18T1
求$$\sum_{i=1}^n \sum_{j=1}^n S_{i,j} \times F_j \times P_j$$其中，$F$是错位排列数，$P$是圆排列数，$S$是第二类斯特林数。答案对$998244353$取模。
$n \le 100000$
圆排列和错位排列都能$O(n)$求出来，但是斯特林数用朴素的方法只能$O(n^2)$递推，所以要先用二项式反演求出通项，再用NTT求出。
原式可化为：$$\sum\limits_{i=1}^nF_i\cdot (i-1)!\sum\limits_{j=0}^i \frac {(-1)^j} {j!}\cdot \frac {1} {(i-j)!} \sum\limits_{k=1}^n(i-j)^k$$
设$f(x)=\frac{(-1)^x}{x!}$，$g(x)=\frac{1}{x!} \sum\limits_{i=1}^nx^i=\frac {x^{n+1}-1}{x!(x-1)}$，原式就是:
$$\sum\limits_{i=1}^nF_i\cdot (i-1)!\sum\limits_{j=0}^if(j)g(i-j)$$
后半部分是一个卷积，用NTT完成就好啦。
小结
公式太难打了。
二项式反演不会，斯特林数递推式看不出来，NTT不会。
对于求和式，想到求出通项后求解，求出通项以后往往能用NTT优化，且模数也已经暗示了可以用NTT。
在和式的化简上，注意能不能用运算律调换顺序。这道题是扩大了求和的范围，把值为0的地方也加进来，简化了运算。
T2
用Lucas定理证明了结论，然后用子集DP，即枚举所有子集转移。但是这样做复杂度很高，而且这道题卡空间，所以需要分两部分考虑。需要用到快速莫比乌斯变换快速求子集和。
小结
和kyr1no学长出的那道题一样，$n$为奇数即$n \mod 2 = 1$，然后用lucas定理证明。想不到奇数的性质和lucas定理。
子集dp没学过。
T3
写出$\varphi$函数的通项，把询问排序，用树状数组维护$\frac{p_i - 1}{p_i}$的积，每次直接回答。
小结
和HH的项链那道题很像，都是把询问排序，树状数组维护一个区间内的信息，记录上一个出现的位置。
对于没有修改的询问，可以考虑把询问离线后排序，类似莫队算法和cdq分治。
要想到对于值域开线段树或者树状数组，这样可以把顺序的区间改为值的区间，有时候会很有效果。
总结
对于$\varphi$函数和斯特林数，都把他们转化为了通项或者计算式，也应该想到把复杂的式子和计算转化为基本的运算，求出通项，再用数据结构或者类似FFT去优化。
学一个东西就要学透，如果急功近利一知半解，用的时候才发现自己什么都不会，就损失惨重了。
只有Day1的，咕咕咕……