小兔的话

欢迎大家在评论区留言哦~

简单题意

有一个 \(n \times m\) 的棋盘，规定左上角的方格的坐标为 \((1, 1)\)，右下角的方格的坐标为 \((n, m)\)，其中有 \(r\) 个障碍物，每个障碍物的坐标是 \((x_i, y_i)\)。
当一颗棋子的坐标为 \((x, y)\) 时，下一步可以走到 \((x + 1, y + 2)\) 或者 \((x + 2, y + 1)\)。
现在 \((1, 1)\) 上有一颗棋子，请求出它走到 \((n, m)\) 不经过障碍物的方案数 \((\) 对 \(110119\) 取模 \()\)，特别地，如果方格 \((1, 1)\) 上有障碍物，方案数应该为 \(0\)。

数据范围

• \(1 \leq n, m \leq 10^{18}\)，\(1 \leq r \leq 100\)
• \(\forall \ 1 \leq i \leq r\)，\(1 \leq x_i \leq n, 1 \leq y_i \leq m\)

题目解析

• 把 \((x, y)\) 走到 \((x + 1, y + 2)\) 记为类型 \(1\)。
• 把 \((x, y)\) 走到 \((x + 2, y + 1)\) 记为类型 \(2\)。

考虑一个格子向右走了 \(N\) 个单位长度，向下走了 \(M\) 个单位长度的方案数，记为 \(f(N, M)\)。

设类型 \(1\) 的步骤有 \(x\) 个，类型 \(2\) 的步骤有 \(y\) 步，那么方案数就是 \(\dbinom {x + y} {x}\)（由于 \(n, m\) 可能很大，所以 \(x, y\) 也可能很大，因此组合数对 \(110119\) 取模的值不能使用常规做法求解，可以使用 \(\texttt {Lucas}\) 定理）。
由于棋盘的限制，\(x, y\) 需要满足一定的条件：

• \(x, y\) 都是 非负整数
• \(x + 2y = N\)
• \(2x + y = M\)

\(\therefore x = \dfrac {2M - N} {3}\)，\(y = \dfrac {2N - M} {3}\)

只需要判断 \(x, y\) 是否都是非负整数即可。

对于 \((1, 1)\) 走到 \((n, m)\) 不经过障碍物的方案数，可以用总方案减去经过障碍物的方案数。
总方案为 \(f(n - 1, m - 1)\)，只需要考虑经过障碍物的方案数即可。
考虑到达每个障碍物之前没有经过其它的障碍物的方案数 \(dp_i\)，\(dp\) 的和就是经过障碍物的方案数了，其对答案的贡献就是 \(dp_i \times f(n - x_i, m - y_i)\)。

对于第 \(i\) 障碍物，若到达它之前还经过了第 \(j\) 个障碍物，那么一定满足 \(x_j < x_i\) 并且 \(y_j < y_i\)。
所以 \(dp_i = f(x_i - 1, y_i - 1) \times \sum \limits _ {x_j < x_i \land y_j < y_i} dp_j\)
求解过程中可以先将障碍物按照 \((x, y)\) 排序，这样就只用算 \(1 \leq j \leq i - 1\) 对 \(i\) 的影响了。

代码

#include 
#include 
using namespace std;

#define int long long
#define uint unsigned int

int rint()
{
	int x = 0, fx = 1; char c = getchar();
	while (c < '0' || c > '9') { fx ^= (c == '-'); c = getchar(); }
	while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
	if (!fx) return -x;
	return x;
}

int qpow(int a, int b, int mod)
{
	int res = 1 % mod; a %= mod;
	while (b > 0)
	{
		if (b & 1) res = res * a % mod;
		a = a * a % mod; b >>= 1;
	}
	return res;
}

const int mod = 110119;
const int mx = mod - 1;
const int MAX_r = 100;

int dp[MAX_r + 5];
int f[mx + 5], inv[mx + 5];

struct node
{
	int x, y;
	node () {}
	bool operator < (const node &rhs) const
	{
		if (x != rhs.x) return x < rhs.x;
		return y < rhs.y;
	}
} p[MAX_r + 5];

void init()
{
	f[0] = 1; for (int i = 1; i <= mx; i++) f[i] = f[i - 1] * i % mod;
	inv[mx] = qpow(f[mx], mod - 2, mod); for (int i = mx; i >= 1; i--) inv[i - 1] = inv[i] * i % mod;
}

int A(int N, int M) { return (N < M || M < 0) ? 0 : (f[N] * inv[N - M] % mod); }
int C(int N, int M) { return A(N, M) * inv[M] % mod; }

int Lucas(int N, int M)
{
	int res = 1;
	while (N || M)
	{
		res = res * C(N % mod, M % mod) % mod;
		if (!res) return 0;
		N /= mod; M /= mod;
	}
	return res;
}

int calc(int N, int M) // 计算 f(N, M) 
{
	int x = 2 * N - M, y = 2 * M - N;
	if (x % 3 || y % 3 || x < 0 || y < 0) return 0;
	return Lucas(x / 3 + y / 3, x / 3);
}

signed main()
{
	int Case = 0, n, m, r; init();
	while (scanf("%lld %lld %lld", &n, &m, &r) != EOF)
	{
		for (int i = 1; i <= r; i++)
			p[i].x = rint(), p[i].y = rint();
		sort(p + 1, p + r + 1);
		int res = calc(n - 1, m - 1);
		for (int i = 1; i <= r; i++)
		{
			dp[i] = calc(p[i].x - 1, p[i].y - 1);
			for (int j = 0; j < i; j++)
				if (p[j].x < p[i].x && p[j].y < p[i].y) dp[i] = (dp[i] - dp[j] * calc(p[i].x - p[j].x, p[i].y - p[j].y) % mod + mod) % mod;
			res = (res - dp[i] * calc(n - p[i].x, m - p[i].y) % mod + mod) % mod;
		}
		printf("Case #%lld: %lld\n", ++Case, res);
	}
	return 0;
}