专栏文章

AT ARC202B Japanese "Knight's Tour"

rrizynvu
AT_arc202_b题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miostcre
此快照首次捕获于
2025/12/03 00:34
3 个月前
此快照最后确认于
2025/12/03 00:34
3 个月前
查看原文
cnblogs。
每一步移动为 (−2,±1)(-2, \pm 1)，所以行的变化一定是每次 −2-2。
又因为每一行肯定需要能被走到，于是有 2∤H2\nmid H，即 HH 为奇数。
当 HH 为奇数时，把这个行的顺序记录下来，就可以当作每一步移动是 (−1,±1)(-1, \pm 1) 了。
考虑把这个过程定向，因为每一个位置都会被恰好经过一次且最后会成环，所以可以知道每个位置一定有一个前驱一个后继。
又因为前驱后继的行数其实是确定的（当前行数 +1,−1+1, -1），所以可以分开各个行间的连边情况最后考虑合并。
考虑行间连边会成什么形态，不难发现只有以下 44 种（变量都是表示的列数，在  mod W\bmod W 意义下）：
  • ∀i∈[0,W−1],i→i+1\forall i\in [0, W - 1], i\to i + 1。
  • ∀i∈[0,W−1],i→i−1\forall i\in [0, W - 1], i\to i - 1。
  • 当 2∣W2 \mid W 时，∀i∈[0,W2−1],2i→2i+1,2i+1→2i\forall i\in [0, \frac{W}{2} - 1], 2i\to 2i + 1, 2i + 1\to 2i。
  • 当 2∣W2 \mid W 时，∀i∈[0,W2−1],2i−1→2i,2i→2i−1\forall i\in [0, \frac{W}{2} - 1], 2i - 1\to 2i, 2i\to 2i - 1。
同时会发现我们只关心能不能遍历完所有的 (0,i)(0≤i<W)(0, i)(0\le i < W)，因为能遍历到这些点根据限制也就能遍历到所有的点。
先来考虑 2∤W2\nmid W，即 WW 为奇数的情况。
行间连边的差距只会是 ±1\pm 1，假设表示 (0,i)(0, i) 会走到 (0,j)(0, j)，记 di=j−id_i = j - i。
可以知道所有 did_i 应当相同，为行间差距的和（即 +1+1 的数量减掉 −1-1 的数量），并且合法当且仅当 gcd⁡(d0,W)=1\gcd(d_0, W) = 1。
于是可以枚举 d0d_0，对应的方案数就是 (HH+d02)\dbinom{H}{\frac{H + d_0}{2}}。
接下来考虑 2∣W2 \mid W，即 WW 为偶数的情况。
依然记 did_i。
此时会发现因为存在第 3,43, 4 种情况的干扰，did_i 或许并不是全部相同的了。
不过会发现：对于 did_i 递推的过程，会发现若 i+dii + d_i 的奇偶性相同，did_i 的变换量也是相同的。
于是可以知道，奇数的 ii 的 did_i 一定相同，偶数的 ii 的 did_i 一定相同。
考虑此时的 d0,d1d_0, d_1 要满足什么限制：
  • gcd⁡(d0,W)=1\gcd(d_0, W) = 1。
  • gcd⁡(d1,W)=1\gcd(d_1, W) = 1。
  • gcd⁡(d0+d1,W)=2\gcd(d_0 + d_1, W) = 2，这个的意义是把 2i2i 和 2i+d02i + d_0 捆绑，当作是 2i→2i+d0+d12i\to 2i + d_0 + d_1，要求所有偶数也得成一个环，gcd⁡(d0+d12,W2)=1\gcd(\frac{d_0 + d_1}{2}, \frac{W}{2}) = 1 这个形式或许更直观。
发现因为 2∤H2\nmid H，所以 2∤d0,2∤d12\nmid d_0, 2\nmid d_1，所以前两个限制一定满足。
那么只需要考虑最后一个限制了，依然可以考虑枚举 d0+d1d_0 + d_1 的值，考虑计数。
发现能够把四种可能的情况分析为：d0d_0 可以选择 ±1\pm 1，d1d_1 可以选择 ±1\pm 1（任意一种情况的组合一定存在）。
于是可以看作是一个长度 2H2H 的折线，每一步都是 ±1\pm 1，最后值为 d0+d1d_0 + d_1，方案数就为 (2HH+d0+d12)\dbinom{2H}{H + \frac{d_0 + d_1}{2}}。
时间复杂度为 O(Hlog⁡W)\mathcal{O}(H\log W)，因为涉及到求 gcd⁡\gcd。
实现中 WW 为偶数的情况枚举的是 d0+d12\frac{d_0 + d_1}{2}。
C
// 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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...