多项式，OI的魅力，OIer的噩梦。
多项式
这个大家应该都会。
对于式子 \(\sum\limits_{i=0}^{k}a_{i}x^i\)，且 \(a_k \ne 0\)，那么我们称它是关于 \(x\) 的 \(k\) 次多项式。\(k\) 为次数。
就是这么简单
生成函数
定义：对于序列 \(a_0,a_1,a_2,a_3,...\)，其生成函数为
\[f(x)=a_{0}+a_{1}x+a_{2}x_{2}+a_{3}x^{3}+... \]举几个例子：
-
若 \(a_{i}=从\ i\ 个球里选出\ 0\ 个球的方案数\)，则有 \(f_1(x)=1+x+x^2+x^3+x^4+...\)；
-
若 \(a_{i}=从\ i\ 个球里选出\ 1\ 个球的方案数\)，则有 \(f_2(x)=0+x+2x^2+3x^3+4x^4+...\)；
-
若 \(a_{i}=i\ 种糖果，每种有无限个，分给\ \text{Alice}\ 和\ \text{Bob}\ 的方案数\)，则有 \(f_3(x)=0+x+2^{2}x^2+3^{2}x^3+4^{2}x^4+...\)。
好了，这就是生成函数的定义。但是现在你肯定会问，这东西有啥用呢？
小学我们就学过，这种有无限项相加的式子可以用“错位相减”之类的办法化成一个有限的表达方式。
那么我们就试试生成函数是否同样可以：
\[\begin{aligned} f_1(x)&=\sum_{i=0}^{\infty}x^i\\ x f_1(x)&=\sum_{i=1}^{\infty}x^i\\ (1-x)f_1(x)&=1\\ \therefore f_1(x)&=\frac{1}{1-x}\\ \\ f_2(x)&=\sum_{i=0}^{\infty}i x^i\\ xf_2(x)&=\sum_{i=0}^{\infty}i x^{i+1}=\sum_{i=1}^{\infty}(i-1)x^i\\ (1-x)f_2(x)&=\sum_{i=0}^{\infty}i x^i - \sum_{i=1}^{\infty}(i-1)x^i=\sum_{i=1}^{\infty}i x^i - \sum_{i=1}^{\infty}(i-1)x^i\\ &= \sum_{i=1}^{\infty}x^i=\sum_{i=0}^{\infty}x^i - 1\\ &= f_1(x)-1 = \frac{1}{1-x} - 1 = \frac{x}{1-x}\\ \therefore f_2(x)&=\frac{x}{(1-x)^2} \end{aligned} \]确实可以。即使它看起来很反常识，但这就是将一个无穷序列“浓缩”起来的表示方式。
类似地，还有\(f_3(x)=\sum\limits_{i=0}^{\infty}i^{2}x^{i}=\frac{x^2+x}{(1-x)^3}\)，请读者自己尝试推导。
顺带一提，无限项的式子可以浓缩，有限也可以。比如可以利用等比数列求和公式把 \(1+x+x^2+x^3+...+x^k\) 写成 \(\frac{1-x^{k+1}}{1-x}\)。
所以到底有啥用
别急嘛，接下来看几个例题你就明白了。
例题 1：有一个多重集 \(A\)，其中值为 \(i\) 的元素有 \(a_i\) 个。还有一个多重集 \(B\)，其中值为 \(i\) 的元素有 \(b_i\) 个。问：多重集 \(C=A\cup B\) 中值为 \(i\) 的有多少个？
显然，是 \(c_i=a_i+b_i\)。算出 \(A\) 和 \(B\) 的生成函数然后两式相加即可。
例题 2：还是刚刚的 \(A\) 和 \(B\)，你可以从两集合内各取一个元素，然后将和扔进 \(C\)。问： \(C\) 中值为 \(i\) 的有多少个？
你想了一下，然后还是很快反应过来了——将两多项式相乘即可。
那如果。。。我想取出 \(k\) 的倍数，或者不超过 \(k\) 个，那么阁下又该如何应对？
例题 3：现在有 \(A,B,C,D\) 四种水果，每种都有无限个。现在要恰好取出 \(n\) 个水果，但水果 \(A\) 必须取偶数个，水果 \(B\) 必须取 \(5\) 的倍数个，水果 \(C\) 最多只能取 \(4\) 个，水果 \(D\) 最多只能取 \(1\) 个。问：方案数是多少？
首先考虑倍数怎么办。\(A\) 必须取 \(2\) 的倍数个，也就是说偶次项系数为 \(1\)，奇次项系数为 \(0\)。即 \(A(x)=0+x^2+x^4+x^6+...\)，不难得出 \(A(x)=\frac{1}{1-x^2}\)。
同理可得 \(B(x)=0+x^5+x^{10}+x^{15}+...=\frac{1}{1-x^5}\)。
此时，一条显然的规律也出来了：\(\sum\limits_{i=0,d|i}^{\infty}x^i=\frac{1}{1-x^d}\)。
然后再考虑「至多」，此时的你应该也能发现，这就是上面说的有限项数的函数。
比如，\(C(x)=1+x+x^2+x^3+x^4\)，利用公式写成 \(\frac{1-x^5}{1-x}\)。
同理，\(D(x)=1+x=\frac{1-x^2}{1-x}\)。
最后总方案数的生成函数就是：
\[A(x)\times B(x)\times C(x)\times D(x)=\frac{1}{1-x^2}\times\frac{1}{1-x^5}\times\frac{1-x^5}{1-x}\times\frac{1-x^2}{1-x}=\frac{1}{(1-x)^2} \]而 \(\frac{1}{(1-x)^2}\) 的意义可以参考例题二，也就是两个集合内都有无限个元素 \(1,2,3,...\)，然后每个集合选一个出来，再求和。
因此你就可以通过它的意义来还原多项式：
\[\frac{1}{(1-x)^2}=1+2x+3x^2+4x^3+... \]解释：\(0=0+0\)，\(1=0+1=1+0\)，\(2=0+2=1+1=2+0\)，\(...\) 。
是不是很神奇？那么复杂的问题，它的答案就是 \(n+1\)！
不信？那你可以随意拿几个数试试哦。
洛谷P2000 拯救世界
不用多说，就是刚刚那题的加强版。建议先手动推一推。
最后你会发现答案是 \(\frac{1}{(1-n)^5}\)，也就是选 \(5\) 个非负整数，使得和为 \(n\) 的方案数。这个东西就是小学学的插板法，\(n\) 个苹果分给 \(5\) 个小朋友，可以有小朋友没有，方案数是 ${n+5-1 \choose 5-1}={n+4 \choose 4}=\frac{(n+1)(n+2)(n+3)(n+4)}{24} $。
别急，再看看数据范围——呃？这题还卡普通高精乘，看来得用 \(\text{NTT}\) qwq。
不过你用 Ruby 写倒也不是不行
拉格朗日插值法
众所周知，在平面直角坐标系中，\(k\) 个横坐标互不相同的点就可以唯一确定一个 \((k-1)\) 次函数。这一点在代码上可以用高斯消元来解决。那么就来看看这个题：洛谷P4781 【模板】拉格朗日插值。
这时候我们看了眼数据范围：
遗憾地发现高斯消元过不去了。
由于这题并不需要解出函数，只需求出 \(f(k)\) 的值，所以就可以引入一个新东西：拉格朗日插值法。
这个方法的思想就是，对每个点 \(i\) 求出一个函数 \(f_i\)，满足将 \(x_i\) 带入可以返回 \(y_i\)，但是将别的 \(x_j\) 带入都会返回 \(0\)。这样一来，把 \(k\) 带入每个函数 \(f_i\)，返回值加起来，就能得到 \(f(k)\)。这是因为你求出了一个函数 \(f(x)=f_1(x)+f_2(x)+...+f_n(x)\)，满足 \(f(x_i)=y_i\)，也就是说 \(f(x)\) 就是原函数。（聪明的你这时也一定发现了，这个思想和中国剩余定理有着异曲同工之妙）
那么问题是如何构造一个「将 \(x_i\) 带入可以返回 \(y_i\)，但是将别的 \(x_j\) 带入都会返回 \(0\)」的函数？很简单：
\[f_i(x)=y_i \prod_{i\ne j} \frac{x-x_j}{x_i-x_j} \]验证一下，发现确实符合我们的要求。那么代码也能很轻松的写出来了。
不过由于这题需要取模，所以需要求逆元。如果模拟上式的计算，时间复杂度是 \(\mathcal{O}(n^2\log p)\)。
观察上式，发现可以每轮单独记录分子之积和分母之积，因此枚举完 \(j\) 再算总分母的逆元即可。时间复杂度 \(\mathcal{O}(n^2+n\log p)\)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5, MOD = 998244353;
int n, k, x[N], y[N], ans;
inline int madd(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }
inline int msub(int x, int y) { return madd(x, MOD - y); }
inline int mmul(int x, int y) { return 1ll * x * y % MOD; }
inline int qpow(int x, int y) { int res = 1, t = x % MOD;
while (y) { if (y & 1) res = mmul(res, t);
t = mmul(t, t); y >>= 1; }
return res; }
inline int mdiv(int x, int y) { return mmul(x, qpow(y, MOD - 2)); }
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
scanf("%d%d", x + i, y + i);
if (k == x[i])
{
cout << y[i] << endl;
return 0;
}
}
for (int i = 1; i <= n; i++)
{
int bdiv = 1, div = 1;
for (int j = 1; j <= n; j++)
if (i != j)
{
bdiv = mmul(bdiv, msub(k, x[j]));
div = mmul(div, msub(x[i], x[j]));
}
ans = madd(ans, mmul(y[i], mdiv(bdiv, div)));
}
cout << ans << endl;
return 0;
}