题目传送门：一元三次方程求解

盛金公式

$part\mathtt{\text{1.}}$ 基本概念

• 根：方程的解。

• 实根：指方程式的解为实数解。实数包括正数，负数和 $0$。

$part\mathtt{\text{2.}}$ 一元三次方程的一般形式

$$a{x}^3+b{x}^2+cx+d=0(a\ne 0).$$

$part\mathtt{\text{3.}}$ 一元三次方程的实根

令 $x=y-{\displaystyle \frac{b}{3a}}$，则

$$a{(y-{\displaystyle \frac{b}{3a}})}^3+b{(y-{\displaystyle \frac{b}{3a}})}^2+c(y-{\displaystyle \frac{b}{3a}})+d=0$$

$$a(y^3-{\displaystyle \frac{b{y}^2}{a}}+{\displaystyle \frac{b^{2}y}{3a^2}}-{\displaystyle \frac{b^3}{27a^3}})+b(y^2-{\displaystyle \frac{2by}{3a}}+{\displaystyle \frac{b^2}{9a^2}})+c(y-{\displaystyle \frac{b}{3a}})+d=0$$

$$a{y}^3-b{y}^2+{\displaystyle \frac{b^2}{3a}}y-{\displaystyle \frac{b^3}{27a^2}}+b{y}^2-{\displaystyle \frac{2b^2}{3a}}y+{\displaystyle \frac{b^3}{9a^2}}+cy-{\displaystyle \frac{bc}{3a}}+d=0$$

$$a{y}^3+(c-{\displaystyle \frac{b^2}{3a}})y+(d+{\displaystyle \frac{2b^3}{27a^2}}-{\displaystyle \frac{bc}{3a}})=0$$

$$y^3+({\displaystyle \frac{c}{a}}-{\displaystyle \frac{b^2}{3a^2}})y+({\displaystyle \frac{d}{a}}+{\displaystyle \frac{2b^3}{27a^3}}-{\displaystyle \frac{bc}{3a^2}})=0$$

令 $p={\displaystyle \frac{c}{3a}}-{\displaystyle \frac{b^2}{9a^2}}$，$q={\displaystyle \frac{d}{2a}}+{\displaystyle \frac{b^3}{27a^3}}-{\displaystyle \frac{bc}{6a^2}}$，则

$$y^3+3py+2q=0$$

令 $\mathrm{\Delta }=q^2+p^3$，则

$\left(1\right)$ 当 $\mathrm{\Delta }>0$ 时，方程只有一个实根：

$$y=\sqrt[3]{-q+\sqrt{\mathrm{\Delta }}}+\sqrt[3]{-q-\sqrt{\mathrm{\Delta }}}$$

$\left(2\right)$ 当 $\mathrm{\Delta }=0$ 时，方程有三个实根，其中至少有两个相等的实根：

$$y_1=-2\sqrt[3]{q}$$

$$y_2=y_3=\sqrt[3]{q}$$

$\left(3\right)$ 当 $\mathrm{\Delta }<0$ 时，方程有三个不等实根：

$$令 $\alpha ={\displaystyle \frac{1}{3}}\arccos {\displaystyle \frac{-q\sqrt{-p}}{p^2}}$，则

$$y_1=2\sqrt{-p}\cos \alpha$$

$$y_2=2\sqrt{-p}\cos (\alpha +{120}^{\circ })$$

$$y_3=2\sqrt{-p}\cos (\alpha +{240}^{\circ })$$

$part\mathtt{\text{4.}}$ 代码实现

// 除一元三次方程外，附上一元一次方程与一元二次方程的实根求解代码
#include <bits/stdc++.h>
using namespace std;
// #define int long long

const double PIE = 3.1415926535897932384626433832795;
static double SolveCubicRoot(double value); // 立方根
static void SolveLinearEquation(double a, double b); // 一元一次方程
static void SolveQuadraticEquation(double a, double b, double c); // 一元二次方程
static void SolveCubicEquation(double a, double b, double c, double d); // 一元三次方程

int op;
double A, B, C, D;
vector<double> root;

// 求一个实数的立方根
double SolveCubicRoot(double value) {
    return value > 0 ? pow(value, 1.0 / 3) : -pow(-value, 1.0 / 3);
}

// 求一元一次方程的实根
void SolveLinearEquation(double a, double b) {
    if (a != 0) // 判断一次项系数是否为零
        root.push_back(-b / a);
    return;
}

// 求一元二次方程的实根
void SolveQuadraticEquation(double a, double b, double c) {
    if (a == 0) { // 判断二次项系数是否为零
        SolveLinearEquation(b, c);
        return;
    }
    double delta = b * b - 4 * a * c; // 判别式
    if (delta > 0) { // 方程有两个不等的实根
        root.push_back((-b + sqrt(delta)) / (2 * a));
        root.push_back((-b - sqrt(delta)) / (2 * a));
    } else if (delta == 0) // 方程有两个相等的实根
        root.push_back(-b / (2 * a));
    return;
}

// 求一元三次方程的实根
void SolveCubicEquation(double a, double b, double c, double d) {
    if (a == 0) { // 判断三次项系数是否为零
        SolveQuadraticEquation(b, c, d);
        return;
    }
    double p = (c / a - b * b / (3 * a * a)) / 3;
    double q = (d / a + 2 * b * b * b / (27 * a * a * a) - b * c / (3 * a * a)) / 2;
    double diff = -b / (3 * a);
    double delta = p * p * p + q * q; // 判别式
    if (delta > 0) { // 方程只有一个实根
        double sqrtDelta = sqrt(delta);
        root.push_back(SolveCubicRoot(-q + sqrtDelta) + SolveCubicRoot(-q - sqrtDelta));
    } else if (delta < 0) { // 方程有三个不等的实根
        double angle = acos(-q * sqrt(-p) / (p * p)) / 3;
        root.push_back(2.0 * sqrt(-p) * cos(angle));
        root.push_back(2.0 * sqrt(-p) * cos(angle + 2 * PIE / 3));
        root.push_back(2.0 * sqrt(-p) * cos(angle + 4 * PIE / 3));
    } else { // 方程有三个实根，其中至少有两个相等的实根
        if (q == 0) root.push_back(0);
        else {
            root.push_back(SolveCubicRoot(q));
            root.push_back(-2 * SolveCubicRoot(q));
        }
    }
    for (int i = 0, maxSize = root.size(); i < maxSize; ++i)
        root[i] += diff; // 将结果加上余量
    return;
}

// 排序并打印结果
void print() {
    priority_queue<double, vector<double>, greater<double> > q;
    int cnt = 0;
    for (auto i : root) {
        q.push(i);
        cnt++;
    }
    while (cnt--) {
        cout << fixed << setprecision(2) << q.top() << " ";
        // 保留两位小数，也可以用 printf 的 %.2f
        q.pop(); // 记住一定要 pop
    }
    cout << "\n";
}

signed main() {
    cin >> op;
    if (op == 1) { // 一元一次方程
        cin >> A >> B;
        SolveLinearEquation(A, B);
        print();
    } else if (op == 2) { // 一元二次方程
        cin >> A >> B >> C;
        SolveQuadraticEquation(A, B, C);
        print();
    } else { // 一元三次方程
        cin >> A >> B >> C >> D;
        SolveCubicEquation(A, B, C, D);
        print();
    }
    return 0;
}

正解提交结果

代码不是题目的正解，会有小改动，学习后自己敲哦

PS: 如有错误请在聊天区 @ 我哦

动态规划概念

• 动态规划主要用来解决多阶段决策过程中的最优化问题，把多阶段过程转化为一系列子问题，不同的子问题通常具有公共的子子问题，即不同的子问题互相重叠。

• 动态规划通常对每个子子问题只求解一次，将其求解结果保存起来，无需每次求解一个子子问题时都重新计算。

• 如 $01$ 背包问题，对于 $i_1$ 个物体、容量是 $j_1$ 的背包来说，能取得的最大价值记为子问题 $1$；对于 $i_2$ 个物体、容量是 $j_2$ 的背包来说，能取得的最大价值记为子问题 $2$。两个子问题可能都会涉及到对于 $i_0$ 个物体、容量是 $j_0$ 的背包来说能取得的最大价值（子问题 $0$）。所以在求解子问题 $2$ 时，由于子问题 $1$ 中已经包含了子问题 $0$，从而可以避免子问题 $0$ 的重复计算。

动态规划解题过程

1. 刻画一个最优解的结构特征 —— 设计状态；
2. 定义最优解的值 —— 推导状态转移方程；
3. 计算最优解的值 —— 记忆化搜索或递推；
4. 利用计算出的信息构造最优解。

  例如，在求解最长上升子序列长度的问题中，朴素的想法是对于长度为 $i$ 的序列，其解如何来求。在推导状态转移的过程中，发现还需要知道上升序列的最后元素，所以需要返回来设计、修改状态 $f_i$，来表示以 $a_i$ 结尾的最长上升子序列的长度，从而得出最优解的值为：$f_i=max(f_j+1)$ $(\ a_j

动态规划适用条件

• 最优子结构。即一个问题的最优解包含其子问题的最优解。如 $01$ 背包问题中的子问题 $1$ 的最优解包含了子问题 $0$ 的最优解，所以才可以用子问题 $1$ 的最优解来求子问题 $2$ 的最优解。

• 重叠子问题。即会反复地求解相同的子问题，而不是一直生成新的子问题。正是利用重叠子问题这个性质，才可以减少不必要的重复计算，从而提高算法的效率。

• 无后效性。即已经求解的子问题不受后续阶段的影响。

常见动规问题

• 从数据结构角度：线性 DP、树形 DP、图上相关的 DP $\dots$

• 从状态设计角度：区间 DP、状态压缩 DP、数位 DP $\dots$

动态规划的优化

• 优化状态描述。如 $01$ 背包问题二维转一维。

• 优化状态计算。前缀和，预处理等。

• 优化决策选择。借助于相关数据结构。如最长不下降序列问题记录当前的最长不下降序列时，用二分选择决策。

• 去除冗余阶段。需要分析每个阶段的性质。

动态规划的应用

【例 $1$】过河问题 $\mathtt{\text{(2021-CSP-J}}$ 第一轮 $\mathtt{\text{T15)}}$

  【题目描述】$N$ 个人要从 $A$ 点坐一条船过河到 $B$ 点，该船一次最多可坐两人。已知每人独自坐船过河的时间，且两个人坐船过河的时间等于船上渡河时间较长的那个人所用的时间。

  【输入格式】 第一行一个整数 $N$ $(N\le {10}^5)$；接下来 $N$ 行，每行一个整数，代表每个人独自过河的时间。

  【输出格式】 一个数，表示所有人都渡过河到 $B$ 点的最少渡河时间。

  【样例输入】

4
1 2 4 8

  【样例输出】

15

  【题目分析】 首先将 $N$ 个人按渡河时间排序，设这 $N$ 个人的渡河时间分别为 $a_1,a_2,\dots ,a_n$。设 $f_i$ 为前 $i$ 个人渡河所需的最小时间，则有两种方案。

  方案一：让渡河最快的人带着最慢的人走，这样返程速度是最快的，即 $f_i=a_1+a_i+f_{i-1}$;

  方案二： 把两个比较慢的放在一起，因为如果把他们分开，会对总时间造成更大的影响，即 $f_i=a_1+2\ast a_2+a_i+f_{i-2}$。

  从而可以得到：

$$f_i=min(a_1+a_i+f_{i-1},a_1+2\ast a_2+a_i+f_{i-2})$$

  【代码片段】

memset(f, 0, sizeof(f));
f[1] = a[1]; f[2] = a[2];
for (int i = 3; i <= n; ++i)
    f[i] = min(a[1] + a[i] + f[i - 1], a[1] + 2 * a[2] + a[i] + f[i - 2]);
printf("%d\n", f[n]);

【例 $2$】方格取数 $\mathtt{\text{(2020-CSP-J}}$ 第二轮 $\mathtt{\text{T4)}}$

  【题目描述】 设有 $n\times m$ 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过方格中的整数，求它能取到的整数之和的最大值。

  【输入格式】 第一行两个整数 $n$，$m$。接下来 $n$ 行，每行 $m$ 个整数，依次代表每个方格中的整数。

  【输出格式】 一个整数，表示小熊能取到的整数之和的最大值。

  【样例输入】

3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1

  【样例输出】

9

  【题目分析】 普通的方格取数问题只有两个方向，用 $f(i,j)$ 表示到格子 $[i,j]$ 能取到的最大值。而在本题中这样表示的话，可以发现就不满足最优子结构的性质，所以需要在普通二维基础上再加一个方向维度，用三维数组进行状态转移，即：

  $f(i,j,0)$ 表示从当前格子的左边走到当前格子能取到的最大整数之和；

  $f(i,j,1)$ 表示从当前格子的上边走到当前格子能取到的最大整数之和；

  $f(i,j,2)$ 表示从当前格子的下边走到当前格子能取到的最大整数之和。

  先进行第 $1$ 列的填值，因为其处在整个地图的最左侧，所以只有从当前格子的上边走到当前格子才可以取到格子里的数的。即： $$f(i,1,1)=f(i-1,1,1)+a(i,1)$$

  然后再进行第 $2$ 到第 $m$ 列的填值，先填向右走到当前格子和向下走到当前格子的值，再从下往上填向上走到当前格子的值。

$$f(i,j,0)=max(f(i,j-1,0),f(i,j-1,1),f(i,j-1,2))+a(i,j)$$

$$f(i,j,1)=max(f(i-1,j,0),f(i-1,j,1))+a(i,j)$$

$$f(i,j,2)=max(f(i+1,j,0),f(i+1,j,2))+a(i,j)$$

  最后答案为: $$max(f(n,m,0),f(n,m,1),f(n,m,2))$$

【例 $3$】上升点阵 $\mathtt{\text{(2022-CSP-J}}$ 第二轮 $\mathtt{\text{T4)}}$

  【题目描述】 在一个二维平面内，给定 $n$ 个整数点 $(x_i,y_i)$，此外你还可以自由添加 $k$ 个整数点。你在自由添加 $k$ 个点后，还需要从 $n+k$ 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 $1$，而且横坐标、纵坐标均单调不减，即 $x_{i+1}-x_i=1,y_{i+1}=y_i$ 或 $y_{i+1}-y_i=1,x_{i+1}=x_i$。请给出满足条件的序列的最大长度。

  【输入格式】 第一行两个正整数 $n$，$k$ 分别表示给定的整点个数、可自由添加的整点个数。接下来 $n$ 行，第 $i$ 行两个正整数 $x_i$，$y_i$ 表示给定的第 $i$ 个点的横纵坐标。

  【输出格式】 一个整数，表示满足要求的序列的最大长度。

  【样例输入】

8 2
3 1
3 2
3 3
3 6
1 2
2 2
5 5
5 3

  【样例输出】

8

  【题目分析】 对于一维不添加点的上升点列问题，其实就是经典的最长不下降序列问题。同样，对于二维平面上如果不添加点的上升点列问题，也可以借助一维的方法实现，即用 $f_i$ 来表示以第 $i$ 个点结尾的上升点列的最大长度，那么有：$f_i=max(f_j+1)$ $($ 当点 $i$ 和点 $j$ 的欧几里得距离为 $1$ 时 $)$。

  在此基础上，如果可以添加点，那我们可以在 $f_i$ 的状态基础上在加上一维 $k$，即用 $f(i,k)$ 表示以点 $i$ 结尾、添加 $k$ 个点的满足要求的序列的最大长度，那么有

$$f(i,k+d)=max(f(i,k+d),f(j,k)+d)$$

  【代码片段】

int dist(int ax, int bx, int ay, int by) { return abs(ax - bx) + abs(ay - by); }
int main() {
    int n, K, ans = 0, a[maxn];
    scanf("%d %d", &n, &K);
    for (int i = 1; i <= n; ++i) scanf("%d %d", &a[i].x, &a[i].y);
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < n; ++j) {
            for (int k = 0; k <= K; ++k) {
                int d = dist(a[i].x, a[j].x, a[i].y, a[j].y) - 1;
                if (d <= K - k && a[i].x >= a[j].x && a[i].y >= a[j].y && i != j)
                    f[i][k + d] = max(f[i][k + d], f[j][k] + d);
            }
        }
        for (int k = 0; k <= K; ++k) f[i][k] += 1;
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= K; ++j)
            ans = max(ans, f[i][j] + K - j);
    printf("%d\n", ans);
    return 0;
}

【例 $4$】数列 $\mathtt{\text{(2021-NOIP-T2)}}$

  【题目描述】 给定整数 $n$，$m$，$k$ 和一个长度为 $m+1$ 的正整数数组 $v_0,v_1,\dots ,v_m$。对于一个长度为 $n$，下标从 $1$ 开始且每个元素均不超过 $m$ 的非负整数序列 $\{a_i\}$，我们定义它的权值为 $v_{a_1}\times v_{a_2}\times \cdots \times v_{a_n}$。当这样的序列 $\{a_i\}$ 满足整数 $S=2^{a_1}+2^{a_2}+\cdots +2^{a_n}$ 的二进制表示中 $1$ 的个数不超过 $k$ 时，我们认为 $\{a_i\}$ 是一个合法序列。计算所有合法序列 $\{a_i\}$ 的权值和对 $998244353$ 取模的结果。

  【输入格式】 输入第一行是三个整数 $n$，$m$，$k$。第二行 $m+1$ 个整数，分别是 $v_0,v_1,\dots ,v_m$。

  【输出格式】 一行一个整数，表示所有合法序列的权值和对 $998244353$ 取模的结果。

  【样例输入】

5 1 1
2 1

  【样例输出】

40

  【样例解释】 由于 $k=1$，而且由 $n\le S\le n\times 2^m$ 知道 $5\le S\le 10$，合法的 $S$ 只有一种可能：$S=8$，这要求 $a$ 中必须有 $2$ 个 $0$ 和 $3$ 个 $1$，于是有 $(\genfrac{}{}{0ex}{}{5}{2})=10$ 种可能的序列，每种序列的贡献都是 $v_0^2{v}_1^3=4$，权值和为 $10\times 4=40$。

  【数据范围】 对所有测试点保证 $1\le k\le n\le 30$，$0\le m\le 100$，$1\le v_i<998244353$。

  【题目分析】 我们发现，$S$ 的二进制表示位中 $1$ 的数量会涉及进位的问题。由于进位是从低位向高位进行的，所以考虑在 $S$ 中从低位到高位按位 DP（最低位为第 $0$ 位）。

  设计状态 $f(i,j,k,p)$ 表示：讨论了 $S$ 从低到高的前 $i$ 位，已经确定了 $j$ 个序列 $a$ 中的元素，$S$ 从低到高前 $i$ 位中有 $k$ 个 $1$，要向当前讨论位的下一位进位 $p$。因为从上一个状态转移到 $f(i,j,k,p)$ 细节太多，所以考虑用 $f(i,j,k,p)$ 往后转移。

  接下来讨论第 $i$ 位（位从 $0$ 开始编号）。假设序列 $a$ 中有 $t$ 个元素为 $i$，那么就相当于给 $S$ 的第 $i$ 位贡献了 $t$ 个 $1$，再加上上一位进过来的 $p$ 个 $1$，总共有 $t+p$ 个 $1$。因为当前位每两个 $1$ 可以向下一位进一个 $1$，所以 $(t+p)mod2$ 的结果即为全部进位后当前位是否为 $1$。同理，向下一位进的 $1$ 的个数即为 $\lfloor {\displaystyle \frac{t+p}{2}}\rfloor$。所以 $f(i,j,k,p)$ 往后转移的状态应该是

$$f(i+1,j+t,k+(t+p)mod2,\lfloor \frac{t+p}{2}\rfloor )$$

  由于乘积之和的形式满足乘法分配律，所以不难想到 $f(i,j,k,p)$ 对新状态的贡献应该是

$$f(i,j,k,p)\times v_i^t\times (\genfrac{}{}{0ex}{}{n-j}{t})$$

  初始化 $f(0,0,0,0)=1$。统计答案：对于 $i$ 这一维，由于 $a_i\in [0,m]$，所以 $S$ 只用看总共 $m+1$ 位，所以是 $m+1$；对于 $j$ 这一维，最终 $n$ 个元素都要确定，所以是 $n$；对于 $k$ 这一维，应该是在 $0\sim k$ 之间的（后面这个 $k$ 是输入的 $k$）；$p$ 这一维就随便了。

  细节：在 $S$ 的第 $m$ 位有可能还要往后面进位，所以可以使用一个 $\mathrm{popcnt}(p)$ 的函数快速统计出进完位后第 $m$ 位往后的 $1$ 的个数，再加上 $k$ 这一维的数量，如果小于等于输入的 $k$，就可以统计进答案。$\mathrm{popcnt}$ 函数很简单，就是一直 res += x & 1, x >>= 1。并且注意要预处理每个 $v$ 的幂次方结果与组合数，代码过程中的取模问题等。

  时间复杂度时间复杂度为 $\mathcal{O}(n^{4}m)$。

  【代码片段】

f[0][0][0][0] = 1;
for (int i = 0; i <= m; i++)
    for (int j = 0; j <= n; j++)
        for (int k = 0; k <= K; k++)
            for (int p = 0; p <= n >> 1; p++)
                for (int t = 0; t <= n - j; t++) {
                    int res = f[i][j][k][p] * pv[i][t] % mod * C[n - j][t] % mod;
                    f[i + 1][j + t][k + (t + p & 1)][t + p >> 1] += res;
                    f[i + 1][j + t][k + (t + p & 1)][t + p >> 1] %= mod;
                }
for (int k = 0; k <= K; k++)
    for (int p = 0; p <= n >> 1; p++)
        if (k + popcnt(p) <= K)
            ans = (ans + f[m + 1][n][k][p]) % mod;
printf("%lld\n", ans);

【例 $5$】$\mathtt{\text{Emiya}}$ 家今天的饭 $\mathtt{\text{(2019-CSP-S}}$ 第二轮 $\mathtt{\text{DAY2-T1)}}$

  【题目描述】$\mathtt{\text{Emiya}}$ 是个擅长做菜的高中生，他共掌握 $n$ 种烹饪方法，且会使用 $m$ 种主要食材做菜。为了方便叙述，我们对烹饪方法从 $1\sim n$ 编号，对主要食材从 $1\sim m$ 编号。

  $\mathtt{\text{Emiya}}$ 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地，$\mathtt{\text{Emiya}}$ 会做 $a(i,j)$ 道不同的使用烹饪方法 $i$ 和主要食材 $j$ 的菜（$1\le i\le n,1\le j\le m$），这也意味着 $\mathtt{\text{Emiya}}$ 总共会做 $\sum _{i=1}^n\sum _{j=1}^{m}a(i,j)$ 道不同的菜。

  $\mathtt{\text{Emiya}}$ 今天要准备一桌饭招待 $\mathtt{\text{Yazid}}$ 和 $\mathtt{\text{Rin}}$ 这对好朋友，然而三个人对菜的搭配有不同的要求，更具体地，对于一种包含 $k$ 道菜的搭配方案而言：

• $\mathtt{\text{Emiya}}$ 不会让大家饿肚子，所以将做至少一道菜，即 $k\ge 1$；

• $\mathtt{\text{Rin}}$ 希望品尝不同烹饪方法做出的菜，因此她要求每道菜的烹饪方法互不相同；

• $\mathtt{\text{Yazid}}$ 不希望品尝太多同一食材做出的菜，因此他要求每种主要食材至多在一半的菜（即 $\lfloor \frac{k}{2}\rfloor$ 道菜）中被使用。

  这里的 $\lfloor x\rfloor$ 为下取整函数，表示不超过 $x$ 的最大整数。

  这些要求难不倒 $\mathtt{\text{Emiya}}$，但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同，当且仅当存在至少一道菜在一种方案中出现，而不在另一种方案中出现。

  $\mathtt{\text{Emiya}}$ 找到了你，请你帮他计算，你只需要告诉他符合所有要求的搭配方案数对质数 $998244353$ 取模的结果。

  【输入格式】 第 $1$ 行两个用单个空格隔开的整数 $n$，$m$。第 $2$ 行至第 $n+1$ 行，每行 $m$ 个用单个空格隔开的整数，其中第 $i+1$ 行的 $m$ 个数依次为 $a(i,1),a(i,2),\cdots ,a(i,m)$。

  【输出格式】 一行一个整数，表示所求方案数对 $998244353$ 取模的结果。

  【样例输入】

2 3 
1 0 1
0 1 1

  【样例输出】

3

  【样例解释】 由于在这个样例中，对于每组 $i$，$j$，$\mathtt{\text{Emiya}}$ 都最多只会做一道菜，因此我们直接通过给出烹饪方法、主要食材的编号来描述一道菜。

  符合要求的方案包括：

• 做一道用烹饪方法为 $1$、主要食材为 $1$ 的菜和一道用烹饪方法为 $2$、主要食材为 $2$ 的菜；

• 做一道用烹饪方法为 $1$、主要食材为 $1$ 的菜和一道用烹饪方法为 $2$、主要食材为 $3$ 的菜;

• 做一道用烹饪方法为 $1$、主要食材为 $3$ 的菜和一道用烹饪方法为 $2$、主要食材为 $2$ 的菜。

  因此输出结果为 $3mod998244353=3$。需要注意的是，所有只包含一道菜的方案都是不符合要求的，因为唯一的主要食材在超过一半的菜中出现，这不满足 $\mathtt{\text{Yazid}}$ 的要求。

  【数据范围】 对于所有测试点，保证 $1\le n\le 100$，$1\le m\le 2000$，$0\le a(i,j)<998244353$。

  【题目分析】 首先考虑列的限制，发现若有不合法的列，则必然有且只有一列是不合法的：因为不可能有不同的两列数量都超过总数的一半。于是发现列的限制容易容斥计算：每行选不超过一个的方案数 减 每行选不超过一个、且某一列选了超过一半的方案数。

  考虑列的限制，发现若有不合法的列，则必然有且只有一列是不合法的：因为不可能有不同的两列数量都超过总数的一半。那么考虑枚举不合法的一列，假设我们已经枚举了不合法的列为 $col$，接下来会发现我们只关心一个数的位置是否在当前列；如果属于其他列的情况，那么它具体在哪一列对当前列的合法性并无影响，并不需要考虑。

  所以可以用 $f(i,j,k)$ 表示对于 $col$ 这一列，前 $i$ 行在 $col$ 列中选了 $j$ 个，在其他列中选了 $k$ 个，令 $s_i$ 为第 $i$ 行的总和，则有转移

$$f(i,j,k)=f(i-1,j,k)+a(i,col)\times f(i-1,j-1,k)+(s_i-a(i,col)\times f(i-1,j,k-1))$$

  状态数 $\mathcal{O}(n^3)$，转移 $\mathcal{O}(1)$，加上枚举 $col$，复杂度为 $\mathcal{O}(m{n}^3)$。统计下式的值并对每一列求和即可得到不合法的方案数：

$$\sum _{j>k}f(n,j,k)$$

  接下来考虑计算总方案数，只需设 $g(i,j)$ 为前 $i$ 行共选了 $j$ 个数的方案数，则有转移

$$g(i,j)=g(i-1,j)+s_i\times g(i-1,j-1)$$

  通过统计可以求得总方案数，这一步是 $\mathcal{O}(n^2)$ 的，所以我们可以在 $\mathcal{O}(m{n}^3)$ 的总复杂度内完成这道题，获得 $\mathtt{\text{84;pts}}$。

  继续优化状态表示，我们注意到，在 $f(i,j,k)$ 的转移过程中，我们实际上并不关心 $j$，$k$ 的具体数值，而只关心相对的大小关系；所以我们可以将状态变为 $f(i,j)$，表示前 $i$ 行，当前列的数比其他列的数多了 $j$ 个，则有转移

$$f(i,j)=f(i-1,j)+a(i,col)\times f(i-1,j-1)+(s_i-a(i,col))\times f(i-1,j+1)$$

  总复杂度降为 $\mathcal{O}(m{n}^2)$，从而可以获得 $\mathtt{\text{100;pts}}$。

  【代码片段】

scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
        scanf("%d", &a[i][j]);
        sum[i][0] = (sum[i][0] + a[i][j]) % mod;
    }
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
        sum[i][j] = (sum[i][0] - a[i][j] + mod) % mod;
long long ans = 0;
for (int col = 1; col <= m; ++col) {
    memset(f, 0, sizeof(f));
    f[0][n] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = n - i; j <= n + i; ++j)
            f[i][j] = (f[i - 1][j] + f[i - 1][j - 1] * a[i][col] % mod + f[i - 1][j + 1] * sum[i][col] % mod) % mod;
    for (int j = 1; j <= n; ++j)
        ans = (ans + f[n][n + j]) % mod;
}
g[0][0] = 1;
for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= n; ++j)
        g[i][j] = (g[i - 1][j] + (j > 0 ? g[i - 1][j - 1] * sum[i][0] % mod : 0)) % mod;
for (int j = 1; j <= n; ++j)
    ans = (ans - g[n][j] + mod) % mod;
printf("%lld\n", ans * (mod - 1) % mod);

【例 $6$】跳房子 $\mathtt{\text{(2017-NOIP-J-T4)}}$

  【题目描述】 跳房子的游戏规则如下：在地面上确定一个起点，然后在起点右侧画 $n$ 个格子，这些格子都在同一条直线上。每个格子内有一个整数，表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定：玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。

  现在小 $\mathtt{\text{R}}$ 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 $d$。小 $\mathtt{\text{R}}$ 希望改进他的机器人，如果他花 $g$ 个金币改进他的机器人，那么他的机器人灵活性就能增加 $g$，但是需要注意的是，每次弹跳的距离至少为 $1$。具体而言，当 $g

  现在小 $\mathtt{\text{R}}$ 希望获得至少 $k$ 分，请问他至少要花多少金币来改造他的机器人。

  【输入格式】 第一行三个正整数 $n$，$d$，$k$，分别表示格子的数目，改进前机器人弹跳的固定距离，以及希望至少获得的分数。相邻两个数之间用一个空格隔开。接下来 $n$ 行，每行两个整数 $x_i$，$s_i$，分别表示起点到第 $i$ 个格子的距离以及第 $i$ 个格子的分数。两个数之间用一个空格隔开。保证 $x_i$ 按递增顺序输入。

  【输出格式】 一行一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 $k$ 分，输出 $-1$。

  【样例输入】

7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

  【样例输出】

2

  【样例解释】 花费 $2$ 个金币改进后，小 $\mathtt{\text{R}}$ 的机器人依次选择的向右弹跳的距离分别为 $2,3,5,3,4,3$，先后到达的位置分别为 $2,5,10,13,17,20$，对应 $1,2,3,5,6,7$ 这 $6$ 个格子。这些格子中的数字之和 $15$ 即为小 $\mathtt{\text{R}}$ 获得的分数。

  【数据范围】 对于全部的数据满足 $1\le n\le 5\times {10}^5$，$1\le d\le 2\times {10}^3$，$1\le x_i,k\le {10}^9$，$|s_i|<{10}^5$。

  【题目分析】 显然需要二分金币花费的值，然后需要考虑，怎样判断二分的这个答案可不可以，显然使用动态规划。

  $f_i$ 表示跳到第 $i$ 个格子时所能得到的分数最大值，若跳不到该格，则 $f_i=-inf$，否则 $f_i=max(f_j+a_i)$ $(i-d-g\le j\le i-d+g)$。时间复杂度 $\mathcal{O}(n^2)$，对于 $50\mathrm{\%}$ 的数据可以过。

  优化决策选择 —— 单调队列。对于上式，可以进行参数分离，即 $f_i=max(f_j+a_i)=max(f_j)+a_i$，所以时间复杂度主要是因为需要 $\mathcal{O}(n)$ 的时间来找最大的 $f_j$，这显然可以通过单调队列来实现。

【例 $7$】摆渡车 $\mathtt{\text{(2018-NOIP-J-T3)}}$

  【题目描述】 有 $n$ 名同学要乘坐摆渡车从人大附中前往人民大学，第 $i$ 位同学在第 $t_i$ 分钟去等车。只有一辆摆渡车在工作，但摆渡车容量可以视为无限大。摆渡车从人大附中出发、把车上的同学送到人民大学、再回到人大附中（去接其他同学），这样往返一趟总共花费 $m$ 分钟（同学上下车时间忽略不计）。摆渡车要将所有同学都送到人民大学。

  凯凯很好奇，如果他能任意安排摆渡车出发的时间，那么这些同学的等车时间之和最小为多少呢？

  注意：摆渡车回到人大附中后可以即刻出发。

  【输入格式】 第一行包含两个正整数 $n,m$，以一个空格分开，分别代表等车人数和摆渡车往返一趟的时间。第二行包含 $n$ 个正整数，相邻两数之间以一个空格分隔，第 $i$ 个非负整数 $t_i$ 代表第 $i$ 个同学到达车站的时刻。

  【输出格式】 一行一个整数，表示所有同学等车时间之和的最小值（单位：分钟）。

  【样例输入】

5 1 
3 4 4 3 5

  【样例输出】

0

  【样例解释】 过程如下：

• 同学 $1$ 和同学 $4$ 在第 $3$ 分钟开始等车，等待 $0$ 分钟，在第 $3$ 分钟乘坐摆渡车出发。摆渡车在第 $4$ 分钟回到人大附中。

• 同学 $2$ 和同学 $3$ 在第 $4$ 分钟开始等车，等待 $0$ 分钟，在第 $4$ 分钟乘坐摆渡车出发。摆渡车在第 $5$ 分钟回到人大附中。

• 同学 $5$ 在第 $5$ 分钟开始等车，等待 $0$ 分钟，在第 $5$ 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。总等待时间为 $0$。

  【数据范围】 对于 $100\mathrm{\%}$ 的数据，$n\le 500,m\le 100,0\le t_i\le 4\times {10}^6$。

  【题目分析】 设 $f_i$ 表示在第 $i$ 分钟发出一班车时，所需要等待的最小时间。最后一个人到车站的时间为 $t$，则有

$$f_i=\min{f_k+\sum_{k

  最终答案 $ans=min(f_i)(t\le i<t+m)$，时间复杂度为 $\mathcal{O}(n{t}^2)$。

  前缀和优化。对于 $\sum _{k<a_j\le i}(i-a_j)$，设 $cn{t}_i$ 表示从 $0$ 到 $i$ 时间为止到达车站的人数和，设 $su{m}_i$ 表示从 $0$ 到 $i$ 时间为止到达车站的人的时间总和，则

$$\sum _{k<a_j\le i}(i-a_j)=i\times (cn{t}_i-cn{t}_k)-(su{m}_i-su{m}_k)$$

  即状态转移方程为

$$f_i=min(f_k+i\ast (cn{t}_i-cn{t}_k)-(su{m}_i-su{m}_k))(k\le i-m)$$

  时间复杂度降为 $\mathcal{O}(t^2)$。

  决策选择优化。由于在最坏情况下，在 $k$ 时刻发出了一辆车，若有同学在 $k+1$ 时刻到达了车站，摆渡车将会在 $k+m$ 时刻返回，考虑到等待其他学生的情况，摆渡车最晚会在 $k+2m-1$ 时刻发出（不然还不如在 $k+m$ 时刻和 $k+2m$ 时刻各发出一辆），所以我们可以得到结论：没有一个同学会等待超过 $2m$ 分钟。依此，状态转移方程为

$$f_i=min(f_k+i\ast (cn{t}_i-cn{t}_k)-(su{m}_i-su{m}_k))(i-2m<k\le i-m)$$

  时间复杂度为 $\mathcal{O}(mt)$。

  去除冗余阶段。根据上一条优化的结论，当顺序相邻的两位同学的时间间隔超过 $2m$ 的时候，其中的状态都是无用的，可以直接压缩至 $2m$。即对 $a$ 排序后，若 $a_{i+1}-a_i>2m$，则对后续所有的 $a_k=a_k-a_{i+1}-a_i-2m(k>i)$。另外，可以将动规的起点定为第一个同学到达的时间，则最后到达的时间 $t$ 最大为 $2mn$，最终的时间复杂度为 $\mathcal{O}(n{m}^2)$。

PS: 如有错误请在聊天区 @ 我哦