2016-10-07

HDU 5794 A Simple Chess【容斥】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5794

题意：

给定$n \times m$的方格，从$(1,1)$走向“马”字走向终点$(n, m)$，中间有$r$个障碍物，问有多少种走的方法。
数据范围：$1\leq n, m\leq 10^{18}, 0 \leq r\leq 100$

分析：

容斥，这题容斥的套路跟多校第一场那道轮廓线dp的容斥类似。只考虑每个点第一次出现时的贡献。
首先对于给定的点，不考虑障碍物的话，该点能否到达以及有多少种到达方案都是可以计算出来的，利用$lucas$定理。
接下来对于每个障碍只考虑在路上第一次遇到这个障碍的方案数，从终点开始dfs，每到一个障碍就减去从其他障碍到达该障碍的方案数，最后加个记忆化外壳。
也可以不dfs，直接排个序然后二重循环。

代码：


/*************************************************************************
    > File Name: 5794.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/10/6 21:19:10
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int maxn = 1e6 + 5, maxm = 123456;
ll mod = 110119;
ll fact[maxm];
void init()
{
	fact[0] = 1;
	for(int i = 1; i < maxm; ++i)
		fact[i] = fact[i - 1] * i % mod;
}
ll extgcd(ll a, ll b, ll &x, ll &y)
{
    ll d = a;
    if(b != 0) {
        d  = extgcd(b, a % b, y, x);
        y -= (a/b) * x;
    }else {
        x = 1, y = 0;
    }
    return d;
}
ll comb(ll n, ll m, ll p)
{
	if(m < 0 || m > n) return 0;
	ll x, y;
	extgcd(fact[m], p, x, y);
	ll xx, yy;
	extgcd(fact[n - m], p, xx, yy);
	return fact[n] * x % p * xx % p;
}
ll lucas(ll n, ll m, ll p)
{
	return m ? lucas(n / p, m / p, p) * comb(n % p, m % p, p) % p: 1;
}
int r;
vector<pll>v;
map<pll, ll>mp;
map<pll, bool>vis;
bool check(ll x, ll y)
{
	if((2 * x - y) % 3 != 0) return false;
	if((2 * y - x) % 3 != 0) return false;
	return true;
}
ll dfs(ll x, ll y)
{
	if(vis[pll(x, y)]) return mp[pll(x, y)];
	if(!check(x - 1, y - 1)) return 0;
	ll aa =(2 * (x - 1) - (y - 1)) / 3;
	ll bb = (2 * (y - 1) - (x - 1)) / 3;
	ll ans = lucas(aa + bb, aa, mod);
	for(int i = 0; i < r; ++i){
		ll a = v[i].first, b = v[i].second;
		if(a >= x && b >= y) break; 
		if(!check(x - a, y - b)) continue;
		aa = (2 * (x - a) - (y - b)) / 3;
		bb = (2 * (y - b) - (x - a)) / 3;
		ans -= dfs(a, b) * lucas(aa + bb, bb, mod) % mod;
		if(ans < 0) ans += mod;
	}
	vis[pll(x, y)] = true;
	return mp[pll(x, y)] = (ans + mod) % mod;
}
int main (void)
{
	ll n, m;
	int kas = 1;
	init();
	while(~scanf("%lld%lld%d", &n, &m, &r)){
		v.clear();
		mp.clear();
		vis.clear();
		ll a, b;
		bool flag = false;
		for(int i = 0; i < r; ++i){
			scanf("%lld%lld", &a, &b);
			v.push_back(pll(a, b));
			if(a == n && b == m) flag = true;
		}
		sort(v.begin(), v.end());
		printf("Case #%d: ", kas++);
		if(flag) puts("0");
		else printf("%lld\n", dfs(n, m));
	}
	return 0;
}