闲话
怎么了的 洛谷不能交太长的代码是吧
经过测试大概码长分界线在 11369 ~ 11381
听 uq 有人说博客太长也不让提交？
而且发现 ABC284 的题已经整一天了都没上
洛谷是不是在作什么大动作？
今日推歌是《ぼくらの16bit戦争(Remaster ver)》sasakure.UK feat.GUMI
推荐博客：多项式 I：拉格朗日插值与快速傅里叶变换, Alex_Wei
拉格朗日插值例题和做法不是拉格朗日插值的题
感觉拉格朗日插值这边的题要么就是求个 \(S_k(n)\)，要么就是看出什么东西可以用多项式表示然后直接插出来系数接着做。
总的来说就是个小工具。
首先需要说明的是，\(f(x) - f(x - 1)\) 是一个关于 \(x\) 的 \(n\) 阶多项式，就表示 \(f(x)\) 是一个关于 \(x\) 的 \(n + 1\) 阶多项式。
简单挑几道题说说。
题面长，不粘。
“恰好”不好求，考虑容斥转化为“至少”。设 \(f_i\) 为至少 \(i\) 人被碾压的方案数。
钦定 \(i\) 个人被碾压，首先选出这些人来。然后对于每一科 \(j\) 我们在没有被钦定的 \(n - i -1\) 人里选择大于 B 神的 \(r_j - 1\) 个人，最后枚举 B 神在这一科的分数，然后每边随意选择。得到
\[f_i = \binom{n}{i} \prod_{j=1}^n \binom{n - i - 1}{r_j - 1} \sum_{k = 1}^{u_j} k^{n - r_i} (u_j - k)^{r_j - 1} \]发现后面那个对 \(k\) 的求和很难直接做，因此需要针对它化简一下。其实做差分后也能看出后面的是个对 \(u_i\) 的 \(n\) 次多项式。推一下：
\[\begin{aligned} & \sum_{k = 1}^{u_j} k^{n - r_i} (u_j - k)^{r_j - 1} \\ = \ & \sum_{k = 1}^{u_j} k^{n - r_i} \sum_{t = 0}^{r_j - 1}\binom{r_j-1}{t} u_j^{r_j - 1 - t} (-k)^{t} \\ = \ & \sum_{t = 0}^{r_j - 1}(-1)^t \binom{r_j-1}{t} u_j^{r_j - 1 - t} \sum_{k = 1}^{u_j} k^{n - r_i + t} \end{aligned}\]好了。然后就没啥了，你直接上一个拉插就能在 \(O(n^2 m)\) 的复杂度内得到每个 \(f_i\)。答案即为
\[\sum_{i=k}^{n-1} (-1)^{i - k} \binom {i}{k} f_i \]\(T\) 组询问，每组询问给定 \(k,a,n,d\)。
定义
\[f(n)=\sum_{i=1}^n i^k\qquad g(n)= \sum_{i=1}^n f(i) \qquad h(n) = \sum_{i=0}^n g(a + id) \]求
\[h(n) \bmod 1234567891 \]的值。
通过差分几次能得到 \(h(n)\) 是一个关于 \(n\) 的 \(k + 3\) 次多项式。
我们能方便的求得 \(f\)，自然可以方便地求得 \(g\) 的前 \(k + 2\) 个点值。自然可以方便地求得答案的前 \(k + 3\) 个点值。
然后一层一层地求即可。
一个长度为 \(n\)、元素值域在 \([1,k]\) 间且各个元素互不相同的序列 \(a\) 对答案的贡献为 \(\prod_{i=1}^n a_i\)。给定 \(k, n_0\) 对每个 \(1\le n \le n_0\)，求所有本质不同的长度为 \(n\) 的序列的权值和对 \(998244353\) 取模的值。
\(1\le n_0 \le 5\times 10^5,\ n_0\le k < 998244353\)。
谁用拉插做这种题啊，又难想复杂度也不优，还不如直接 DP 转生成函数！
我们考虑一个 DP 计算答案。元素互不相同启发我们在值域上做长度相关的 DP，设 \(f_{i, j}\) 为当前决策 \(i\) 选不选，当前计数的序列长度为 \(j\)。考虑当前值 \(i\) 是否选择，容易写出转移方程
\[f_{i, j} = f_{i-1,j} + if_{i-1,j-1} \]然后对第一维求和得到
\[F_i(x) = \sum_{j=0}^{\infty} f_{i, j} x^j = \sum_{j=0}^{\infty} f_{i-1,j} x^j + i\sum_{j=0}^{\infty} f_{i-1,j-1} x^j = F_{i-1}(x) + ixF_{i-1}(x) \]也就是
\[F_{k}(x) = (kx + 1) \times F_{k-1}(x) = \prod_{i=1}^k (ix + 1) \]\(F_0(x) = 1\)。我们需要提取这玩意的第 \(n\) 项系数。容易想到一个 \(\prod\) 的经典套路是 \(\ln + \exp\)，首先作对数。
\[\begin{aligned} & \ln \prod_{i=1}^k (ix + 1) \\ = \ & \sum_{i=1}^k \ln(ix + 1) \\ = \ & \sum_{i=1}^k \int \frac{i}{ix + 1} \text dx \\ = \ & \int \sum_{i=1}^k i(ix + 1)^{-1} \text dx \\ = \ & \int \sum_{i=1}^k i\sum_{t=0}^{\infty} (-i)^t x^t \text dx \\ = \ & \sum_{i=1}^k i\sum_{t=0}^{\infty} (-i)^t \frac{x^{t + 1}}{t + 1} \\ = \ & \sum_{i=1}^k i\sum_{t=1}^{\infty} (-i)^{t - 1} \frac{x^t}{t} \\ = \ & \sum_{t=1}^{\infty} \frac{(-1)^{t + 1}}{t} \sum_{i=1}^k i^t x^t \end{aligned}\]考虑到后面这个东西不是很好刻画，我们可以通过比对系数的方式来转化。具体地，我们考虑对后面的 \(\sum\) 单独构造生成函数，在需要转化回 \(\ln F_k(x)\) 的时候第 \(t\) 项乘入 \((-1)^{t + 1}/t\) 即可。
考虑到这个生成函数的第 \(i\) 项是等比数列求和的形式，我们可以通过 \(e^{px}\) 的 \(\text{EGF}\) 刻画其形式。具体地，我们构造
随后提取 \(x^t / t!\) 即可。带回原式得到
\[\begin{aligned} & \ln \prod_{i=1}^k (ix + 1) \\ = \ & \sum_{t=1}^{\infty} \frac{(-1)^{t + 1}}{t} [x^t / t!] \frac{e^{(k + 1)x} - 1}{e^x - 1} \\ = \ & \sum_{t=1}^{\infty} (-1)^{t + 1}(t-1)! [x^t] \frac{e^{(k + 1)x} - 1}{e^x - 1} \end{aligned}\]我们容易对给定的 \(t\) 构造出 \(e^{tx}\)，随后只需要做一次多项式求逆便可得到 \(G(x)\) 了。由于上下两个多项式的常数均为 \(0\)，因此可以作约分，最终多项式求逆是不受影响的。得到 \(G(x)\) 后转化为 \(\ln F_k(x)\) 是显然的。对结果做 \(\exp\) 后我们就构造出了 \(F_k(x)\)，其前 \(k\) 项即为答案。
总时间复杂度视实现方法而定，为 \(O(n\log n)/O(\frac{n\log^2 n}{\log \log n})\)。半在线卷积真香啊！
对于一个长度为 \(n\)、其中元素取值为 \([1,n]\) 内整数的序列 \(A = (A_1, A_2, \dots, A_n)\)，以及一个整数 \(i(1\le i \le n)\)，我们按如下方式定义一个长度为 \(10^{100}\) 的序列 \(B_i = (B_{i, 1}, B_{i, 2}, \dots, B_{i, 10^{100}})\)：
- \(B_{i, 1} = i\)。
- \(B_{i, j + 1} = A_{B_{i, j}} (1 \le j < 10^{100})\)。
此外，我们定义 \(S_i\) 为 \(B_i\) 中只出现一次的整数的数量。定义一个序列的贡献为 \(\sum_{i=1}^n S_i\)。
给定正整数 \(n, m\)，你需要求出总共 \(n^n\) 种可能的序列的贡献之和模 \(m\) 的值。
\(1\le n \le 2\times 10^5,\ 10^8 \le m\le 10^9\)。
由于答案具有对称性，任意 \(S_i\) 的贡献等于 \(S_1\)，接下来我们只需要讨论 \(S_1\)。下文中简记 \(B_{1, i}\) 为 \(B_i\)。
我们令 \(k\) 为一种可能中满足前 \(i\) 个元素彼此不同的最大的 \(i\)，随后来分别对确定的 \(k\) 计数种类数。
我们已经确定了 \(B_1 = 1\)，这样就需要从 \(n-1\) 个彼此不同的元素中选 \(k-1\) 个，也就有 \(A(n-1, k-1)\) 种可能性。关注 \(B_{k + 1}\)，可以发现其必定与前 \(k\) 个中的一个元素相同。假设 \(B_p = B_{k + 1} (1\le p \le k)\)，则我们可以发现，\(B_p\) 到 \(B_k\) 的子序列定会无限循环下去。
因此，只有 \(B_1\) 到 \(B_{p-1}\) 对应的子序列是只在 \(B\) 中出现一次的序列，对答案的贡献即为 \(p-1\)。对所有可能的子序列贡献求和得到这一部分对答案的贡献 \(\sum_{p=1}^k (p - 1) = p(p-1)/2\)。
现在固定 \(B_1\) 到 \(B_{k + 1}\) 段的序列，考虑有多少 \(A\) 满足当前的条件。由于 \(B_i\) 固定等价于 \(A_{B_{i-1}}\) 被确定，可以发现 \(A_{B_1}, A_{B_2}, \dots, A_{B_k}\) 都是已经确定了的，因此 \(A\) 中没有确定的元素还有 \(n - k\) 个。
因此对 \(k\) 的答案即为
对 \(1\le k\le n\) 求和即可得到 \(S_1\)。总时间复杂度 \(O(n)\)。
标签：infty,le,frac,ix,闲话,sum,23.1,序列 From： https://www.cnblogs.com/joke3579/p/chitchat230108.html