0分做法

这是0分做法

10分做法

暴力dfs

void dfs(int idx,int idy,bool flg,int cnt){
	if(idx==n&&idy==n){
		if(flg){
			if(ans>cnt){
				ans=cnt,dns=cns=1;
				mp.clear(),mp[pth[idx][idy]]=1;
			}
			else if(ans==cnt){
				if(!mp[pth[idx][idy]]) mp[pth[idx][idy]]=1,cns++;
			}
		}else{
			if(ans>cnt) ans=cnt,dns=0,bns=1;
			else if(ans==cnt) bns++;
		}
	}
	for(int i=0;i<2;i++){
		int x=idx+dx[i],y=idy+dy[i];
		if(x>n||y>n||x<0||y<0) continue;
		pth[x][y]=pth[idx][idy];
		dfs(x,y,flg,cnt+w1);
	}if(vis[idx][idy]){
		int x=idx+1,y=idy+1;
		if(x>=0&&x<=n&&y>=0&&y<=n){
			char px=x+'0',py=y+'0';
			pth[x][y]=pth[idx][idy]+"(";
			pth[x][y]+=px;pth[x][y]+=",";
			pth[x][y]+=py;pth[x][y]+=")";
			dfs(x,y,1,cnt+w2);
		}
	}
}

时间复杂度 $O(不能过)$

20分做法

发现我们会使用 $w2$ 当且仅当 $w2=2\times w1$ 时我们才会使用，所以当 $w1=w2$ 的时候直接输出 $n\times w2$ 和 $1$

printf("%d\n1\n",n*w2);

45分做法

第三档是何意味？

计算不需要魔法点的答案，第一问显然是 $2\times n\times w1$ ，第二问我们可以考虑使用dp算出，我们发现这个dp数组实际上就是杨辉三角，观察一下发现答案是 $C_{2\times n}^{n}$

70分做法

我们考虑这样一个贪心，如果我们当前选魔法点更优的话那我们一定要多选魔法点

首先我们先分别按照x和y升序排序

可以使用dp来完成，设 $dp_i$ 表示以 $i$ 为结尾的可以选的最多的魔法点

时间复杂度 $O(n^2)$

则有：

85分做法

何意味？

将树状数组的MAX函数写错即可

100分做法

我们发现70分做法瓶颈在于转移，转移条件是 $x_j<x_i$ 且 $y_j<y_i$

这就是一个二维偏序问题，我们考虑在 $x$ 相同时将 $y$ 倒序排序，使用树状数组维护

时间复杂度 $O(n\log n)$

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
bool Test_MLE_start;
constexpr int N=500005,mod=1e9+7;
int _=1,n,k,w1,w2,fac[N],inv[N],dp[N],g[N];
struct node{int x,y;}a[N];
struct AIbaobao{int f,g;}c[N];
inline int reads(){
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}inline void clr(){
//	Don't forget!

}
bool cmp(node a,node b){return a.x==b.x?a.y>b.y:a.x<b.x;}
int C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
int lowbit(int x){return x&(-x);}
AIbaobao MAX(AIbaobao A,AIbaobao B){
	AIbaobao res=A;if(A.f<B.f) res=B;
	else if(A.f==B.f) res.g=(A.g+B.g)%mod;
	return res;
}
void add(int x,AIbaobao d){for(int i=x;i<=n;i+=lowbit(i)) c[i]=MAX(c[i],d);}
AIbaobao asks(int x){
	AIbaobao res={0,0};
	for(int i=x;i>0;i-=lowbit(i)) res=MAX(res,c[i]);
	return res;
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),k=reads(),w1=reads(),w2=reads();
		for(int i=1;i<=k;i++) a[i].x=reads()+2,a[i].y=reads()+2;
		sort(a+1,a+k+1,cmp);
		if(w1+w1<w2){
			int ans=2*w1*n,bns;
			fac[0]=inv[0]=fac[1]=inv[1]=1;
			for(int i=2;i<N;i++) fac[i]=fac[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod;
			for(int i=1;i<N;i++) inv[i]=inv[i]*inv[i-1]%mod;
			bns=C(n+n,n);printf("%lld\n%lld\n",ans,bns);
		}else{
			int ans=0,bns=0,cnt=0;
			a[0].x=a[0].y=1;g[0]=1;
			add(1,AIbaobao{0,1});
			for(int i=1;i<=k;i++){
				AIbaobao now=asks(a[i].y-1);
				dp[i]=now.f+1,g[i]=now.g;
				add(a[i].y,AIbaobao{dp[i],g[i]});
			}for(int i=1;i<=k;i++) cnt=max(cnt,dp[i]);
			ans=2*w1*n-cnt*(w1+w1-w2);
			for(int i=1;i<=k;i++) bns=(bns+(dp[i]==cnt)*g[i])%mod;
			printf("%lld\n%lld\n",ans,bns);
		}
	}return 0;
}
/*
3 8 1 100
0 0
0 1
1 0
1 1
2 0
0 2
2 1
1 2

*/