B. Light bulbs
题意：
起初\(n\)个位置状态为\(0\)，\(m\)次操作，每次操作更换区间状态：\(0\)到\(1\)，\(1\)到\(0\)。
共有\(T,T\leq 1000\)组数据，\(n\leq 10^6,m\leq 1000\)。
最后输出状态为\(1\)的个数和。
思路：
一开始冲了一发维护差分，最后求出前缀和，成功\(TLE\)。
其实只要发现有用的点只有\(2m\)个，之后从左到右扫一遍，类似于扫描线的思想，累加贡献就行了。
C. Triple
题意：
给出三个数组\(A,B,C\)，要求满足条件的三元组\((i,j,k)\)，满足：
\[\left\{\begin{aligned}|A_i-B_j|\leq C_k\\|B_j-C_k|\leq A_i\\|A_i-C_k|\leq B_j\end{aligned}\right.\]
限制条件：\(n\leq 10^5,1\leq A_i,B_i,C_i\leq 10^5\)。
思路：
- 数据范围较小时，可以考虑枚举一个\(i\)作为最大值，然后其余两个数组双指针来扫，时间复杂度\(O(3*n^2)\)。
- 但这对于本题数据来说，显然会\(T\)的，考虑如何优化。
- 注意到在多项式乘法当中，两项相乘其指数相加，那么我们可以将数组对应挂在指数上面，系数则为对应指数出现次数，那么将两个多项式乘起来最终得到一项\(x^n\)，其前面的系数则为两数相加和为\(n\)的方案数。
- 此过程\(FFT\)优化即可，时间复杂度\(O(nlogn)\)。
因为本题数据比较特殊，所以就小范围暴力，大范围\(FFT\)优化即可。
另外还注意一些细节，去重的问题：
- 如果出现多个都为最大值的情况，会重复计算。
- 小范围暴力时，可以参考我的代码，只是有些地方限制一下即可。
- \(FFT\)处理时，将三个数组丢到同一个数组当中进行排序，然后扫一遍，对于第\(i\)个位置，假设目前其为最大值。那么我们减掉一下情况就行(以\(a_i\)为最大值为例)：
- \(b_j\geq a_i,c_k\geq a_i\)
- \(b_j\geq a_i,c_k<a_i\)
- \(b_j<a_i,c_k\geq a_i\)
- 所以用个桶维护每种数出现次数即可。
详见代码（有点复杂...）
D. Counting Sequences I
题意：
定义一个好的序列\(a_1,a_2,\cdots,a_n\)满足：\(n\geq 2\)且\(a_1+a_2+\cdots+a_n=a_1\cdot a_2\cdot \cdots a_n\)。
给定一个长度\(n\)，问有多少长度为\(n\)的序列满足是好的序列。
思路：
- 注意到\(1\)在等式里面比较特殊，因为不断增加\(1\)的个数，那么等式左边会不断增加，而等式右边则会不变。
- 因为题目给出的\(n\)较小，所以直接爆搜即可，但要注意剪枝：两边的差已经不能用\(1\)弥补时就及时中止。
代码中爆搜的时候并没有考虑\(1\)，而是默认用\(1\)来补差值。同时还要维护一些分母上的东西用来统计答案。
详见代码吧：
E. Counting Sequences II
题意：
给出限制条件\(n,m\)，构造序列\(a_i\)，满足\(1\leq a_i\leq m\)对于\(1\leq i\leq n\)，并满足偶数的个数为偶数。
思路：
- 对于一个偶数，其出现次数可能为\(0,2,4,\cdots\)；对于一个奇数，其出现次数可能为\(0,1,2,3,\cdots\)。
- 因为所求情况数为排列，考虑指数生成函数，我们将每个数可能出现的次数挂到指数上，系数则为方案数。
- 易知对于一个偶数，其生成函数为：\(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots\)；对于一个奇数，其生成函数为\(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\cdots\)。
- 因为小于等于\(m\)的数有\(\lfloor\frac{m}{2}\rfloor\)，记其为\(t\)，那么答案就为\((\frac{e^x+e^{-x}}{2})^te^{x(m-t)}\)的第\(n\)项的系数乘以\(n!\)。
- 最后随便化一下，把\((\frac{e^x+e^{-x}}{2})^t\)展开，就得到：\(\frac{1}{2^t}\sum_{i=0}^t {t\choose i}e^{(m-2i)x}\)，其第\(n\)项系数为\(\frac{1}{2^t}\sum_{i=0}^t (m-2i)^n\)。
预处理一下阶乘和逆元就行了。
总结一下，关键还是第一步构造生成函数的思想，对每个数独立考虑所有的情况，其余的都很好推。
生成函数nb！多项式nb！
F. Rhyme scheme
题意：
求字典序第\(k\)大的序列，该序列满足每一位不会大于前面的最大位加一。
思路：
- 因为是字典序第\(k\)小，所以考虑逐位确定，但是每当我们考虑某一位时我们需要知道后缀个数信息。
- 考虑\(dp\)(递推)()来计算这个信息。
- 显然每一位与之相关的有当前位数和前面最大的位数，同时由于与后缀相关，我们考虑从后往前依次考虑不同长度的后缀。
- 设\(dp[n,i,j]\)表示长度为\(n\)的后缀，当前从后往前第\(i\)位，前面最大值为\(j\)时的方案数，那么就有转移方程：
\[dp[n][i][j]=dp[n][i+1][j]*j+dp[n][i+1][j+1]\]
之后逐位确定就行。
G. Substring
题意：
现定义两个字符串相等：
- \(S_1=T_1,S_n=T_n\)；
- 每个字母出现次数相等。
现在给出串\(S\)，然后\(n\)个串，对于每个串，回答它与多少\(S\)的子串相等。串的长度之和不超过\(10^5\)。
思路：
- 首先思考如何判断两个串相等，因为与顺序无关，所以我们可以换一下哈希的方法，使得哈希值只与字母以及出现次数有关。
- 具体地说就是\(hash[i]=hash[i-1]+p[s[i]-'a']\)，\(p[k]=p^k\)。
- 因为\(n\)可能很大，对于每个串直接回答会超时。如果只有一个询问的话，因为长度固定，所以可以考虑类似于滑动窗口那样，那么对于一种长度\(O(n)\)就可以求解。
- 注意到虽然有多组询问，但是询问串的长度总和不超过\(10^5\)，也就是说长度不同的串为\(\sqrt{10^5}\)个，考虑时限比较宽松，那么直接枚举长度搞就行。
我实现是用了两个unordered_map，最后两个相减得到答案，详细见代码吧：
J. Stone game
题意：
现在有\(n\)个石头，每个石头都有权值\(a_i\)。
现在要拿石子，直到满足下面的条件：目前手中石子的权值和大于等于剩下石子的权值和，并且拿掉任意一块石子，手中石子的权值和就小于剩下石子的权值和了。
问这样拿石子的方案有多少种。
思路：
- 注意到最终去掉的石子一定为权值最小的一块，那么我们可以考虑枚举最小权值的石子，然后再来\(dp\)。
- 定义\(dp[i][j]\)表示前\(i\)个石子，权值和为\(j\)的方案数，那么考虑当前石子拿或者不拿直接\(dp\)就行了，很简单的计数\(dp\)。
- 但是这样搞复杂度是\(O(n^3)\)的，显然不能接受。
- 发现我们直接这样搞会计算很多重复的部分，比如前面的很多东西都会重复计算，并且我们每次计算的其实是一个后缀。那么直接将\(dp\)改为从后往前\(dp\)就行了：最小权值每减少一次，\(dp\)就会多计算一个，这样复杂度就为\(O(n^2)\)了。
注意最后要特判一下最后一个位置。
L. Digit sum
数位\(dp\)板子，或者直接暴力==