P6475 [NOI Online #2 入门组] 建设城市

传送门

分类讨论：
设\(f(x, y)\)为\(C^{j-1}_{i +j -1}\)

1. \(x,y\)在同一旁
   把\(x, y\)之间的看成一个高楼
   公式\(f(n,m)\times f(n+x-y,m)\)
2. \(x, y\)在异侧
   枚举\(x,y\)高楼的高度\(h\)
   \(\displaystyle \sum^{n}_{i=1}f(x-1,i)*f(n-x,m-i+1)*f(y-n-1,m-i+1)* f(2*n-y,i)\)

接着我们要处理的是\(f(x,y)\)

如何\(O(1)\)查询呢？
我们用\(O(n)\)时间预处理出阶乘逆元

fac[0] = inv[0] = 1;
for (int i = 1; i <= M; ++i) fac[i]= (fac[i - 1] * i) % MOD;
inv[M] = Qpow(inv[M], MOD - 2);
for (int i = M - 1; i >= 1; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;

查询:

int C(int n, int m)
{ return fac[m] * inv[n] % MOD * inv[m - n] % MOD; }
int f(int n, int m)
{ return C(y - 1, i + j - 1); }

code :

#include <bits/stdc++.h>

#define int long long
using namespace std;
const int inf = 0x3f3f3f3f;
const int MOD = 998244353, N = 2e5 + 5, M = 2e5;
int fac[N], inv[N], ans;

int Qpow(int x, int y)
{
    int res = 1;
    for (; y; y /= 2, (x *= x) %= MOD)
        if (y & 1) (res *= x) %= MOD;
    return res;
}

int C(int n, int m)
{ return fac[m] * inv[n] % MOD * inv[m - n] % MOD; }
int f(int i, int j)
{ return C(j - 1, i + j - 1); }


signed main()
{
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= M; ++i) fac[i]= (fac[i - 1] * i) % MOD;
    inv[M] = Qpow(fac[M], MOD - 2);
    for (int i = M - 1; i >= 1; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;

    int m, n, x, y;
    scanf("%lld%lld%lld%lld", &m, &n, &x, &y);
    if (x <= n && y > n)
        for (int i = 1; i <= m; i++)
            ans = (ans + f(x - 1, i) * f(n - x, m - i + 1) % MOD * 
                    f(2 * n - y, i) % MOD * f(y - n - 1, m - i + 1) % MOD) % MOD;
    else ans = f(n, m) * f(n + x - y, m) % MOD;
    printf("%lld", ans);
    return 0;
}