题解：P3336 [ZJOI2013] 话旧

zhang_kevin · 2026-03-02 14:35:34 · 题解

是 dp 好题！

题意简述

函数 f(x) 定义在 [0, n] 上，连续，f(0) = f(n) = 0，所有极值点在整数处取到，极小值均为 0。在相邻整数区间 (I, I + 1) 上斜率为 1 或 -1。给定 k 个整点的函数值，求满足条件的函数个数（模 19940417）以及这些函数中 f(x) 的最大值的最大值。

关键性质

我们先观察一些性质。

函数值总是非负，因为极小值为 0。
任何局部极小值（本题中，等价于下降后上升的转折点）必须恰好为 0。
函数在整数点处的值均为整数，且每一步变化 1 或 -1。

这些性质非常重要。

动态规划状态

下面考虑设计 dp 状态。

我们关心处理了哪些已知点，以及上一步的方向。因此，考虑令 f_{i, 0/1} 表示处理到第 i 个已知点，且上一步的方向是向下或向上，的方案数。同理，再记 g_{i, 0/1} 表示此时最大值的最大值。

由于第一步只能向上走，因此有初始值 f_{1, 0} = 1,g_{1, 0} = 0。

转移

对于两个相邻的已知点 (x_1, y_1) 和 (x_2, y_2)，分析如何转移。

显然我们需要操作的次数 d = x_2 - x_1，移动距离 \Delta y = y_2 - y_1。显然需要满足 d \geq |\Delta y| 且 d \equiv |\Delta y| \pmod 2 才存在合法路径，否则不存在路径。

记 S = \frac{d - y_1 - y_2}{2} 表示多余的对数。具体地，操作次数 d 减去 y_1 和 y_2 后，剩余的步数应当全部用于从 0 \to 0 的“山峰”。由于山峰左右对称，因此可以除 2 得到一半的大小。

下面我们分讨 0 是否在路径上。

无 0 路径

首先考虑没有 0 的路径。由于不触碰到 0，根据性质 2，这条路径只能是先上升后下降。

假设上升了 u 步，下降了 v 步。则我们要求 u + v = d 且 u - v = \Delta y，解得 u = \frac{d + \Delta y}{2}, v = \frac{d - \Delta y}{2}。

这个过程中路径唯一，最大值 M = y_1 + u = \frac{y_1 + y_2 + d}{2}。且第一步方向为上升当且仅当 u > 0，最后一步方向为下降当且仅当 v > 0。

有 0 路径

这类路径可以由两个整数 a,b 和一个山峰高度数组 h_i \geq 1 描述，需要满足 a + b + \sum h_i = S。其中，a 表示从 y_1 到第一个 0 的上升步数，b 表示从最后一个 0 到 y_2 的下降步数。

举个例子，我们可以这样描述一条路径：

第一段：从 y_1 开始先上升 a 步，再下降 a + y_1 步，到达 0。
中间段：许多从 0 \to 0 的山峰，高度为 h_i。
末尾段：从 0 上升 b + y_2 步到达 b + y_2，再下降 b 步到达 y_2。

问题等价地转化为对合法的有序三元组 (a, b, (h_1, h_2, \cdots, h_k)) 计数。

首先我们知道合法的路径总数为 2^{S + 1} - 1，证明如下。

不妨写出其生成函数：
(\sum_{a \geq 0} x^{a})(\sum_{b \geq 0} x^{b})(\sum_{k \geq 0}(\sum_{h \geq 1} x^{h})^{k})=\frac{1}{1-x} \cdot \frac{1}{1-x} \cdot \frac{1}{1-\frac{x}{1-x}}=\frac{1}{(1-x)(1-2x)}
展开得 \frac{1}{(1 - x)(1 - 2x)} = \sum\limits_{S \geq 0} (2^{S + 1} - 1)x^S，故 x^S 的系数为 2^{S + 1} - 1。

证毕。

接下来分讨各种方向的可能情况，如下表所示：

第一步	最后一步	要求的条件	方案数	此时该段内最大值的最大值
上升	上升	S \geq 1	2^{S - 1}	\max(y_1 + S, y2)
上升	下降	S \geq 2	2^{S - 1} - 1	\max(y_1 + S - 1, y_2 + S - 1)
下降	上升	S \geq 0	\begin{cases}1,\qquad S= 0\\2^{S - 1}, \quad S \geq 1\end{cases}	\max(S, y2)
下降	下降	S \geq 1	2^{S - 1}	y_2 + S

注意，当 S = 0 时，只有（下降，上升）一种，方案数为 1，最大值为 0。

答案

下面分析最终答案，设加上 f(0) = 0、f(n) = 0 并去重后有 k 个要求。

由于最后必须出现在 f(n) = 0 处，只能通过下降到达。因此，可以得到第一问的答案为 f_{k, 0}，第二问的答案为 g_{k, 0}。

特别的，如果 f_{k, 0} = 0，说明无解。

时间复杂度

考虑分析时间复杂度。

前面排序的时间复杂度为 \mathcal{O}(k \log k)，dp 过程中计算 2^S 使用快速幂需要单次 \mathcal{O}(\log n)。

故总时间复杂度为 \mathcal{O}(k \log n)，足以通过。

参考实现

下面给出这道题的 C++ 参考代码。

::::info[Code]{open}

提交记录：https://qoj.ac/submission/2085823。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline char gc(){return getchar();}
inline void pc(char ch){putchar(ch);}
inline int rd(){
    int x = 0, f = 1;
    char ch = gc();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = gc();
    }
    while(isdigit(ch)){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = gc();
    }
    return x * f;
}
inline void wr(int x){
    if(x < 0) pc('-'), x = -x;
    if(x > 9) wr(x / 10);
    pc(x % 10 + '0');
    return;
}
const int Mod = 19940417;
inline int fp(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}
#define y1 zhang_kevin
int n, k, f[1000005][2], g[1000005][2];
pair<int, int> fx[1000005];
#define fi first
#define se second
signed main(){
    n = rd(), k = rd();
    for(int i = 1; i <= k; i++) fx[i].fi = rd(), fx[i].se = rd();
    fx[++k] = {0, 0}, fx[++k] = {n, 0};
    sort(fx + 1, fx + 1 + k);
    k = unique(fx + 1, fx + 1 + k) - fx - 1;
    // for(int i = 1; i <= k; i++) cout << fx[i].fi << ' ' << fx[i].se << '\n';
    memset(g, 0x80, sizeof(g));
    f[1][0] = 1, g[1][0] = 0;
    for(int i = 2; i <= k; i++){
        int x1 = fx[i - 1].fi, y1 = fx[i - 1].se, x2 = fx[i].fi, y2 = fx[i].se;
        // cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
        int d = x2 - x1, deltay = y2 - y1;
        if(d >= abs(deltay) && d % 2 == abs(deltay) % 2){
            int S = (d - y1 - y2) / 2;
            { // 无 0 路径
                int u = (d + deltay) / 2, v = (d - deltay) / 2, mx = y1 + u;
                if(u > 0){
                    if(v > 0){
                        if(y1 > 0) f[i][0] = (f[i][0] + f[i - 1][1]) % Mod;
                        if(y1 == 0) f[i][0] = (f[i][0] + f[i - 1][0]) % Mod;
                        if(y1 > 0) if(f[i][0]) g[i][0] = max({g[i][0], g[i - 1][1], mx});
                        if(y1 == 0) if(f[i][0]) g[i][0] = max({g[i][0], g[i - 1][0], mx});
                    }else{
                        if(y1 > 0) f[i][1] = (f[i][1] + f[i - 1][1]) % Mod;
                        if(y1 == 0) f[i][1] = (f[i][1] + f[i - 1][0]) % Mod;
                        if(y1 > 0) if(f[i][1]) g[i][1] = max({g[i][1], g[i - 1][1], mx});
                        if(y1 == 0) if(f[i][1]) g[i][1] = max({g[i][1], g[i - 1][0], mx});
                    }
                }else{
                    if(v > 0){
                        f[i][0] = (f[i][0] + f[i - 1][1]) % Mod;
                        f[i][0] = (f[i][0] + f[i - 1][0]) % Mod;
                        if(f[i][0]) g[i][0] = max({g[i][0], g[i - 1][1], mx});
                        if(f[i][0]) g[i][0] = max({g[i][0], g[i - 1][0], mx});
                    }else{
                        f[i][1] = (f[i][1] + f[i - 1][1]) % Mod;
                        f[i][1] = (f[i][1] + f[i - 1][0]) % Mod;
                        if(f[i][1]) g[i][1] = max({g[i][1], g[i - 1][1], mx});
                        if(f[i][1]) g[i][1] = max({g[i][1], g[i - 1][0], mx});
                    }
                }
            }
            if(S >= 0){ // 有 0 路径
                if(S >= 1 && y2 > 0){
                    int cnt = fp(2, S - 1), mx = max(y1 + S, y2);
                    if(y1 > 0) f[i][1] = (f[i][1] + f[i - 1][1] * cnt % Mod) % Mod;
                    if(y1 == 0) f[i][1] = (f[i][1] + f[i - 1][0] * cnt % Mod) % Mod;
                    if(y1 > 0) if(f[i][1]) g[i][1] = max({g[i][1], g[i - 1][1], mx});
                    if(y1 == 0) if(f[i][1]) g[i][1] = max({g[i][1], g[i - 1][0], mx});
                }
                if(S >= 2){
                    int cnt = fp(2, S - 1) - 1, mx = max(y1 + S - 1, y2 + S - 1);
                    if(y1 > 0) f[i][0] = (f[i][0] + f[i - 1][1] * cnt % Mod) % Mod;
                    if(y1 == 0) f[i][0] = (f[i][0] + f[i - 1][0] * cnt % Mod) % Mod;
                    if(y1 > 0) if(f[i][0]) g[i][0] = max({g[i][0], g[i - 1][1], mx});
                    if(y1 == 0) if(f[i][0]) g[i][0] = max({g[i][0], g[i - 1][0], mx});
                }
                if(S >= 0 && y1 > 0 && y2 > 0){
                    int cnt = S == 0 ? 1 : fp(2, S - 1), mx = max(S, y2);
                    f[i][1] = (f[i][1] + f[i - 1][1] * cnt % Mod) % Mod;
                    f[i][1] = (f[i][1] + f[i - 1][0] * cnt % Mod) % Mod;
                    if(f[i][1]) g[i][1] = max({g[i][1], g[i - 1][1], mx});
                    if(f[i][1]) g[i][1] = max({g[i][1], g[i - 1][0], mx});
                }
                if(S >= 1 && y1 > 0){
                    int cnt = fp(2, S - 1), mx = y2 + S;
                    f[i][0] = (f[i][0] + f[i - 1][1] * cnt % Mod) % Mod;
                    f[i][0] = (f[i][0] + f[i - 1][0] * cnt % Mod) % Mod;
                    if(f[i][0]) g[i][0] = max({g[i][0], g[i - 1][1], mx});
                    if(f[i][0]) g[i][0] = max({g[i][0], g[i - 1][0], mx});
                }
            }
        }else cout << "No Solution" << '\n';
    }
    wr(f[k][0]), pc(' '), wr(g[k][0]), pc('\n');
    return 0;
}

::::