飞翔的小鸟：用类似完全背包的方法DP下即可。

# include <stdio.h>
# include <algorithm>
using namespace std;
int n,m,k;
const int inf=21000000;
int f[10010][1010];
int x[10010],y[10010];
int up[10010],down[10010];
int main() {
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=n;++i) {
		scanf("%d%d",&x[i],&y[i]);
		up[i]=m+1,down[i]=0;
	}
	for (int i=1,P,L,H;i<=k;++i) {
		scanf("%d%d%d",&P,&L,&H);
		up[P]=H,down[P]=L;
	}
	for (int i=1;i<=n;++i)
		for (int j=0;j<=m;++j) f[i][j]=inf;
	f[0][0]=inf;
	for (int i=1;i<=n;++i) {
		for (int j=1;j<=m;++j) {
			if(j>=x[i]) 
				f[i][j]=min(f[i][j],min(f[i-1][j-x[i]]+1,f[i][j-x[i]]+1));
			if(j==m) {
				for (int k=j-x[i];k<=m;++k) 
					f[i][j]=min(f[i][j],min(f[i-1][k]+1,f[i][k]+1));
			}
		} 
		for (int j=down[i]+1;j<=up[i]-1;++j)
			if(j+y[i]<=m)
				f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
		for (int j=1;j<=down[i];++j) f[i][j]=inf;
		for (int j=up[i];j<=m;++j) f[i][j]=inf;
	}
	int fail = k, ans = inf;
	for (int i=n; i>=1; --i) {
		for (int j=down[i]+1;j<=up[i]-1;++j)
			if(f[i][j]<inf) 
				ans=min(ans,f[i][j]);
		if(ans!=inf) break;
		if(up[i]<=m) fail --;
	}
	if(fail == k) printf("1\n%d\n",ans);
	else printf("0\n%d\n",fail);
	return 0;
}

解方程：取4个10000多的质数$p_1,p_2,p_3,p_4$，在模意义下判断。

我们会发现，在某一个模意义下，若$x$在答案内，那么$x+k \times p_i$也在答案内。

那么我们就可以把$0~p_{i}-1$的预处理出来即可，然后$O(gn+km)$判断，$k=4,g \leq 10050$。

# include <stdio.h>
using namespace std;
int n,m;
const int prime[5]={0,10037,10039,10003,10009};
int num[110][7];
bool f[10050][5];
int cnt[1000010];
int x1,x2,x3,x4,ff;
char ch;
bool js(int prim,int valu) {
	long long t=0,xx=1;
	for (int ii=n;ii>=0;--ii) 
		t=(t*valu+num[ii][prim])%prime[prim];
	return t!=0;
}
inline void scan(int i) {
	x1=x2=x3=x4=0,ff=1;ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x1=(x1<<3)+(x1<<1)+ch-'0';
		x1%=prime[1];
		x2=(x2<<3)+(x2<<1)+ch-'0';
		x2%=prime[2];
		x3=(x3<<3)+(x3<<1)+ch-'0';
		x3%=prime[3];
		x4=(x4<<3)+(x4<<1)+ch-'0';
		x4%=prime[4];
		ch=getchar();
	}
	num[i][1]=ff*x1;
	num[i][2]=ff*x2;
	num[i][3]=ff*x3;
	num[i][4]=ff*x4;
	if(ff==-1) {
		num[i][1]+=prime[1];
		num[i][2]+=prime[2];
		num[i][3]+=prime[3];
		num[i][4]+=prime[4]; 
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for (int i=0;i<=n;++i) scan(i);
	for (int i=1;i<=4;++i) 
		for (int j=0;j<prime[i];++j) 
			f[j][i]=js(i,j);
	for (int i=1;i<=m;++i) {
		bool flag=1;
		for (int j=1;j<=4;++j)
			if(f[i%prime[j]][j]){
				flag=0;
				break;
			}
		if(flag) cnt[++cnt[0]]=i;
	}
	printf("%d\n",cnt[0]);
	for (int i=1;i<=cnt[0];++i) printf("%d\n",cnt[i]);
}