rt 根据题目描述，“f(x) 的极小值均是0”，那么如下的一组数据：

20 3
6 2
8 2
10 2

就是不合法的，因为若要满足同时过给出的三个点的条件，点6 2和点8 2之间的线段就不可能有0的极小值。

（根据题解的描述，题意即每条线段必须有一个端点的函数值为0）

所以，我写了如下的一个程序来判断数据的合法性。

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int mod=19940417;

struct node{
	int x,fx;
}a[1000010];
bool cmp2(node x, node y){return x.x==y.x&&x.fx==y.fx;}
bool cmp(node x, node y){return x.x<y.x;}
int f[1000010][2];

int power(int x, int y){
	if(y==-1) return 1;
	int ans=1;
	while(y){
		if(y&1) ans=(ans*x)%mod;
		y>>=1,x=(x*x)%mod;
	}
	return ans;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=k;i++) cin>>a[i].x>>a[i].fx;
	sort(a+1,a+k+1,cmp);
	a[0]={0,0},a[++k]={n,0};
	k=unique(a,a+k+1,cmp2)-a-1;
	int maxt=0;
	for(int i=1;i<=k;i++) maxt=max(maxt,a[i].fx);
	f[0][1]=1;
	for(int i=1;i<k;i++){
		int t1=a[i+1].x-a[i].x-a[i].fx-a[i+1].fx,t2=a[i-1].x-a[i-2].x-a[i-2].fx-a[i-1].fx;
		if(t1<0&&t2<0) cout<<"ERROR\n",exit(0); //如果t1 t2 同时小于0，即数据不合法，会输出ERROR，否则会继续执行
	}
	for(int i=1;i<=k;i++){
		if(a[i].x-a[i-1].x==-a[i].fx+a[i-1].fx){
			f[i][1]=(f[i-1][1]+f[i-1][0])%mod;
		} else if(a[i].x-a[i-1].x==a[i].fx-a[i-1].fx){
			if(a[i-1].fx) f[i][0]=f[i-1][0];
			else f[i][0]=f[i-1][1];
		} else if(a[i].x-a[i-1].x<a[i].fx+a[i-1].fx){
			if(a[i-1].fx) f[i][1]=f[i-1][0];
			else f[i][1]=f[i-1][1];
			maxt=max(maxt,(a[i].x-a[i-1].x+a[i].fx+a[i-1].fx)/2);
		} else {
			if(a[i].x-a[i-1].x==a[i].fx+a[i-1].fx){
				f[i][1]=f[i-1][0];
				if(a[i-1].fx==0) f[i][1]=(f[i][1]+f[i-1][1])%mod;
				f[i][0]=(f[i-1][1]+f[i-1][0])%mod;
			} else {
				int len=(a[i].x-a[i-1].x-a[i].fx-a[i-1].fx)/2;
				int t=((f[i-1][1]+2*f[i-1][0])*power(2,len-1))%mod;
				if(a[i].fx) f[i][0]=t;
				f[i][1]=t;
			}
			int t1=a[i+1].x-a[i].x-a[i].fx-a[i+1].fx,t2=a[i-1].x-a[i-2].x-a[i-2].fx-a[i-1].fx;
			int tx1=a[i-1].x+a[i-1].fx,tx2=a[i].x-a[i].fx;
			if(t1<0&&t2<0){
				maxt=max(maxt,(tx2-tx1)/2);
			} else if(t2<0){
				maxt=max(maxt,(a[i].x-tx1+a[i].fx)/2);
			} else if(t1<0) maxt=max(maxt,(tx2-a[i-1].x+a[i-1].fx)/2);
			else maxt=max(maxt,(a[i].x-a[i-1].x+a[i].fx+a[i-1].fx)/2);
		}
	}
	cout<<f[k][1]%mod<<' '<<maxt;
	return 0;
}

提交记录如下： record

可以看到，有7个点的运行结果都是"ERROR"

所以，我们是否可以说原始测试数据有误？或是说题解对题意的理解有偏差？