wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数学

组合计数

二项式定理

生成函数（一）

FFT

多项式与形式幂级数

同余与模

同余与模的应用

同余与模的概念

特殊的数

斯特林数

斯特林数相关的恒等式

斯特林数的综合应用

FFT的应用

整除分块

[[ item.c ]]

FFT的应用

## 一些例子
### Triple Sums
**[TSUM - Triple Sums](https://ac.nowcoder.com/acm/contest/26012/B)**
给定序列$$s_1, s_2, \cdots, s_n$$，对所有可能的取值$$v$$，求满足$$s_i + s_j + s_k = v (i < j < k)$$的三元组$$(i, j, k)$$的数量

**算法分析**
首先$$v$$不会很大，$$[-6e5, 6e5]$$之间，可以考虑枚举$$v$$
如果没有$$i < j < k$$这个限制，考虑令
```math
\displaystyle
S(x) = \sum x^{s_i}, \quad [x^k] S^3(x)
```
就是答案，现在考虑容斥
> 考虑$$i \neq j \neq k$$的方案数

```math
\displaystyle
U = \{ (i, j, k) \mid 1 \leqslant i, j, k \leqslant n \} \\
A = \{ (i, j, k) \mid i = j \} \\
B = \{ (i, j, k) \mid i = k \} \\
C = \{ (i, j, k) \mid j = k \}
```
所求的集合是
```math
f(U - A \cup B \cup C) = f(U) - f(A) - f(B) - f(C) \\
+ f(A \cap B) + f(A \cap C) + f(B \cap C) - f(A \cap B \cap C)
```
因为这里有顺序要求$$i < j < k$$，所以最后要把顺序除去，$$\times \dfrac{1}{3!}$$
注意到$$f(A \cap B), f(A \cap C), f(B \cap C), f(A \cap B \cap C)$$表示的意义是一样的
即$$i = j = k$$，不妨记为$$f_3$$

而$$f(A), f(B), f(C)$$都表示$$i, j, k$$中至少有两个数相等的方案数，记为$$f_2$$
最后的答案是$$f(U) - 3f_2 + 2f_3$$

> 再分别构造生成函数

关于$$f_2$$，实际上是要求$$2s_i + s_k = v$$，构造$$S_2(x) = \sum x^{2s_i}, f_2 = S_2(x)S(x)$$

同理，关于$$f_3$$，实际上是$$3s_i = v$$，令$$S_3(x) = \sum x^{3s_i}$$
```math
\displaystyle
\dfrac{1}{3!} (S^3(x) - 3S_2(x)S(x) + 2S_3(x))
```
> 值得注意的是，这里的$$s_i$$有负数，可以将所有的$$s_i$$**整体平移**$$+|maxv|$$距离

> 最后算出答案之后，$$[x^k]$$应该对应$$x^{k - 3|maxv|}$$

### Fuzzy Search
**[Fuzzy Search](https://ac.nowcoder.com/acm/contest/26012/C)**
给定只有`ATCG`的两个字符串`S, T`，给定非负整数`k`，求有多少$$i$$
满足$$1 \leqslant i \leqslant |S|-|T|+1$$，满足任意的$$j, 1 \leqslant j \leqslant |T|$$
都存在$$p, 1 \leqslant p \leqslant |S|$$使得$$|i+j-1-p| \leqslant k$$并且$$S_p = T_j$$

换句话说，$$T$$在$$S$$中出现，当且仅当把$$T$$的首字符和$$S_i$$**对齐**之后，$$T$$的
**每一个字符**都能够在`S`中找到一个位置偏差不超过`k`的，相同的字符
比如`k = 1, ACAT`可以出现在`AGCAATTCAT`的`i = 2`的位置
（`ACAT`和`GCAATTCAT`对齐，发现`A`和`G`虽然不匹配，但是`A`可以和`G`之前的`A`匹配上）

原来$$T_j$$能够匹配上的位置，如果$$T$$和$$S_i$$对齐的话
原本**期望**的匹配位置是$$S(i+j-1)$$`(1-indexed)`，如果这个位置匹配不上
但是$$T_j$$能和$$S_p$$匹配上，并且$$|i+j-1-p| \leqslant k$$，我们也认为匹配上了

**算法分析**
枚举$$i$$，如果
```math
\displaystyle
\sum_{j = 0}^{|T|-1} [T_j = S_p, \quad |i+j-p| \leqslant k] = |T|
```
那么我们认为$$i$$是满足的
因为字符集很小，只有`A, T, C, G`四种，可以每个字符单独考虑，比如说`A`在$$T$$的哪些位置出现
```math
\displaystyle
f(i, A) = \sum_{j = 0}^{|T|-1}[T_j= \text{'A'}][\text{'A'}=S_p, \quad |i+j-p| \leqslant k]
```
如果$$f(i, A) + f(i, T) + f(i, C) + f(i, G) = |T|$$，那么$$i$$就是合法的

> 问题转化

```bash
S = [x x x A x A x x A]
T = [x x A x]

可以转化，S 中的每一个 A，可以往前往后覆盖 k 个，比如 k = 1
S2 = [x x A A A A A A A]
```
令$$S = S2$$，那么对于**枚举的**$$i$$
```math
\displaystyle
\sum_{j = 0}^{|T|-1} [T_j = \text{'A'} \textbf{ and } S_{i+j} = \text{'A'}] \\
= \sum_{j = 0}^{|T|-1} [T_j = \text{'A'}] \cdot [S_{i+j} = \text{'A'}]
```
在枚举`i`确定`i`的情况下，这是一个**减法卷积**，考虑$$rev(S(x))$$转成加法卷积，构造
```math
\displaystyle
T(x) = \sum_{j = 0}^{|T|-1} [T_j = \text{'A'}]x^j \\
\quad \\
rev(S(x)) = \sum_{i = 0}^{|S|-1} [S_{n-1-i} = \text{'A'}]x^i
```
合法的$$i$$就对应到合法的$$k$$，考虑第$$k$$项，$$x^k$$的系数
```math
\displaystyle
[x^k] ( T(x)\cdot rev(S(x)) ) = [x^k] \left( \sum_{j = 0}^{|T|-1}[T_j = \text{'A'}][rev(S) \text{ 中 }x^{k - j} \text{ 的系数}] \right) \Rightarrow \\
\quad \\
\sum_{j = 0}^{|T|-1}[T_j = \text{'A'}][S_{n-1-k+j} = \text{'A'}]
```
将$$k$$和$$i$$在原来的问题对应起来
那么$$n - 1 - k + j = i + j, \quad k = n - 1 - i$$
```math
\displaystyle
f(i, A) = [x^k] = [x^{n - 1 - i}] T(x)rev(S(x))
```
其中$$T(x)rev(S(x))$$可以预处理，对于$$f(i, T/C/G)$$都是可以类似求出
最后我们`for`一遍每一个位置$$i$$，看一下$$f(i, A) + f(i, T) + f(i, C) + f(i, G) = |T|$$
是否满足就可以了
#### 算法实现
```bash
void solve(int cas) {
    int n, m, K;
    cin >> n >> m >> K;

string s, t;
    cin >> s >> t;

vector<int> ans(n+5, 0);

auto work = [&](string str, string t, char ch) -> void {
 int n = str.size(), m = t.size();
 vector<cd> D(n+1);

for (int i = 0; i < n; i++) {
 if (str[i] != ch) continue;
 int l = max(0, i - K), r = min(i + K, n - 1);
 D[l] += 1.0, D[r+1] -= 1.0;
 }

vector<cd> S(n, 0);
 for (int i = 0; i < n; i++) S[i] = (i - 1 >= 0 ? S[i-1] : 0) + D[i];

for (int i = 0; i < n; i++) if (S[i].real() > 0) S[i] = cd(1.0, 0);
 // debug(S);

vector<cd> T(m);
 for (int i = 0; i < m; i++) T[i] = cd(1.0 * (t[i] == ch), 0);

reverse(S.begin(), S.end());
        Poly Sx(S), Tx(T);

auto res = Sx * Tx;

for (int i = 0; i < n - m + 1; i++) {
 ans[i] += res[n-1-i].real();
 }
 };

work(s, t, 'A');
    work(s, t, 'T');
    work(s, t, 'C');
    work(s, t, 'G');

int cnt = 0;
 for (int i = 0; i < n - m + 1; i++) {
 if (ans[i] == m) cnt += 1;
 }

cout << cnt << "\n";
}
```

## 拉格朗日插值
对于$$n$$个点值$$(x_i, y_i), 1 \leqslant i \leqslant n$$，满足$$x_i \neq x_j (i \neq j)$$
它们可以唯一确定一个$$n - 1$$次多项式$$f(x)$$
```math
\displaystyle
f(x) = \sum_{i = 1}^{n} y_i \prod_{j \neq i} \dfrac{x - x_j}{x_i - x_j}
```
> 证明，和中国剩余定理类似

对于$$(x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n)$$
```math
\displaystyle
f(x) = f_1(x) + f_2(x) + \cdots + f_n(x)
```
构造
```math
\begin{cases}
f_1(x_1) = y_1 \\
f_1(x_2) = 0 \\
\vdots \\
f_1(x_n) = 0
\end{cases}
\begin{cases}
f_2(x_1) = 0 \\
f_2(x_2) = y_2 \\
\vdots \\
f_2(x_n) = 0
\end{cases}
\cdots 
\begin{cases}
f_i(x_1) = 0 \\
\vdots \\
f_i(x_i) = y_i \\
\vdots \\
f_i(x_n) = 0
\end{cases}
\cdots
```
不难发现，$$f_1(x)$$形如
```math
f_1(x) = A(x-x_2)(x-x_3)\cdots (x-x_n) \\
f_1(x_1) = y_1 \\
\quad \\
A = \dfrac{y_1}{(x_1 - x_2)\cdots (x_1 - x_n)}
```
从而
```math
\displaystyle
f(x) = \sum_{i = 1}^{n} \dfrac{y_i}{\prod_{j \neq i} (x_i - x_j)}\prod_{j \neq i}(x - x_j)
```
那么$$\prod (x - x_j)$$有$$n - 1$$个这样的项相乘，所以`deg = n - 1`

### 拉格朗日插值与 CRT
拉格朗日插值，可以看作 CRT 在**多项式环**上的推广
> 回顾 CRT

```math
\displaystyle
\begin{cases}
x \equiv a_1 (\bmod m_1) \\
x \equiv a_2 (\bmod m_2) \\
\vdots \\
x \equiv a_n (\bmod m_n)
\end{cases}
```
从而有形式$$x \equiv ? (\bmod \ m_1m_2\cdots m_n)$$，`?`最后可以通过迭代求出来
推广到多项式环上
```math
\displaystyle
\begin{cases}
f(x) \equiv y_1 (\bmod (x - x_1)) \\
f(x) \equiv y_2 (\bmod (x - x_2)) \\
\vdots \\
f(x) \equiv y_n (\bmod (x - x_n))
\end{cases}
```
那么我们可以求出
```math
\displaystyle
f(x)\equiv ? (\bmod \ (x-x_1)(x-x_2)\cdots (x-x_n) )
```
这里模和互质的概念，都可以在**多项式环上**相应推广
**模和互质**
```math
f(x) - y_i = f(x) - f(x_i) = a_1(x - x_i) + a_2(x^2 - x_i^2) + \cdots + a_k(x^k - x_i^k) + \cdots \\
x^k - x_i^k = (x - x_i)(x^{k-1} + x^{k-2}x_i + \cdots)
```
从而我们有$$f(x) \equiv y_i (\bmod (x - x_i))$$
另外$$f(x) \bmod g(x) = r(x)$$
那么$$f(x) = q(x)g(x) + r(x), \ deg (r(x)) < deg (g(x))$$，记为$$f(x) \equiv r(x) (\bmod g(x))$$

**多项式互质**
相当于$$(A(x), B(x))$$**的公因子只有常数项**

### 多项式快速插值
根据拉格朗日插值公式
```math
\displaystyle
f(x) = \sum_{i = 1}^{n}\dfrac{y_i}{\prod_{i \neq j} x_i - x_j} \prod_{i \neq j} (x - x_j)
```
首先来看系数
```math
\displaystyle
\dfrac{y_i}{\prod_{j \neq i} x_i - x_j}
```
分子是一个常数，只需要考虑分母，分母实际上是若干多项式的相乘
令$$\displaystyle g(x) = \prod\_{i=1}^n (x - x\_i)$$，那么分母可以写成$$\dfrac{g(x\_i)}{(x - x\_i)}$$

根据**洛必达法则**
```math
\displaystyle
\lim_{x \to a} \dfrac{f(x)}{g(x)} = \lim_{x \to a} \dfrac{f'(x)}{g'(x)}
```
分母就是$$g^{\prime}(x_i)$$，对于$$i$$来说，系数就是$$\dfrac{y_i}{g^{\prime}(x_i)}$$

> 接下来就考虑**线段树分治**

不妨设$$f\_{l, r}$$表示$$[(x\_l, y\_l), (x\_{l+1}, y\_{l+1}), \cdots, (x\_r, y\_r)]$$这些点算出来的答案
（因为表达式的形式，是一段区间的数都乘起来，可以线段树分治维护）
```math
\displaystyle
f_{l, r} = \sum_{i = l}^{r} \dfrac{y_i}{g'(x_i)} \prod_{j \neq i, j = l}^{r} (x - x_j) \\
\quad \\
= \prod_{j = mid+1}^{r} (x - x_j) \left( \sum_{i = l}^{mid} \dfrac{y_i}{g'(x_i)} \prod_{j=l, j \neq i}^{mid}(x - x_j) \right) + \prod_{j = l}^{mid}(x - x_j) \left(\sum_{i = mid+1}^{r} \dfrac{y_i}{g'(x_i)} \prod_{j = mid+1, j \neq i}^r (x - x_j) \right) \\
\quad \\
= \prod_{j = mid+1}^{r} (x - x_j) f_{l, mid} + \prod_{j = l}^{mid}(x - x_j)f_{mid+1, r}
```
其中$$\prod(x - x_j)$$可以预处理，实际上是多项式`(-x[j], 1)`的相乘

### 算法实现
```bash
// lagrange interpolate
template<int P = 998244353>
Poly interpolate(const std::vector<Mint > &X, const std::vector<Mint > &Y) {
 // X need to be diffrent!
 using mint = Mint;
 int n = X.size();

if (n == 0) return Poly();
 if ((int)Y.size() != n) {
 throw std::invalid_argument("x and y size mismatch");
 }
 if (n == 1) return Poly { Y[0] };

// build product tree, q[p] = prod[l, r]: (x - xj)
 std::vector<Poly > q(4 * n);
 std::function<void(int, int, int)> build = [&](int p, int l, int r) {
 if (r - l == 1) {
 // (1*x - x[l]): 
 q[p] = Poly{ -X[l], mint(1) };
 }
 else {
 int mid = (l + r) >> 1;
 build(p<<1, l, mid);
 build(p<<1|1, mid, r);

q[p] = q[p<<1] * q[p<<1|1];
 }
 };
 build(1, 0, n);

// Q(x) / prod(x - xj) -> L'Hospital
 // then Q'(xi)
 Poly dq = q[1].deriv();
 auto dqvals = dq.eval(X);

// coef, c[i] = yi / Q'(xi)
 std::vector<mint> c(n);
 for (int i = 0; i < n; i++) {
 c[i] = Y[i] / dqvals[i];
 }

// combine coef, res[p] = res[l] * Q[r] + res[r] * Q[l]
 std::function<Poly(int, int, int)> solve = [&](int p, int l, int r) -> Poly {
 if (r - l == 1) {
 return Poly{ c[l] };
 }
 else {
 int mid = (l + r) >> 1;
 Poly L = solve(p<<1, l, mid);
 Poly R = solve(p<<1|1, mid, r);

return L * q[p<<1|1] + R * q[p<<1];
 }
 };

Poly res = solve(1, 0, n);
 res.resize(n);
 return res;
}
```

## 一些例子
### The Sum of the k-th Powers
**[The Sum of the k-th Powers](https://ac.nowcoder.com/acm/contest/26012/D)**
求
```math
\displaystyle
\left(\sum_{i = 1}^{n} i^k \right) (\bmod 10^9 + 7)
```
注意`n`很大，$$10^9$$，但是$$k \leqslant 10^6$$

**算法分析**
根据斯特林数
```math
\displaystyle
f(n) = \sum_{j = 0}^k {k \brace j} \dfrac{(n+1)^{\underline{j+1}}}{j+1}
```
如果直接做，求第二类斯特林数，需要的复杂度是$$O(k^2)$$的
但注意到，$$f(n)$$是一个关于`n`的$$k+1$$次多项式，可以用$$k+2$$个点的**拉格朗日插值**来求解
递推求解$$Y = \\{ f(0), f(1), \cdots, f(k+1) \\}$$，其中每一个值都可以快速幂求出
然后代入插值即可

只不过，这里的插值不需要求出整个多项式，只需要知道系数即可
```math
\displaystyle
f(n) = \sum_{i = 0}^{k+1} y_i \cdot \dfrac{ \prod_{j \neq i}(n - j) }{ \prod_{j \neq i}(i - j) }
```
特别地，这里令$$m = k+1$$
来看分母，实际上分母由两部分组成，对于确定的$$i$$来说，$$\prod\_{j = 0}^{i-1}(i - j) = i!$$
而$$\prod\_{j = i+1}^m(i-j) = (-1)(-2)\cdots (i-m) = (-1)^{m-i} (m - i)!$$
所以分母$$(-1)^{m-i} (m - i)! \cdot i!$$

分子呢？考虑$$\prod\_{j = 0}^{i-1} (n - j) \cdot \prod\_{j = i+1}^{m} (n - j)$$
这是一个前缀乘积和后缀乘积，可以预处理

```bash
// 根据拉格朗日插值，单点求值
mint lagrange_eval(const std::vector<mint> &Y, int x) {
 // calc f(x), 点的个数 pts = m + 1 个
 int pts = Y.size();
 // 最大下标，多项式次数是 m
 int m = pts - 1;
 
 if (0 <= x and x <= m) return Y[x];

comb.init(m+5);

vector<mint> pre(m+2), suf(m+2);

pre[0] = mint(1);
 for (int i = 0; i <= m; i++) {
 pre[i+1] = pre[i] * mint(x - i);
 }

suf[m+1] = mint(1);
    for (int i = m; i >= 0; i--) {
        suf[i] = suf[i+1] * mint(x - i);
    }

mint S = 0;
 for (int i = 0; i <= m; i++) {
 mint yi = Y[i];

mint P = pre[i] * suf[i+1];
        mint Q = comb.invfac(i) * comb.invfac(m - i);
        mint sgn = ((m - i) % 2 == 0 ? 1 : mint(-1));
        S += yi * P * Q * sgn;
    }
    return S;
}
```

### 2019 南昌邀请赛
**[B.Polynomial](https://ac.nowcoder.com/acm/contest/26012/E)**

定义$$n$$次多项式$$f(x)$$，给定$$f(0), f(1), \cdots, f(n)$$，求`m`个询问

每个询问给定$$l, r$$，求$$\sum\_{i = l}^{r} f(i) \bmod 9999991$$

**算法分析**
不难想到，所求的值相当于$$S(r) - S(l-1)$$，定义$$S(x) = f(1) + f(2) + \cdots + f(x)$$

> 注意到$$f(x)$$是一个关于$$x$$的$$n$$次多项式，那么$$S(x)$$就是关于$$x$$的$$n+1$$次多项式

也就是说，确定$$S(x)$$，需要$$n+2$$个点的插值
而我们已经有了$$f(1), f(2), \cdots, f(n)$$，可以用拉格朗日插值，求出$$f(n+1)$$

然后根据$$S$$的递推，我们又可以得到$$n+2$$个点
分别是$$S(0), S(1), \cdots, S(n+1)$$

这样每次询问，都可以$$O(n)$$的复杂度，用**插值的方法**得到特定的点值$$S(R), S(L-1)$$
这样就做完了

### Assigning Prizes
**[Assigning Prizes](https://ac.nowcoder.com/acm/contest/26012/F)**
给定一个正整数序列$$p_1, p_2, \cdots p_n$$和正整数$$R$$，问有多少个正整数列满足
```math
\displaystyle
p_i \leqslant a_i \leqslant R \textbf{ and } \\
a_1 \geqslant a_2 \geqslant \cdots \geqslant a_n
```
答案对$$10^9 + 7$$取模

#### 重要的算法思想回顾

**[算法思想回顾1 - AGC041 D](https://www.ringalgo.com/article/58/)**
**[算法思想回顾2 - 牛客周赛81 E建筑入门](https://www.ringalgo.com/article/54/)**

> 对于问题1，怎么构造 $$a_1 \leqslant a_2 \leqslant \cdots \leqslant a_k$$
可以考虑一开始令$$a_1 = a_2 = \cdots = a_k = x$$，然后呢，操作若干次，每一次减去一个前缀
每次操作减去前缀的长度，保证$$\leqslant$$递增

> 另外问题1的限制是任意$$k+1$$个数的和，都会**严格大于**任意的$$k$$个数的和
那么我们转化为最小的$$k+1$$个数的和，严格大于最大的$$k$$个数的和
即$$a\_1 + a\_2 + \cdots + a\_{k+1} > a\_{n-k+1} + \cdots + a_n $$，要满足$$n-k+1 \geqslant k+2$$
也就是说，$$k \leqslant \lfloor (n-1)/2 \rfloor$$

> 这样，每一次操作我们需要减去一个前缀，并且前缀的长度是单调递增的，考虑 dp，同时考虑每个前缀减或者不减
状态原来设计成$$dp(i, pre, suf)$$，表示考虑前缀$$i$$，最小的`k+1`个数的和是`pre`
最大的`k`个数的和是`suf`，但如果这样设计状态会退化到$$O(n^3)$$
所以转化成$$dp(i, d), d = pre - suf > 0$$，这样就可以考虑去转移了

> 一开始的时候都放`n`，那么`d = (k+1 个 n) - (k 个 n) = n, dp[n] = 1`
对于前缀$$i \leqslant (k+1 = \lfloor (n-1)/2 \rfloor + 1 = (n+1)/2 )$$
原先的$$d = a - b$$，减完之后的$$d' = (a - i) - b = (a - b) - i = d - i$$，所以$$w_i = i$$

> 而对于前缀$$i > (n+1)/2$$呢？原先的$$d = (a-b)$$
减完之后，$$d' = (a - (n+1)/2) - (b - (i - (n+1)/2)) = d - (n+1-i)$$，所以$$w_i = n + 1 - i$$

> 分析完之后，就可以背包了，枚举`i`，然后$$\forall d = n \to 1, \quad dp(d - w_i) += dp(d)$$

> 另外注意，这里选前缀，实际上是**完全背包**，如果选可以选多次，如果用`i`表示阶段
```bash
不选前缀 i，dp(i, d) <-- dp(i-1, d)
选了前缀 i，因为可以选多次，转移不会跳阶段，还是在 i 阶段，dp(i, d-w[i]) <-- dp(i, d)
```

接着考虑第二个问题
> 第二个问题也是类似的，先构造出满足条件的最基本的`base`，然后看还**缺了多少**
假设说是`rest`，一开始所有的增量都是`0`
然后我们每一次选一个后缀$$[j\cdots n]$$，这个后缀所有数都$$+1$$
只不过这个后缀是“立体的”，对于$$i$$位置，实际上应该增加$$+ 1 \cdot i$$
也就是说，$$j$$这个物体的重量是$$w_j = j + (j+1) + \cdots + n$$

> 然后 dp 的过程就考虑完全背包，对于后缀$$[j\cdots n]$$（当然`j`必须单调递增考虑）
考虑选或者不选，`dp(j) += dp(j - cost)`

#### 算法设计
考虑 dp，不难想到这样设计 dp 状态
```bash
for i = n downto 1
	dp(i, x) = (a[i] = x 的方案数)，其中 a[i+1, n] 已经确定下来了
	而 p[i] <= x <= R
```
转移方程比较好写
```math
\displaystyle
dp(i, x) = \sum_{j = p_{i+1}}^{x} dp(i+1, j)
```
另外，$$dp(n, x) = 1, \quad \forall x:\ p_n \leqslant x \leqslant R$$
还有，序列从$$n \to 1$$是单调递增的，所以下界$$p_i$$应该取**后缀最大值**

> 如果$$p_i, R$$都比较小的话，是可以直接`dp`的，但是这里他们的范围都是$$10^9$$
但是呢，$$n$$又比较小，表达式$$ndp = \sum dp$$，符合前缀和的形式
可以考虑做`n`个点的插值，然后代入求解$$dp(R), dp(p_i)$$之类的

```math
\displaystyle
f(n, x) = 1, \quad p_n \leqslant x \leqslant R, \quad \text{关于 x 的 0 次多项式}, deg(x) = 0 \\
f(n-1, x) = f(n, p_n) + f(n, p_n+1) + \cdots + f(n, x) = F(x), \quad \text{关于 x 的 1 次多项式}, deg(x) = 1 \\
f(n-2, x) = \sum_{j = p_{n-1}}^{x} f(n-1, j), \quad deg(x) = 2 \\
\vdots \\
f(0, R), \quad deg(x) = n
```

> 再看 dp 状态转移方程

在第$$i$$阶段，有$$f(i+1, x) = \sum\_{j = p\_i}^{x} f(i, j)$$

如果用滚动数组来表示$$\displaystyle ndp(x) = \sum\_{j = p\_i}^{x} dp(j)$$
考虑$$dp(j)$$是一个$$n - i$$次多项式，那么$$ndp$$是一个$$n - i + 1$$次多项式
可以用拉格朗日插值来求出具体的 dp 值
（值得注意的是，拉插中的 dp 不一定有意义，我们只是有插值来确定多项式的系数）

1）对于$$dp(j)$$，求一遍前缀和$$sdp$$，最多就是$$n$$次多项式，需要$$n+1$$个点
所以实际上，$$dp, sdp$$数组的大小开$$n+1$$即可

2）关于$$sdp$$，它构成一个`n-i+1`次多项式，上一步的前缀和我们可以确定
`sdp(0), sdp(1), sdp(2), ....., sdp(n-i+1)`这`n-i+2`个**点值**，恰好可以把$$sdp$$对应的多项式确定下来
从而可以用**插值**的方法，得到$$sdp(x), sdp(p_i - 1)$$的值

3）真正的`ndp`值，是$$\sum\_{j = p\_i}^{x} dp(j)$$，这实际上是$$sdp(x) - sdp(p\_i - 1)$$
此时**`for x = 0 to n`**，计算出真正的$$ndp[x]$$

注意，这里算出来的`ndp[x]`不一定有意义，比如`ndp[x] = sdp[x] - sdp[pi - 1] < 0`
但没有关系，我们只是用来**做插值**，只需要**保证这些点值在对应的多项式上**就可以
我们是用它来确定系数的，用插值来辅助，最后求具体的，有意义的`dp`值的时候，用相应的$$x$$代进去求即可

这里的$$x$$可能会很大，但是插值方法可以通过确定多项式系数，直接求出$$dp(x)$$

4）最后我们已经知道在$$i = 0$$处，整个过程迭代完之后的`dp[0...n]`的值了
那么就可以用这些点值，插值求出$$dp(R)$$

#### 算法实现
```bash
void solve(int cas) {
    int n, R;
    cin >> n >> R;

vector<int> l(n+1, 0);
 for (int i = 1; i <= n; i++) cin >> l[i];

for (int i = n-1; i >= 1; i--) l[i] = max(l[i], l[i+1]);

vector<mint> dp(n+1, 1), ndp(n+1, 1);

for (int i = n; i >= 1; i--) {
 auto sdp = dp;
 for (int j = 0; j + 1 <= n; j++) sdp[j+1] += sdp[j];

auto lo = lagrange_eval(vector<mint>(sdp.begin(), sdp.begin() + n-i+1 + 1), l[i] - 1);

for (int x = 0; x <= n; x++) {
 ndp[x] = sdp[x] - lo;
 }

dp = ndp;
    }

auto ans = lagrange_eval(vector<mint>(dp.begin(), dp.end()), R);
 cout << ans << "\n";
}
```

看完文章有啥想法

算法小站

wiki 主题

数学

FFT的应用

目录