XXI OpenCup Grand Prix of Tokyo D
\[ \begin{align*} ans_k=&\sum_{i=1}^nC_i\prod_{j\leq k}(A_i+B_j)\\ =&\sum_{i=1}^nC_i\sum_{p=0}^{k}(A_i^p\prod_{j_1,j_2,...,j_{k-p},j_l\leq k}B_{j_l})\\ =&(\sum_{i=1}^nC_i(\sum_{p=0}^{k}A_i^px^{p}))(\prod_{i=1}^k(B_ix+1))[x^k]\\ =&(\sum_{i=1}^{n}\frac{C_i}{1-A_ix})(\prod_{i=1}^k(B_ix+1))[x^k] \end{align*} \]
不妨令 \(H(x)=\sum_{i=1}^n\frac{C_i}{1-A_ix},S_k(x)=\prod_{i=1}^k(B_ix+1)\)，有 \(H(x)\) 可以由分治NTT和多项式求逆预先计算。
对于答案有另一个分治方法，对于区间 \([l,r]\)，其左边可以递归求解，右边部分的贡献有 \[ ans_k=H(x)S_k(x)[x^k]=H(x)S_{mid}(x)S'_{k}(x)[x^k] \] 将 \(H(x)\) 变为 \(H(x)S_{mid}(x)\) 的对右边可以产生贡献的部分，显然对于长度为 len 的区间，有贡献的长度不会超过 len，所以复杂度依然与分治NTT相同
CF1810F
观察一个 M 叉树的形成过程，可以发现是不断地一个将深度为 D 的叶子变为 M 个深度为 \(D+1\) 的叶子，这个过程与 M 进制下的加法类似，而原本要求的是一个向上合并的过程，将这个过程看做一个加法，发现答案就是求最小的 \(k\) 使得 \(\sum{m^{a_i}}\leq m^k\)，修改可以用线段树维护加法
群友分享
题意
给定 \(n,m,k\)，求 \(\sum[d| \binom{n}{m} \and cnt(d)=k]d\)，其中 \(cnt(x)\) 表示 \(x\) 的可重质因子个数
\(n,m\leq1e9,k\leq15\)
做法
由库默尔定理可知，\(\binom{n}{m}\) 中 \(p\geq\sqrt n\) 的部分的 \(p\) 的次数最大为 1，且当且仅当 \(n\mod p < m \mod p\) 为 1。
不妨将 \(p\leq\sqrt n\) 暴力计算，复杂度为 \(O(k^2n^{\frac{1}{2}})\)，得到了考虑这一部分的可重因子个数为 \(t\) 的数和
对于 \(p\geq \sqrt n\) 的部分，有生成函数 \([x^k]\prod(1+px)=[x^{cnt-k}]\prod(p+x)\)，对于知道所有因式求某一项的情况，考虑牛顿恒等式
对于 \(A(x)=\sum_{i=0}^{n}a_ix^i\) 的 0 点 \(x_1,x_2,...,x_n\)，记 \(P_n=\sum{x_i^n}\)，有
\[ \sum_{i = 0}^na_{n -i}P_{k-i} = 0 (k\geq n)\\ \sum_{i = 0}^ka_{n -i}P_{k-i} = 0 (k\leq n) \] 于是求出 \(P_0,P_1,...,P_k\)，即可解出 \(a_{n-k}\) 即 \(A(x)[x^{cnt-k}]\)，而 \(A(x)\) 的所有根为满足条件的质数，质数次方和用 min-25 处理
CF1815D
\(m = 1\) 时平凡
\(m\geq3\) 时，容易发现所有奇偶性与 \(n\) 相同的且比 \(n\) 小的都可以凑出，并且显然其他都不可能
\(m=2\) 时，考虑某一位的取值已经确定后，可以将问题转化为比他大的部分和比他小的部分两半，大小部分之间互不影响。就拆分为了子问题，并且取哪一位不影响，不妨取最中间的，每次可使长度减半，然后每一个会递归到最多 6 个子问题，爆搜复杂度为 \(O(6^{\log\log n})\)
LuoguP3763
#####法1：
枚举每个位置为起点，找失配三次最多匹配到哪里，用二分加上hash可以快速算，复杂度为 \(O(kn\log n)\)
法2：
枚举每种字符，若是这种字符则置1，否则置 0，用差卷积表示这种字符的匹配，使用 FFT 计算复杂度为 \(O(\sum n\log n)\)
LuoguP3538
对于长度为 \(n\) 的字符串，有长度为 \(d,(d|n)\) 的循环节与有长为 \(n-d\) 的border等价，判断 border 可以通过 hash 直接判断，所以枚举 \(len\) 的质因子，检查 border 即可
LuoguP3546
容易发现循环同构等价于取一次 border 后，最长不重叠的 border 长度，\(f_i\) 表示去掉两边 i 个字符后的最长不重叠 border 长度，容易发现有 \(f_{i-1}\leq f_i+2\)，由 KMP 的势能分析的那一套可以得知，如果 \(O(1)\) 用 HASH 判断相等的话时间复杂度为 \(O(n)\)，直接跑就可以了