首页 > 代码库 > HDU 5794 A Simple Chess（杨辉三角+容斥原理+Lucas）
HDU 5794 A Simple Chess（杨辉三角+容斥原理+Lucas）
题目链接 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 secondtypedef 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 secondtypedef 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）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。