题目链接 A Simple Chess
打表发现这其实是一个杨辉三角……
然后发现很多格子上方案数都是0
对于那写可能可以到达的点（先不考虑障碍点），我们先叫做有效的点
对于那些障碍，如果不在有效点上，则自动忽略
障碍$(A, B)$如果有效，那么就要进行如下操作：
以这个点为一个新的杨辉三角的顶点，算出目标点的坐标$(x, y)$。
目标点的答案减去$C(A, B) * C(x, y)$的值。
但是这样会造成重复计算，原因是障碍之间可能有相互影响的关系。
这个时候就要考虑容斥原理，DFS消除这些重复计算即可。
计算组合数的时候可以用两种方法，
一种是快速幂
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define fi first
#define se second
typedef long long LL;
const int N = 120010;
const int A = 210;
const LL mod = 110119;
struct node{
LL x, y;
friend bool operator < (const node &a, const node &b){
return (a.x + a.y) / 3 < (b.x + b.y) / 3;
}
} c[A];
int r, cnt;
LL x, y, n, m, nx, ny, ans;
LL fac[N], a[A], b[A], f[A][A];
inline LL Pow(LL a, LL b, LL Mod){ LL ret(1); for (; b; b >>= 1, (a *= a) %= Mod) if (b & 1) (ret *= a) %= Mod; return ret;}
inline LL C(LL n, LL m){ return m > n ? 0 : fac[n] * Pow(fac[m] * fac[n - m] % mod, mod - 2, mod) % mod; }
LL Lucas(LL n, LL m){
if (m > n / 2) m = n - m;
return m == 0 ? 1 : C(n % mod, m % mod) % mod * (Lucas(n / mod, m / mod) % mod) % mod;
}
inline LL calc(LL x, LL y){
LL n = (x + y) / 3;
LL m = y - n - 1;
return Lucas(n, m);
}
inline bool check(LL x, LL y){
if (x < 0 || y < 0 || (x + y) % 3 != 2) return false;
LL n = (x + y) / 3;
if (x < n + 1 || y < n + 1) return false;
return true;
}
void dfs(int pre, int pos, int d, LL tmp){
if (tmp == 0LL) return;
if (d & 1) ans = (ans - tmp * b[pos] % mod) % mod;
else ans = (ans + tmp * b[pos] % mod) % mod;
rep(i, pos + 1, cnt) dfs(pos, i, d + 1, tmp * f[pos][i] % mod);
}
int main(){
fac[0] = 1; rep(i, 1, N - 10) fac[i] = (fac[i - 1] * i) % mod;
int ca = 0;
while (~scanf("%lld%lld%d", &n, &m, &r)){
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
memset(c, 0, sizeof c);
memset(f, 0, sizeof f);
cnt = 0;
rep(i, 1, r){
scanf("%lld%lld", &x, &y);
if (check(x, y)){
++cnt;
c[cnt].x = x;
c[cnt].y = y;
}
}
printf("Case #%d: ", ++ca);
if (!check(n, m)){
puts("0");
continue;
}
LL x1 = (n + m) / 3, y1 = n - x1 - 1;
ans = Lucas(x1, y1);
sort(c + 1, c + cnt + 1);
rep(i, 1, cnt){
a[i] = calc(c[i].x, c[i].y);
nx = n - c[i].x + 1;
ny = m - c[i].y + 1;
if (check(nx, ny)) b[i] = calc(nx, ny);
rep(j, i + 1, cnt){
nx = c[j].x - c[i].x + 1;
ny = c[j].y - c[i].y + 1;
if (check(nx, ny)) f[i][j] = calc(nx, ny);
}
}
rep(i, 1, cnt) dfs(-1, i, 1, a[i]);
printf("%lld\n", (ans + mod) % mod);
}
return 0;
}
另一种是扩展欧几里得。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define fi first
#define se second
typedef long long LL;
const int N = 120010;
const int A = 210;
const LL mod = 110119;
struct node{
LL x, y;
friend bool operator < (const node &a, const node &b){
return (a.x + a.y) / 3 < (b.x + b.y) / 3;
}
} c[A];
int r, cnt;
LL x, y, n, m, nx, ny, ans;
LL fac[N], a[A], b[A], f[A][A];
void exgcd(LL a, LL b, LL &x, LL &y){
if (b == 0){ x = 1, y = 0; return;}
exgcd(b, a % b, x, y);
LL tmp = x; x = y; y = tmp - (a / b) * y;
}
LL C(LL n, LL m){
if (m > n) return 0LL;
if (n == m) return 1LL;
LL cnt, x, y;
cnt = m;
m = fac[n];
n = fac[cnt] * fac[n - cnt] % mod;
exgcd(n, mod, x, y);
x *= m;
x %= mod;
if (x < 0) x += mod;
return x;
}
LL Lucas(LL n, LL m){
if (m > n / 2) m = n - m;
if (m == 0) return 1;
return C(n % mod, m % mod) % mod * (Lucas(n / mod, m / mod) % mod) % mod;
}
inline LL calc(LL x, LL y){
LL n = (x + y) / 3;
LL m = y - n - 1;
return Lucas(n, m);
}
inline bool check(LL x, LL y){
if (x < 0 || y < 0 || (x + y) % 3 != 2) return false;
LL n = (x + y) / 3;
if (x < n + 1 || y < n + 1) return false;
return true;
}
void dfs(int pre, int pos, int d, LL tmp){
if (tmp == 0LL) return;
if (d & 1) ans = (ans - tmp * b[pos] % mod) % mod;
else ans = (ans + tmp * b[pos] % mod) % mod;
rep(i, pos + 1, cnt) dfs(pos, i, d + 1, tmp * f[pos][i] % mod);
}
int main(){
fac[0] = 1; rep(i, 1, N - 10) fac[i] = (fac[i - 1] * i) % mod;
int ca = 0;
while (~scanf("%lld%lld%d", &n, &m, &r)){
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
memset(c, 0, sizeof c);
memset(f, 0, sizeof f);
cnt = 0;
rep(i, 1, r){
scanf("%lld%lld", &x, &y);
if (check(x, y)){
++cnt;
c[cnt].x = x;
c[cnt].y = y;
}
}
printf("Case #%d: ", ++ca);
if (!check(n, m)){
puts("0");
continue;
}
LL x1 = (n + m) / 3, y1 = n - x1 - 1;
ans = Lucas(x1, y1);
sort(c + 1, c + cnt + 1);
rep(i, 1, cnt){
a[i] = calc(c[i].x, c[i].y);
nx = n - c[i].x + 1;
ny = m - c[i].y + 1;
if (check(nx, ny)) b[i] = calc(nx, ny);
rep(j, i + 1, cnt){
nx = c[j].x - c[i].x + 1;
ny = c[j].y - c[i].y + 1;
if (check(nx, ny)) f[i][j] = calc(nx, ny);
}
}
rep(i, 1, cnt) dfs(-1, i, 1, a[i]);
printf("%lld\n", (ans + mod) % mod);
}
return 0;
}
HDU 5794 A Simple Chess（杨辉三角+容斥原理+Lucas）
原文：http://www.cnblogs.com/cxhscst2/p/7226618.html