45 分做法

直接输出不用魔法点的答案，第一问是 $2\times n\times w_1$，第二问是 $\dbinom{2n}{n}$。

25 分做法

如果使用魔法点更优，则用的越多越好。然后就转化成了二维的最长上升子序列问题。这里的“上升”指 $\forall i<j, x_i<x_j ~and~y_i<y_j$ 。

当 $k$ 比较小的时候，设计 $f_i$ 表示以 $i$ 结尾的最长上升子序列长度，$g_i$ 表示以 $i$ 为结尾的方案数。先按照 $x$ 在按照 $y$ 排序，转移条件是 $x_i \ne x_j ~and~ y_i>y_j$。

然后这个时候如果把第一种情况写错了，你就会 25 分做法了。

具体代码可以参考我赛时代码。

70 分做法

把前两个合起来，注意第一种情况别写错了。

如果 $k$ 过大直接输出第一种情况的答案。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+(c^'0');
		c=getchar();
	}
	return x*y;
}
const int N=500005,mod=1000000007;
int n,w1,w2,k;
struct node {
	int x,y;
} a[N];
bool cmp(node A,node B) {
	if(A.x==B.x)return A.y<B.y;
	return A.x<B.x;
}
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}return res;
}
int f[N],g[N];
signed main() {
//	freopen("grid.in","r",stdin);
	R(n),R(k),R(w1),R(w2);
	for(int i=1; i<=k; ++i) R(a[i].x)+1,R(a[i].y)+1;
	sort(a+1,a+1+k,cmp);
	g[0]=1;
  if(k<=5000)
	for(int i=1; i<=k; ++i) {
		for(int j=0; j<k; ++j) {
			if(a[i].y>a[j].y&&a[i].x!=a[j].x) {
				if(f[i]<f[j]+1) {
					f[i]=f[j]+1;
					g[i]=g[j];
				} else if(f[i]==f[j]+1) {
					g[i]=(g[i]+g[j])%mod;
				}
			}
		}
	}
	int len=0;
	for(int i=1; i<=k; ++i) {
		len=max(len,f[i]);
	}
	int cost1=2*n*w1,cost2=cost1+len*(w2-2*w1);
	if(cost1<cost2||k>5000){
		int fac1=1,fac2=1;
		for(int i=1;i<=2*n;++i){
			fac2=fac2*i%mod;
			if(i<=n) fac1=fac1*i%mod;
		}
		int inv1=ksm(fac1,mod-2);
		cout<<cost1<<"\n"<<fac2*inv1%mod*inv1%mod;
		return 0;
	}
	int ans=0;
	for(int i=1;i<=k;++i){
		if(len==f[i]) ans=(ans+g[i])%mod;
	}
	cout<<cost2<<"\n"<<ans;
	return 0;
}

满分做法

复杂度瓶颈在于 $\mathcal O(k^2)$ 的状态转移。这个看着挺像二维数点。首先，如果 $x$ 一样，$y$ 降序排，这样就不用判 $x_i\ne x_j$ 了。

然后现在只有 $y$ 这一个偏序关系要处理。我们使用树状数组优化 DP。

树状数组需要维护长度和方案，要支持以下两个操作：

• add(x,f,g)，把 $(x,f_x,g_x)$ 加入树状数组。

• ask(x)，找出下标 $\le x$ 的最大长度和方案。

然后把 DP 部分改一下就行了。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+(c^'0');
		c=getchar();
	}
	return x*y;
}
const int N=500005,mod=1000000007;
int n,w1,w2,k;
struct node {
	int x,y;
} a[N];
bool cmp(node A,node B) {
	if(A.x==B.x)return A.y>B.y;
	return A.x<B.x;
}
int ksm(int a,int b) {
	int res=1;
	while(b) {
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int f[N],g[N];
int tf[N],tg[N];
#define lb(x) (x&(-x))
void add(int x,int f,int g){
	while(x<=n){
		if(f>tf[x]) tf[x]=f,tg[x]=g;
		else if(f==tf[x]) tg[x]=(tg[x]+g)%mod;
		x+=lb(x);
	}
}
pair<int,int>ask(int x){
	int f=0,g=0;
	while(x){
		if(tf[x]>f) f=tf[x],g=tg[x];
		else if(tf[x]==f) g=(g+tg[x])%mod;
		x-=lb(x);
	}
	return {f,g};
}
signed main() {
//	freopen("grid.in","r",stdin);
	R(n),R(k),R(w1),R(w2);
	for(int i=1; i<=k; ++i) R(a[i].x)+2,R(a[i].y)+2;
	sort(a+1,a+1+k,cmp);
	add(1,0,1);
	for(int i=1; i<=k; ++i) {
		pair<int,int>pii=ask(a[i].y-1);
		f[i]=pii.first+1,g[i]=pii.second;
		add(a[i].y,f[i],g[i]);
	}
	int len=0;
	for(int i=1; i<=k; ++i) {
		len=max(len,f[i]);
	}
	int cost1=2*n*w1,cost2=cost1+len*(w2-2*w1);
	if(cost1<cost2) {
		int fac1=1,fac2=1;
		for(int i=1; i<=2*n; ++i) {
			fac2=fac2*i%mod;
			if(i<=n) fac1=fac1*i%mod;
		}
		int inv1=ksm(fac1,mod-2);
		cout<<cost1<<"\n"<<fac2*inv1%mod*inv1%mod;
	} else {
		int ans=0;
		for(int i=1; i<=k; ++i) {
			if(len==f[i]) ans=(ans+g[i])%mod;
		}
		cout<<cost2<<"\n"<<ans;
	}
	return 0;
}