AT ARC202B Japanese "Knight's Tour"

· · 题解

cnblogs。

每一步移动为 (-2, \pm 1)，所以行的变化一定是每次 -2。
又因为每一行肯定需要能被走到，于是有 2\nmid H，即 H 为奇数。

当 H 为奇数时，把这个行的顺序记录下来，就可以当作每一步移动是 (-1, \pm 1) 了。

考虑把这个过程定向，因为每一个位置都会被恰好经过一次且最后会成环，所以可以知道每个位置一定有一个前驱一个后继。

又因为前驱后继的行数其实是确定的（当前行数 +1, -1），所以可以分开各个行间的连边情况最后考虑合并。

考虑行间连边会成什么形态，不难发现只有以下 4 种（变量都是表示的列数，在 \bmod W 意义下）：

同时会发现我们只关心能不能遍历完所有的 (0, i)(0\le i < W)，因为能遍历到这些点根据限制也就能遍历到所有的点。

先来考虑 2\nmid W，即 W 为奇数的情况。

行间连边的差距只会是 \pm 1，假设表示 (0, i) 会走到 (0, j)，记 d_i = j - i。

可以知道所有 d_i 应当相同，为行间差距的和（即 +1 的数量减掉 -1 的数量），并且合法当且仅当 \gcd(d_0, W) = 1。

于是可以枚举 d_0，对应的方案数就是 \dbinom{H}{\frac{H + d_0}{2}}。

接下来考虑 2 \mid W，即 W 为偶数的情况。

依然记 d_i。

此时会发现因为存在第 3, 4 种情况的干扰，d_i 或许并不是全部相同的了。

不过会发现：对于 d_i 递推的过程，会发现若 i + d_i 的奇偶性相同，d_i 的变换量也是相同的。
于是可以知道，奇数的 i 的 d_i 一定相同，偶数的 i 的 d_i 一定相同。

考虑此时的 d_0, d_1 要满足什么限制：

发现因为 2\nmid H，所以 2\nmid d_0, 2\nmid d_1，所以前两个限制一定满足。

那么只需要考虑最后一个限制了，依然可以考虑枚举 d_0 + d_1 的值，考虑计数。
发现能够把四种可能的情况分析为：d_0 可以选择 \pm 1，d_1 可以选择 \pm 1（任意一种情况的组合一定存在）。
于是可以看作是一个长度 2H 的折线，每一步都是 \pm 1，最后值为 d_0 + d_1，方案数就为 \dbinom{2H}{H + \frac{d_0 + d_1}{2}}。

时间复杂度为 \mathcal{O}(H\log W)，因为涉及到求 \gcd。

实现中 W 为偶数的情况枚举的是 \frac{d_0 + d_1}{2}。

// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using ll = long long;

constexpr ll mod = 998244353;
constexpr ll inv2 = (mod + 1) / 2;

inline ll qpow(ll a, ll b) {
    ll v = 1;
    for (; b; b >>= 1, a = a * a % mod) {
        if (b & 1) v = v * a % mod;
    }
    return v;
}

constexpr int maxH = 4e5 + 10;

ll fac[maxH], ifac[maxH];
inline ll binom(int n, int m) {
    return fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}

int main() {
    int H, W;
    scanf("%d%d", &H, &W);

    if (H % 2 == 0) return puts("0"), 0;

    fac[0] = 1;
    for (int i = 1; i <= H * 2; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    ifac[H * 2] = qpow(fac[H * 2], mod - 2);
    for (int i = H * 2; i >= 1; i--) {
        ifac[i - 1] = ifac[i] * i % mod;
    }

    ll ans = 0;
    if (W % 2 == 1) {
        for (int i = -H; i <= H; i += 2) {
            if (std::__gcd(std::abs(i), W) != 1) continue;
            (ans += binom(H, (H + i) / 2)) %= mod;
        }
    } else {
        for (int i = -H; i <= H; i++) {
            if (std::__gcd(std::abs(i), W / 2) != 1) continue;
            (ans += binom(H * 2, H + i)) %= mod;
        }
    }

    printf("%lld\n", ans);

    return 0;
}