HDU5794-A Simple Chess（Lucas定理） A Simple Chess

74 阅读 0 评论 49 点赞

我是靠谱客的博主忧伤哈密瓜，最近开发中收集的这篇文章主要介绍HDU5794-A Simple Chess（Lucas定理） A Simple Chess，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A Simple Chess

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2905 Accepted Submission(s): 764

Problem Description

There is a

n×m board, a chess want to go to the position

(n,m) from the position

(1,1) .
The chess is able to go to position

(x2,y2) from the position

(x1,y1) , only and if only

x1,y1,x2,y2 is satisfied that

(x2−x1)2+(y2−y1)2=5, x2>x1, y2>y1 .
Unfortunately, there are some obstacles on the board. And the chess never can stay on the grid where has a obstacle.
I want you to tell me, There are how may ways the chess can achieve its goal.

Input

The input consists of multiple test cases.
For each test case:
The first line is three integers,

n,m,r,(1≤n,m≤1018,0≤r≤100) , denoting the height of the board, the weight of the board, and the number of the obstacles on the board.
Then follow

r lines, each lines have two integers,

x,y(1≤x≤n,1≤y≤m) , denoting the position of the obstacles. please note there aren't never a obstacles at position

(1,1) .

Output

For each test case,output a single line "Case #x: y", where x is the case number, starting from 1. And y is the answer after module

110119 .

Sample Input

Sample Output

  
  
   
   Case #1: 1
Case #2: 0
Case #3: 2
Case #4: 1
Case #5: 5

Author

UESTC

Source

2016 Multi-University Training Contest 6

Recommend

wange2014

题意：给你一个n*m的网格，问从(1, 1)走到(n, m)的方案数是多少，其中有r个障碍，障碍不能走，每次只能走”日"型

解题思路：可达点都是满足(x + y) % 3 = 2的; 路径可以看成一个斜着放置的杨辉三角。我们只需要把坐标转换一下即可，这是没有障碍时的方案数，有一个障碍，那么可以用起点到终点的方法数 - 起点到障碍点的方法数*障碍点到终点的方法数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <cmath>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

#define LL long long
const int INF = 0x3f3f3f3f;
#define mod 110119

struct node
{
	LL x, y;
	bool operator < (const node &a)const
	{
		if (x != a.x) return x < a.x;
		return y < a.y;
	}
}a[105];
LL f[120000], ans[105];

void Get_Fact()
{
	f[0] = 1;
	for (int i = 1; i <= mod; i++) f[i] = (f[i - 1] * i) % mod;
}

LL Pow(LL a, LL b)
{
	LL ans = 1;
	while (b)
	{
		if (b & 1) ans = ans*a%mod;
		b >>= 1;
		a = a*a%mod;
	}
	return ans;
}

LL C(LL n, LL m)
{
	if (m > n) return 0;
	if (m == 0) return 1;
	LL ans = f[n] * Pow(f[m], mod - 2) % mod * Pow(f[n - m], mod - 2) % mod;
	return ans;
}

LL Lucas(LL n, LL m)
{
	if (n < 0 || m < 0) return 0;
	if (m > n) return 0;
	if (m == 0) return 1;
	return C(n%mod, m%mod) * Lucas(n / mod, m / mod) % mod;
}

LL solve(LL x1, LL y1, LL x2, LL y2)
{
	if ((x1 + y1) % 3 != 2) return 0;
	if ((x2 + y2) % 3 != 2) return 0;
	LL ax = (x1 + y1 - 2) / 3;
	LL ay = y1 - 1 - ax;
	LL bx = (x2 + y2 - 2) / 3;
	LL by = y2 - 1 - bx;
	return Lucas(bx - ax, by - ay);
}

int main()
{
	Get_Fact();
	LL n, m;
	int cas = 1, r;
	while (~scanf("%lld %lld %d", &n, &m, &r))
	{
		for (int i = 1; i <= r; i++) scanf("%lld %lld", &a[i].x, &a[i].y);
		sort(a + 1, a + r + 1);
		LL sum = solve(1, 1, n, m);
		for (int i = 1; i <= r; i++)
		{
			ans[i] = solve(1, 1, a[i].x, a[i].y);
			for (int j = 1; j < i; j++)
				ans[i] = (ans[i] - ans[j] * solve(a[j].x, a[j].y, a[i].x, a[i].y) % mod + mod) % mod;
		}
		for (int i = 1; i <= r; i++) sum = (sum - ans[i] * solve(a[i].x, a[i].y, n, m) % mod + mod) % mod;
		printf("Case #%d: %lldn", cas++, sum);
	}
	return 0;
}