题解：P5376 [THUPC 2019] 过河卒二

题意

卒从

(1,1)

出发，可以向令

x+1

，或

y+1

，或

x+1

并且

y+1

。棋盘上有一些地方不可到达，求到达

(n+1,m+1)

的方案数（原文不是这样的，但是转化之后是的）。

思路

首先考虑没有障碍时怎么做。

设

dp_{i,j}

表示在没有障碍的情况下，到达

(i,j)

的方案数。

如果只有

x+1

，

y+1

两个操作是好做的，走斜线就比较烦人。

所以考虑枚举走的斜线数量。

直接给出

dp_{i,j}

的计算方法。

dp_{i+1,j+1}=\sum_{k=0}^{\min(i,j)} C_{i+j-k \times 2}^{i-k} \times C_{i+j-k}^{k}

如果有点想不明白，可以先假设斜线是在一起的，再将其与直线混在一起，求出组合数就行了。

接下来加上障碍。

考虑容斥原理（~~其实挺显然的吧~~）。

注意到

k

只有

20

，考虑暴力枚举经过了哪几个障碍即可。

具体的，先将障碍物按照

x

为第一关键字，

y

为第二关键字从小到达排序，预处理出两两之间的方案数（与上文的类似）。

然后状态压缩一下就行了。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Beginning;

#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define se second
#define fi first
using PII=pair<int,int>;
using PIB=pair<int,bool>;
using PBI=pair<bool,int>;
using PBB=pair<bool,bool>;
using PDI=pair<double,int>;
using PID=pair<int,double>;

const int mod=59393;
namespace Memory_Love{
	int read(){ int x=0; bool flag=1; char ch=getchar();
		while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
		while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return flag? x:-x;}
	template<typename T> void read(T &x){ bool flag=1; x=0; char ch=getchar();
		while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
		while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} x=(flag? x:-x);}
	template<typename T,typename ...Args> void read(T &Re,Args &...Res){read(Re),read(Res...);}
	template<typename T> void write(T x,char ch=0){if(x<0) x=-x,putchar('-');
		static short s[35],top=-1; do{s[++top]=x%10;x/=10;}while(x);
		while(~top) putchar(s[top--]+48); if(ch) putchar(ch);}
	int gcd(int a,int b){return b==0? a:gcd(b,a%b);}
	int lcm(int a,int b){return a/gcd(a,b)*b;}
	void MADD(int &x,int y,int mod){x=(x+y>=mod? x+y-mod:x+y);}
	int ksc(int a,int b,int p){int ans=0;while(b){if(b&1)MADD(ans,a,p);MADD(a,a,p);b>>=1;}return ans;}
	int ksm(int a,int b,int p){int ans=1%p;while(b){if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;}return ans;}
	int exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=0;return a;}int d=exgcd(b,a%b,y,x);y-=a/b*x;return d;}
	int inv(int t){int x,y;exgcd(t,mod,x,y);return (x%mod+mod)%mod;}
} using namespace Memory_Love;
const int N=1e5+5;
const int MK=22;
int n,m,k;
int B[MK][MK];

namespace FACT
{
	int fact[mod+5],infact[mod+5];
	void init(int n)
	{
		int i;
		for(i=fact[0]=infact[0]=1;i<=n;i++)
		{
			fact[i]=fact[i-1]*i%mod;
			infact[i]=infact[i-1]*ksm(i,mod-2,mod)%mod;
		}
	}
	int C(int n,int m)
	{
		if(n<m) return 0;
		return fact[n]*infact[m]%mod*infact[n-m]%mod;
	}
	int Lucas(int n,int m)
	{
		if(m==0) return 1;
		return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
	}
} using FACT::Lucas;

struct Barrier
{
	int x,y;
}a[MK];
bool comp(const Barrier &a,const Barrier &b)
{
	if(a.x!=b.x)
	return a.x<b.x;
	else 
	return a.y<b.y;
}

int DP(int n,int m)
{
	int i,ans=0; n--,m--;
	for(i=0;i<=min(n,m);i++)
	(ans+=Lucas(n+m-i*2,n-i)*Lucas(n+m-i,i))%=mod;
	return ans;
}

bool Ending;
signed main()
{
	int i,j;
	read(n,m,k);
	FACT::init(mod-1);
	for(i=1;i<=k;i++)
	read(a[i].x,a[i].y);
	sort(a+1,a+1+k,comp);
	a[0]=(Barrier){1,1};
	a[k+1]=(Barrier){n+1,m+1};
	
	for(i=0;i<=k+1;i++)
	{
		for(j=i+1;j<=k+1;j++)
		{
			if(a[i].y>a[j].y)
			B[i][j]=0;
			else
			B[i][j]=DP(a[j].x-a[i].x+1,a[j].y-a[i].y+1);
		}
	}
	
	int ans=DP(n+1,m+1);
	for(i=0;i<(1<<k);i++)
	{
		if(i==0) continue;
		int now=1,last=0,t=-1;
		for(j=0;j<k;j++)
		{
			if(i>>j&1)
			{
				(now*=B[last][j+1])%=mod;
				last=j+1;
				t=-t;
			}
		}
		(ans-=now*B[last][k+1]*t)%=mod;
	}
	write((ans%mod+mod)%mod,'\n');
	cerr<<"\nused:"<<(abs(&Ending-&Beginning)/1048576)<<"MB\n";
	return 0;
}

题解：P5376 [THUPC 2019] 过河卒二

文章操作

题意

思路

相关推荐

评论

题解：P5376 [THUPC 2019] 过河卒二