当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

注意到其实只有这 4 种骨牌是实际有效的

把原来的题意转化为这样:我们可以往角落依次里堆骨牌,可以放当且仅当其每个格子的左边和右边都被填满或是边界,最后要堆成一个 n \times m 的矩形。

把轮廓线提出来,一段自下而上走的记为 0 ,自左向右走的记为 1 。显然一开始为 n 个 0 连着 m 个 1 ,最后要变成 m 个 1 连着 n 个 0 。

考虑到四种图形对应的变换如下

before transformation after transformation image
0001 1000
0011 1010
0101 1100
0111 1110

发现中间的 2 个二进制位都是固定的,变化的只有第四位的 1 跑到了第一位去。

于是我们又可以转换题意,每次可以选择一个 1 ,然后把它向前移 3 格。分模 3 意义下讨论,每一部分就变成了杨氏矩阵计数,可以用钩子公式解决。

定义杨表的钩子为在这个格正下方和正右方的格子个数。钩子公式对于由 n 个格子组成的杨表,给其标号的方案数为 n! 除以每个格子的钩子大小 + 1 。

参考资料

代码

// =================================
//   author: memset0
//   date: 2019.07.11 17:41:52
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define rep(i, l, r) for (int (i) = (l), __lim = (r); (i) <= __lim; (i)++)
#define for_each(i, a) for (size_t i = 0, __lim = a.size(); i < __lim; ++i)
namespace ringo {

template <class T> inline void read(T &x) {
  x = 0; char c = getchar(); bool f = 0;
  while (!isdigit(c)) f ^= c == '-', c = getchar();
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
  if (f) x = -x;
}
template <class T> inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) print(x / 10);
  putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }
template <class T> inline void print(T a, int l, int r, std::string s = "") {
  if (s != "") std::cout << s << ": ";
  for (int i = l; i <= r; i++) print(a[i], " \n"[i == r]);
}

const int N = 2e4 + 10, NN = 34000000, mod = 1e9 + 7;
int T, n, m, ans, inv[N], _n[3], _m[3], fac[NN];

inline int dec(int a, int b) { a -= b; return a < 0 ? a + mod : a; }
inline int inc(int a, int b) { a += b; return a >= mod ? a - mod : a; }
inline int mul(int a, int b) { return (ll)a * b - (ll)a * b / mod * mod; }

inline int get_inv(int x) {
  if (x < 2) return 1;
  return 1ll * (mod - mod / x) * get_inv(mod % x) % mod;
}

inline int fpow(int a, int b) {
  int s = 1;
  for (; b; b >>= 1, a = mul(a, a))
    if (b & 1) s = mul(s, a);
  return s;
}

inline int calc(int n, int m) {
  int ans = 1;
  for (int i = 2; i <= n + m; i++) {
    ans = mul(ans, fpow(inv[i - 1], std::min(n, i - 1) - std::max(1, i - m) + 1));
  }
  return ans;
}

void main() {
  fac[0] = inv[0] = inv[1] = 1;
  for (int i = 2; i < N; i++) inv[i] = mul(mod - mod / i, inv[mod % i]);
  for (int i = 1; i < NN; i++) fac[i] = mul(fac[i - 1], i);
  for (read(T); T--; ) {
    read(n), read(m);
    for (int i = 0; i < 3; i++) {
      _n[i] = n <= i ? 0 : (n - i - 1) / 3 + 1;
      _m[i] = (n + m <= i ? 0 : (n + m - i - 1) / 3) - (n <= i ? 0 : (n - i - 1) / 3);
    }
    // printf("> %d %d %d %d %d %d\n", _n[0], _m[0], _n[1], _m[1], _n[2], _m[2]);
    ans = fac[_n[0] * _m[0] + _n[1] * _m[1] + _n[2] * _m[2]];
    ans = 1ll * ans * calc(_n[0], _m[0]) % mod;
    ans = 1ll * ans * calc(_n[1], _m[1]) % mod;
    ans = 1ll * ans * calc(_n[2], _m[2]) % mod;
    print(ans, '\n');
  }
}

} signed main() {
#ifdef memset0
  freopen("1.in", "r", stdin);
#endif
  return ringo::main(), 0;
}

巧妙的思路 钩子定理 杨表 二进制转换 Favorite

仅有一条评论

  1. 此处的杨表可能和别的地方定义的杨表有点不大一样,我是从左上角开始放 QAQ

NOI 模拟赛 20190711A 刀剑传奇
上一篇 «
LOJ6627 等比数列三角形
» 下一篇