洛谷P3336 [ZJOI2013]话旧题解

题目链接：P3336 [ZJOI2013]话旧

题意：小林跟着银河队选手去了一趟宇宙比赛，耳濡目染，变得学术起来。回来后，他发现世界大变样了。比丘兽究级进化，成了凤凰兽；金先生因为发了一篇 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\) 个整点的函数值，那么：

有多少个函数满足条件？

满足条件的函数中，\(f(x)\) 的最大值，最大能是多少？

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

输入格式

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

输出格式

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

输入输出样例

输入 #1
2 0
输出 #1
1 1
输入 #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\) ，说明每次下降都是直接一口气到底的

从文字中可以看出题目保证了有解（不然怎么输出最大值）

考虑设计状态 \(dp[i][0/1]\) 表示是需要访问到 \(i\) 结点时的路径是向上还是向下的

\(dp[i][1] \to dp[i+1][0]\)

显然延长左右的两条路径，可得零点 \(a,b\)

然后在 \(a,b\) 间反复横跳便可以相连了

设 \(a,b\) 间的距离为 \(2k\) ，则方案数为 \(2^{k-1}\)

如下图 \((2k=6)\)
```
\          /
 \        /
  \/\/\/\/
```
观察到其形成了 \(4\) 个 \/ 的结构，不妨其为齿孔
```
\          /
 \  /\    /
  \/  \/\/
```
注意到此时除了两侧的齿孔不可扩展以外，其余均可扩展

故方案数为 \(2^2 = 4\)
\(dp[i][0] \to dp[i+1][0]\)

不妨将 \(i\) 与其向上的路径看作一个点，则又可以确定两个零点 \(a,b\)

而此时左侧的齿孔也可以扩展了，而右侧的仍不可，故方案数为 \(2^k\)

如下图 \((2k=4)\)
```
/\        /
  \      /
   \/\/\/
```
扩展左侧齿孔会变成
```
 /\      /
/  \    /
    \/\/
```
故方案数为 \(2^2 = 4\)
\(dp[i][1]\to dp[i+1][1]\)

与上一种情况类似，将 \(i+1\) 与其向下的路径看作一个点

右侧的齿孔可以扩展，而此时左侧的不可，故方案数为 \(2^k\)
\(dp[i][0] \to dp[i+1][1]\)

考虑将 \(i+1\) 与其向下的路径看作一个点

则此时左侧的齿孔可以扩展，而右侧的不可以

故方案数为 \(2^k\)

然而有些情况会导致 \(k<0\) ，因此要特判一下

还有一些特殊的情况，比如 \(i+1\) 恰好在 \(i\) 的向上/下的路径上，也需要特判

然后最大值的求解，根据贪心，一定先选掉所有的上升

设有 \(a\) 个上升， \(b\) 个下降，则有 \[ \begin{cases} a+b = x_2-x_1 \\ a-b = y_2-y_1 \end{cases} \] 则最大值为 \[ y_1+a = \dfrac{1}{2}(x_2+y_2-x_1 + y_1) \] 但是要注意，如果可以选择向上，一定有 \(dp[i][0]\ne0\)

因此对于所有的 \(i\) 到 \(i+1\) 的转移，都额外计算一下先走到底再上升的情况，即 \[ \dfrac{1}{2}(x_2+y_2-x_1-y_1) \] 代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e6+15)
const int p=19940417;
int n,k,mx;
void add(int &a,int b){a=((a+b%p)%p+p)%p;}
int qpow(int a,int b)
{
    int ans=1,base=a%p;
    while(b)
    {
        if(b&1)ans=ans*base%p;
        base=base*base%p;
        b>>=1;
    }
    return ans;
}
struct node
{
    int x,y;
}a[N];
bool operator<(node a,node b)
    {return a.x<b.x;}
bool operator==(node a,node b)
    {return a.x==b.x&&a.y==b.y;}
int dp[N][2];
signed main()
{
    read(n);read(k);
    for(int i=1; i<=k; i++)
        read(a[i].x),read(a[i].y);
    a[++k]={0,0};a[++k]={n,0};
    sort(a+1,a+1+k);k=unique(a+1,a+1+k)-a-1;
    dp[1][1]=1;
    for(int i=1; i<k; i++)
    {
        int d=(a[i+1].x-a[i].x-a[i+1].y-a[i].y)>>1;
        mx=max(mx,(a[i+1].x+a[i+1].y-a[i].x-a[i].y)>>1);
        if(dp[i][0])mx=max(mx,(a[i+1].x+a[i+1].y-a[i].x+a[i].y)>>1);
        if(a[i+1].y-a[i].y==a[i].x-a[i+1].x)
            add(dp[i+1][1],dp[i][0]+dp[i][1]);
        else if(a[i+1].y-a[i].y==a[i+1].x-a[i].x)
            add(dp[i+1][0],dp[i][0]+(a[i].y?0:dp[i][1]));
        else if(d<0)
            add(dp[i+1][1],dp[i][0]);
        else if(d==0)
            add(dp[i+1][0],dp[i][0]+dp[i][1]),add(dp[i+1][1],dp[i][0]);
        else
        {
            int c=qpow(2,d-1);
            if(a[i+1].y)add(dp[i+1][0],(dp[i][1]+2ll*dp[i][0]%p)%p*c);
            add(dp[i+1][1],(dp[i][1]+2ll*dp[i][0]%p)%p*c);
        }
    }
    printf("%lld %lld\n",dp[k][1],mx);
    return 0;
}