HDU 5794 A Simple Chess （容斥原理+Lucas定理+dp）

发表于 |
字数统计: 936字 | 阅读时长 ≈ 5min

A Simple Chess

问题描述

有一个n*m棋盘，一枚棋子要从(1,1)格子移动到(n,m)格子。
该棋子能从坐标为(x1,y1)的格子跳到格子(x2,y2),当且仅当:

(x2-x1)^2+(y2-y1)^2=5 x2>x1，y2>y1

棋盘上有r个格子有障碍物，棋子不能落到有障碍物的格子上。
请你计算，该棋子从起点到达终点总共有多少种方案。

输入格式

有若干组数据(<=25组)，对于每组数据，格式如下：
一行，三个整数n，m，r
接下来r行，每行两个整数，表示一个有障碍物的格子的坐标。

输出格式

对于每组数据，输出一行，一个整数，表示所求方案数。mod 110119

样例输入 1

1 1 0
3 3 0
4 4 1
2 1
4 4 1
3 2
7 10 2
1 2
7 1

样例输出 1

1
0
2
1
5

样例输入 2

58939239 79926962 4
28255565 36535194
51497377 67322260
48931736 62290476
23383627 30097072

样例输出 2

9061

提示

对于100%的数据：1≤n,m≤10^18 , 0≤r≤100
(1,1)格子不会有障碍。

为了方便，将题目中的$x,y$坐标都减一，变成从$(0,0)$到$(n-1,m-1)$

如果不考虑障碍，那么从$(0,0)$到$(x,y)$的方案数是一个组合数，这个比较好推，就是$C_{\frac{x+y}{3}}^{\frac{2x-y}{3}}$，注意到$(x,y)$可以到达当且仅当$x+y\equiv0\ mod\ 3$

障碍数比较小，考虑容斥，令$F[i]$表示从$(1,1)$出发，经过的第一个障碍是第$i$个障碍，那么对于每一个在$i$左下角的障碍$j$，
$$
F[i]=C_{\frac{x_i+y_i}{3}}^{\frac{2x_i-y_i}{3}}-\sum_{j}F[j]\times C_{\frac{tx+ty}{3}}^{\frac{2tx-ty}{3}},tx=x_i-x_j,ty=y_i-y_j
$$
直接写个记忆化搜索，暴力枚举那些点在左下方就行了。
组合数用$Lucas$处理，预处理阶乘和逆元，注意到$2x-y$可能小于$0$，此时也意味着走不到，因此要返回$0$
另外还需要注意如果终点是障碍，那么答案也是$0$

总时间复杂度$O(n^2\times???)$，还是很快。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 105
#define ll long long
using namespace std;
const ll mod=110119;
ll n,m,r,F[N],X[N],Y[N],fac[110220],inv[110220];
bool mark[N];
ll C(ll a,ll b)
{
	if(a<b)return 0;
	return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
ll Lucas(ll a,ll b)
{
	if(a<b)return 0;
	if(a<0||b<0)return 0;
	if(b==0||a==0)return 1;
	return Lucas(a/mod,b/mod)*C(a%mod,b%mod)%mod;
}
ll DP(ll p)
{
	ll i,j;
	if(F[p]!=-1)return F[p];
	if(mark[p])return F[p]=0;
	F[p]=Lucas((X[p]+Y[p])/3,(2*Y[p]-X[p])/3);
	for(i=1;i<=r;i++)
	if(X[i]<X[p]&&Y[i]<Y[p])
	{
		if(mark[i])continue;
		F[p]-=DP(i)*Lucas((X[p]+Y[p]-X[i]-Y[i])/3,(2*(Y[p]-Y[i])-X[p]+X[i])/3)%mod;
		F[p]%=mod;
	}
	F[p]+=mod;F[p]%=mod;
	return F[p];
}
int main()
{
	ll i,j,k,x,y;bool f;
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(i=2;i<=mod;i++)
	{
		fac[i]=fac[i-1]*i%mod;
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	}
	for(i=2;i<=mod;i++)inv[i]=inv[i]*inv[i-1]%mod;
	while(scanf("%lld%lld%lld",&n,&m,&r)!=EOF)
	{
		f=0;
		for(i=1;i<=r;i++)
		{
			scanf("%lld%lld",&X[i],&Y[i]);
			if(X[i]==n&&Y[i]==m)f=1;
		}
		if(f){puts("0");continue;}
		for(i=1;i<=r;i++)X[i]--,Y[i]--;
		X[++r]=n-1;Y[r]=m-1;
		for(i=1;i<=r;i++)mark[i]=(X[i]+Y[i])%3!=0;
		memset(F,-1,sizeof(F));
		printf("%lld\n",DP(r));
	}
}