原题链接
解析
首先明确极小值的含义，形象地说就是山谷，在本题中表现为函数值一旦下降则必定会下降至 0。
进一步读题发现所谓“在 \((I,I+1)\) 上是斜率为 \(1\) 或 \(−1\) 的一次函数”其实就是点 \((I,y)\) 走到点 \((I,y + 1)\) 或点 \((I,y-1)\)。
定点将函数划分成了若干个区间，我们一个区间一个区间来考虑。设 \(v_i\) 为第 \(i\) 个顶点，设 \(g_i\) 表示以 \(x_i\) 和 \(x_{i - 1}\) 为端点的区间中，合法图像个数。但是此时我们发现如果到达第 \(v_{i - 1}\) 的那一步如果是往下走的，那么只要 \(f(x_{i - 1}) > 0\)，这个区间为了满足极小值限制也得往下走。所以多加一维状态 \(g_{i,0/1}\) 表示到达 \(v_{i}\) 时是 往下走/往上走。
考虑如何转移，下面默认只讨论一般情况。
-
\(g_{i,0}\) 从 \(g_{i - 1,0}\) 转移。
画个图先。
可以发现图像中会出现若干个山峰（红色和紫色也算）除去这些山峰后会出现一个对高度作 \(\lvert f(x_i) - f(x_{i - 1})\rvert\) 的贡献的连续段，所以在山峰上消耗的步数为总步数 \(x_i - x_{i - 1}\) 减去高度差 \(\lvert f(x_i) - f(x_{i - 1})\rvert\)，记为 \(c\)。对高度做贡献的连续段的位置是确定的，必定在最后一个山峰之前或第一个山峰之前，取决于相对高度；类似红色段的山峰必定存在且高度一定，现在问题在于剩余山峰的个数以及高度。按照每个山峰考虑，一个高度为 \(h\) 的山峰需要 \(2h\) 的步数，总共可支配 \(c - 2\min(f(x_i),f(x_{i - 1}))\) 步。求方案数考虑插板，但是这里有限制每个板之间的间隔必须为偶数，所以不妨将一个元素视为两步，总共 \(\frac{c - 2\min(f(x_i),f(x_{i - 1}))}{2}\) 个元素，记为 \(m\)，这样就变为普通插板了。山峰个数，即插的板数 \(+1\) 可以是 \([1,m]\)，插 \(i\) 个板的方案数是 \(\tbinom{m - 1}{i}\)，总方案数就是 \(\sum_{i=0}^{m - 1} \tbinom{m - 1}{i}=2^{m - 1}-1\)，但是可能只有一个红色山峰，即其余山峰个数为 \(0\)，所以最终方案数为 \(2 ^ {m - 1}\)。 -
\(g_{i,0}\) 从 \(g_{i - 1,1}\) 转移。
区别在于没有了开始必须向下走的限制。
考虑向上走，按照类似的方法画图分析得到同样有一个类似的高度固定为 \(f(x_{i - 1})\) 的山峰，于是总方案数的计算方式是一样的，向下走更是一样。
-
\(g_{i,1}\) 从 \(g_{i - 1,0}\) 转移和从 \(g_{i - 1,1}\) 转移。
画图之后可以发现计算方式是完全一致的。
-
特判。
- 从 \(g_{i - 1,0}\) 转移时， \(f(x_{i - 1}) = 0\) 的情况。
- 图像只能为一条直线，没有山峰的情况。
- \(m<0\) 与 \(m=0\) 的情况。
- 后面忘了。
现在来处理第二问，其实就是个贪心，尽量把向上的堆在一起走，但是细节巨多。
时间复杂度 \(O(n\log n)\)。
话说数据貌似保证有解。
代码
你确定要看吗？
#include <bits/stdc++.h>
#define ls(p) ((p) << 1)
#define rs(p) (((p) << 1) | 1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e6 + 5,M = 100 + 5,mod = 19940417;
int g[N][2],x[N],fx[N],mx[N][2];
bool b[N][2];//表示该状态是否合法
int qmi(int a,int b){int res = 1;while(b){if(b & 1) res = 1ll * res * a % mod;a = 1ll * a * a % mod;b >>= 1;}return res;
}
map<int,int> m;
int main(){ios::sync_with_stdio(false);cin.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);int n,k;cin>>n>>k;m[0] = m[n] = 0;for(int i=1;i<=k;i++){cin>>x[i]>>fx[i];if(m.count(x[i]) && m[x[i]] != fx[i]){cout<<0; return 0;}m[x[i]] = fx[i];}vector<pii> v;for(auto it = m.begin();it != m.end();it++){v.push_back(*it);}g[0][0] = 1;b[0][0] = true;for(int i=1;i<v.size();i++){mx[i][1] = mx[i][0] = v[i].second;int c = v[i].first - v[i - 1].first - abs(v[i].second - v[i - 1].second);if(!c){if(v[i].second > v[i - 1].second){g[i][1] = g[i - 1][0] * (v[i - 1].second == 0) + g[i - 1][1];g[i][1] %= mod;b[i][1] |= b[i - 1][0] & (v[i - 1].second == 0) | b[i - 1][1];if(b[i - 1][0] && !v[i - 1].second) mx[i][1] = max(mx[i][1],mx[i - 1][0]);if(b[i - 1][1]) mx[i][1] = max(mx[i][1],mx[i - 1][1]);}if(v[i].second < v[i - 1].second){g[i][0] = g[i - 1][0] + g[i - 1][1];g[i][0] %= mod;b[i][0] |= b[i - 1][0] | b[i - 1][1];if(b[i - 1][0]) mx[i][0] = max(mx[i][0],mx[i - 1][0]);if(b[i - 1][1]) mx[i][0] = max(mx[i][0],mx[i - 1][1]);}continue;}if(c < 0 || (c - 2 * min(v[i - 1].second,v[i].second)) % 2){cout<<0; return 0;}int m = (c - 2 * min(v[i - 1].second,v[i].second)) / 2;if(m < 0){g[i][0] = g[i - 1][0] * (v[i - 1].second == 0) + g[i - 1][1];g[i][0] %= mod;b[i][0] |= b[i - 1][0] | b[i - 1][1];if(b[i][0]) mx[i][0] = max(mx[i][0],c / 2 + max(v[i].second,v[i - 1].second));if(b[i - 1][0]){mx[i][0] = max(mx[i][0],mx[i - 1][0]);}if(b[i - 1][1]){mx[i][0] = max(mx[i][0],mx[i - 1][1]);}continue;}else if(!m){g[i][1] = g[i - 1][0] + g[i - 1][1]; g[i][0] = g[i - 1][0] * (v[i - 1].second == 0) + g[i - 1][1];g[i][1] %= mod;g[i][0] %= mod;b[i][1] |= b[i - 1][0] | b[i - 1][1];b[i][0] |= b[i - 1][0] | b[i - 1][1];if(b[i][0]){if(b[i - 1][1] || b[i - 1][0] && v[i - 1].second == 0)mx[i][0] = max(mx[i][0],c / 2 + max(v[i].second,v[i - 1].second));}if(b[i - 1][0]){mx[i][0] = max(mx[i][0],mx[i - 1][0]);mx[i][1] = max(mx[i][1],mx[i - 1][0]);}if(b[i - 1][1]){mx[i][0] = max(mx[i][0],mx[i - 1][1]);mx[i][1] = max(mx[i][1],mx[i - 1][1]);}continue;}g[i][0] = 1ll * g[i - 1][0] * qmi(2,m - 1) % mod + 1ll * g[i - 1][1] * qmi(2,m) % mod;g[i][0] %= mod;b[i][0] |= b[i - 1][0] | b[i - 1][1];if(b[i - 1][0]){mx[i][0] = max(mx[i][0],mx[i - 1][0]);if(!v[i - 1].second){mx[i][0] = max(mx[i][0],max(v[i].second,v[i - 1].second) + m);}else{mx[i][0] = max(mx[i][0],v[i].second + m);}}if(b[i - 1][1]){mx[i][0] = max(mx[i][0],mx[i - 1][1]);mx[i][0] = max(mx[i][0],v[i - 1].second + m);mx[i][0] = max(mx[i][0],v[i].second + m);}if(v[i].second != 0){g[i][1] = 1ll * g[i - 1][0] * qmi(2,m - 1) % mod + 1ll * g[i - 1][1] * qmi(2,m) % mod;g[i][1] %= mod;b[i][1] |= b[i - 1][0] | b[i - 1][1]; if(b[i - 1][0]){mx[i][1] = max(mx[i][1],mx[i - 1][0]);if(!v[i - 1].second){mx[i][1] = max(mx[i][1],v[i - 1].second + m);}mx[i][1] = max(mx[i][1],m);}if(b[i - 1][1]){mx[i][1] = max(mx[i][1],v[i - 1].second + m);mx[i][1] = max(mx[i][1],mx[i - 1][1]);}}}cout<<g[v.size() - 1][0]<<" "<<mx[v.size() - 1][0];return 0;
}