P3336 话旧

题面

题目描述

小林跟着银河队选手去了一趟宇宙比赛，耳濡目染，变得学术起来。回来后，他发现世界大变样了。比丘兽究级进化，成了凤凰兽；金先生因为发了一篇 paper，一跃成为教授，也成为了银河队选拔委员会成员。

一日，小林与金教授聊天。金教授回忆起过去的岁月，那些年他学过的电路原理。他曾经对一种三角波很感兴趣，并且进行了一些探究。小林感到很好奇，于是金教授就将课题形式化地说了一遍。

有一定义在 $[0,N]$ 的连续函数 $f(x)$，其中 $N$ 是整数，满足 $f(0)=f(N)=0$，它的所有极值点在整数处取到，且 $f(x)$ 的极小值均是 $0$。对于任意的 $0$ 到 $N-1$ 间的整数 $I$，$f(x)$ 在 $(I, I+1)$ 上是斜率为 $1$ 或 $-1$ 的一次函数。

金先生研究的是，若他知道其中 $K$ 个整点的函数值，那么：

1. 有多少个函数满足条件？
2. 满足条件的函数中，$f(x)$ 的最大值，最大能是多少？

小林思考了一下，便想出了很好的算法。那么作为经过多年训练的你呢？

输入格式

第一行包含两个用空格隔开的整数 $N,K$。接下来 $K$ 行，每行两个整数，表示 $x_i$ 和 $f(x_i)$。

输出格式

一行两个整数，分别对应两个问题的答案。考虑到第一问答案可能很大，你只要输出它除以 $19940417$ 的余数。

样例 #1

样例输入 #1

2 0

样例输出 #1

1 1

样例 #2

样例输入 #2

6 9
4 2
4 2
2 0
4 2
6 0
5 1
2 0
0 0
0 0

样例输出 #2

1 2

提示

• 对于 $10\%$ 的数据，$N \leq 10$。
• 对于 $20\%$ 的数据，$N \leq 50$。
• 对于 $30\%$ 的数据，$N \leq 100$，$K \leq 100$。
• 对于 $50\%$ 的数据，$N \leq 10^3$，$K \leq 10^3$。
• 对于 $70\%$ 的数据，$N \leq 10^5$。
• 另有 $10\%$ 的数据，$K=0$。
• 对于 $100\%$ 的数据，$ 0 \leq N \leq 10^9$，$0 \leq K \leq 10^6$。

思路

这一道题的情况有点多，需要有条不紊地列出来。

首先，由于这个函数的极小值是 0，因此它一旦开始下降就必然下降到 0.

所以当前这个点是处于上升还是处于下降状态对我们转移有影响，所以我们设 $f_i$ 为 $i$ 号点为上升点的函数方案数，$g_i$ 为 $i$ 号点为 下降点的函数方案数。

那么分类讨论：

假如当前点和上一个点斜率为 1，那么这个点必然是上升点，上一个点如果不是零点，那它就是上升点；如果上一个点是零点，那它就是下降点。

如果当前点和上一个点斜率为 -1，那么这个点必然是下降点，上一个点既可以是上升点也可以是下降点。

剩下的就是分别经过两点的两条直线相交的情况了：

假如是无法向下交于同一零点且在空中提前相交，那么它们只可能向上交于一点。

假如是可以向下交于同一零点，那么它们既可以向上交也可以向下交。

假如向下分别产生了两个零点，那么就会产生很多情况，我们先把最原始的样子画出来：

下面产生了尽可能多的零点，零点数也就是截距的一半，所以对于它们的每一个，我们都可以把它“拎起来”，每个零点有不变和拎起的两个状态，看作 0 和 1，那么方案数就是 $0\sim{111111\dots}$ 也就是 $2^k$ 种，其中 $k$ 为零点数，但假如 $x$ 是下降点，也就是说 $x$ 对应的那个零点是不可以被拎起来的，这种情况的零点数要减一。

更好的图可以参考这篇博客

举个例子（八种）：

那么更新最大值的时候能向上就尽量向上，解出来的式子是 $\dfrac{y_x-x_x+y_y+x_y}{2}$。

需要注意的是，假如上一个点是下降点，那么它不可以直接上升，它需要触底反弹后再上升，这个式子解出来是 $\dfrac{y_x+y_y-x_x-x_y}{2}$。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int MOD = 19940417;
typedef long long LL;

int n, k;
int ans;
LL f[N], g[N]; // 经过前 i 个点且 i - 1 ~ i 斜率为 1 / -1 的函数的个数

struct Function
{
    int x, y;
    bool operator < (const Function &t) const 
    {
        return x < t.x;
    }
    bool operator == (const Function &t) const 
    {
        return x == t.x && y == t.y;
    }
}p[N];

LL ksm(LL x, int y)
{
    LL res = 1;
    while(y)
    {
        if(y & 1) res = res * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return res;
}

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= k; i++)
        scanf("%d%d", &p[i].x, &p[i].y);
    p[++k].x = 0, p[k].y = 0;
    p[++k].x = n, p[k].y = 0;
    sort(p + 1, p + k + 1);
    k = unique(p + 1, p + k + 1) - p - 1;
    // for(int i = 1; i <= k; i++)
        // printf("x[%d]: %d, y[%d]: %d\n", i, p[i].x, i, p[i].y);
    g[1] = 1, f[1] = 0;
    for(int i = 2; i <= k; i++)
    {
        auto &a = p[i - 1], &b = p[i];
        int len = (b.x - b.y - a.x - a.y) >> 1;
        ans = max(ans, (b.x + b.y - a.x - a.y) >> 1); // 先下去再上来
        if(f[i - 1]) ans = max(ans, (b.x + b.y - a.x + a.y) >> 1); // 上一个点不是在下降 才可以让它上升 不然可能不合法
        if(a.x - b.x == a.y - b.y) // k = 1
        {
            if(a.y) f[i] = f[i - 1]; // 上一个点不是零点 那么同为上升点路径唯一 函数个数不变
            else f[i] = g[i - 1]; // 假如上一个点是零点 那么就是它作为下降点的函数个数
        }
        else if(a.x - b.x == b.y - a.y) // k = -1
        {
            g[i] = (f[i - 1] + g[i - 1]) % MOD; // 上一个点既可以上升也可以下降 所以都要算上
        }
        else if(len <= 0) // 向上有交点 无法向下
        {
            if(len == 0) f[i] = (f[i - 1] + g[i - 1]) % MOD; // 如果下方恰好交于一个零点 那么当前点可以作为上升点被更新 上一个点上升下降都可以
            if(a.y) g[i] = f[i - 1]; // 如果上一个点不是零点 那么必然是上升点
            else g[i] = g[i - 1]; // 否则是下降点
        }
        else // 向下到 y = 0 有两个交点 那么数齿即可 齿数 = 截距 / 2 如果上一个点是下降点 那么这个齿不能往上翻 所以齿数 - 1
        {
            int l = ksm(2, len - 1); // 每一个齿有原型和拉起两个状态 0 / 1 可以用二进制理解
            if(b.y) // 如果当前点不是零点 那么可以作为上升点被更新
            {
                f[i] = 1ll * ((f[i - 1] << 1) + g[i - 1]) % MOD * l % MOD;
            }
            g[i] = 1ll * ((f[i - 1] << 1) + g[i - 1]) % MOD * l % MOD;
        }
    }
    // for(int i = 1; i <= k; i++)
    //     printf("g[%d] = %lld\n", i, g[i]);
    cout << g[k] << ' ' << ans << endl;
    return 0;
}