题解：AT_arc190_b [ARC190B] L Partition

· · 题解

记点的坐标为 (a, b)。

考虑从大到小填，发现每次相当于构造出一个 k \times k 正方形，每次填有 4 种方案，不考虑限制则总方案数为 4^{n-1}，因为最后一个怎样填都是一样的。

考虑加上限制怎么做，发现这个点一定在一个 k \times k 的正方形的边界上。进行如下分讨。

以下只考虑在其种一个角的情况，其余相同。

那么 k 级 L 型就有 3 种方法摆放使这个点在角上，考虑里面的，显然没有限制则有 4^{k-2} 种方法。考虑外面的，发现每次放都会使上下左右其中 2 个长度减 1，并且上下和左右不会同时，那么前 n-k 个 L 会使上面减 a-1，左边减 b-1。所以外面方案数为 \binom{n-k}{a-1} \times \binom{n-k}{b-1}，总方案用乘法原理乘起来即可。

以下只考虑在最上面的边的情况，其余相同。

跟上面的做法一样，容易得到 k 级 L 型方案数为 2，里面方案数为 4^{k-2}，外面方案数为 \binom{n-k}{a-1} \sum_{i=b-k+1}^{b-2} \binom{n-k}{i}。考虑预处理 f_k = {\sum_{i=b-k+1}^{b-2} \binom{n-k}{i}}。考虑组合恒等式 \binom{n}{m} = \binom{n-1}{m}+\binom{n-1}{m-1}，容易得到 f_k = \dfrac{f_{k-1} + \binom{n-k}{b-k+1} + \binom{n-k}{b-2}}{2}。递推预处理即可。

复杂度 \mathcal{O}(n+q)。

#include <bits/stdc++.h>
#define int long long
#define rd read()
using namespace std;
inline int read() {
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}
const int N = 1e7 + 5, mod = 998244353;
inline int qpow(int a, int b) {int res = 1; for (; b; b >>= 1, a = a * a % mod) if (b & 1) res = res * a % mod; return res;}
int n, a, b, fac[N], inv[N], f[N], q, pw[N], g[N], ans[N];
inline int C(int a, int b) {if (a < b || a < 0 || b < 0) return 0; return fac[a] * inv[b] % mod * inv[a - b] % mod;}
inline int solve(int x, int y, int k) {
    if (x >= 1 && y >= 1 && x <= n && y <= n) return C(n - k, x - 1) * C(n - k, y - 1) % mod * 3 * pw[k - 2] % mod;
    return 0;
}
signed main() {
    n = rd, a = rd, b = rd, q = rd; fac[0] = pw[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod, pw[i] = pw[i - 1] * 4 % mod;
    inv[n] = qpow(fac[n], mod - 2); for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
    int inv2 = qpow(2, mod - 2);
    bool f1 = 0, f2 = 0;
    for (int k = 1; k <= n; ++k) {
        if (b - k + 1 <= b - 2 && !f1) {
            for (int i = b - k + 1; i <= b - 2; ++i) f[k] = (f[k] + C(n - k, i)) % mod; 
            f1 = 1;
        } else if (f1) f[k] = (f[k - 1] + C(n - k, b - k + 1) + C(n - k, b - 2)) * inv2 % mod;
        if (a - k + 1 <= a - 2 && !f2) {
            for (int i = a - k + 1; i <= a - 2; ++i) g[k] = (g[k] + C(n - k, i)) % mod; 
            f2 = 1;
        } else if (f2) g[k] = (g[k - 1] + C(n - k, a - k + 1) + C(n - k, a - 2)) * inv2 % mod;
        if (k == 1)ans[k] = C(n - k, a - 1) * C(n - k, b - 1) % mod;
        else {
            ans[k] = (ans[k] + solve(a, b, k)) % mod;
            ans[k] = (ans[k] + solve(a - k + 1, b, k)) % mod;
            ans[k] = (ans[k] + solve(a, b - k + 1, k)) % mod;
            ans[k] = (ans[k] + solve(a - k + 1, b - k + 1, k)) % mod;
            ans[k] = (ans[k] + C(n - k, a - 1) * f[k] % mod * 2 * pw[k - 2] % mod) % mod;
            ans[k] = (ans[k] + C(n - k, a - k) * f[k] % mod * 2 * pw[k - 2] % mod) % mod;
            ans[k] = (ans[k] + C(n - k, b - 1) * g[k] % mod * 2 * pw[k - 2] % mod) % mod;
            ans[k] = (ans[k] + C(n - k, b - k) * g[k] % mod * 2 * pw[k - 2] % mod) % mod;
        }
    }
    while (q--) cout << ans[rd] << '\n';
    return 0; 
}