[HG]提高组题解

首先很容易想到暴力DP

设状态f[i][j]表示当前放了第i个数，最大的数为j的方案数。

然后根据转移推出实际上是在下图走路的方案数

\[\left( \left( \begin{matrix}
x + y - 2 \\ x - 1
\end{matrix} \right)-
\left( \begin{matrix}
x+y-2 \\ x-2
\end{matrix} \right) \right) \times
\left(\left( \begin{matrix}
2n-x-y \\ n-x
\end{matrix} \right)-
\left( \begin{matrix}
2n-x-y \\ n-x+1
\end{matrix} \right) \right)
\]

注意：

以上情况是 \(x \leq y\) 的情况，对于\(x > y\)的情况，显然需要处理，

由于该图的对称性，我们珂以轻易地

将 \(x\) 变换为 \(n - x - 1\)；

将 \(y\) 变换为 \(n - y - 1\)。

#include <cstdio>

#define MOD 1000000007

namespace fast_IO{

    const int IN_LEN = 10000000, OUT_LEN = 10000000;

    char ibuf[IN_LEN], obuf[OUT_LEN], *ih = ibuf + IN_LEN, *oh = obuf, *lastin = ibuf + IN_LEN, *lastout = obuf + OUT_LEN - 1;

    inline char getchar_(){return (ih == lastin) && (lastin = (ih = ibuf) + fread(ibuf, 1, IN_LEN, stdin), ih == lastin) ? EOF : *ih++;}

    inline void putchar_(const char x){if(oh == lastout) fwrite(obuf, 1, oh - obuf, stdout), oh = obuf; *oh ++= x;}

    inline void flush(){fwrite(obuf, 1, oh - obuf, stdout);}

    int read(){

        int x = 0; char ch = ' ';

        while (ch < '0' || ch > '9') ch = getchar_();

        while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar_(); return x;

    }

    void write(int x){

        if (x < 0) putchar_('-'), x = -x;

        if (x > 9) write(x / 10);

        putchar_(x % 10 + '0');

    }

}

using namespace fast_IO;

long long fc[20000005];

long long ksm(long long a, long long b){

    long long res = 1;

    for ( ; b; b >>= 1, a = (a * a) % MOD)

        if (b & 1) res = (res * a) % MOD;

    return res;

}

long long getC(int a, int b){

    return fc[b] * ksm(fc[b - a], MOD - 2) % MOD * ksm(fc[a], MOD - 2) % MOD;

}

int main(){

    fc[0] = fc[1] = 1;

    for (register int i = 2; i <= 20000000; ++i)

        fc[i] = fc[i - 1] * i % MOD;

    int T = read();

    while (T--){

        long long n = read(), x = read(), y = read();

        if (x > y){

            x = n - x + 1;

            y = n - y + 1;

        }

        long long res = (getC(x - 1, x + y - 2) - getC(x - 2, x + y - 2))

                      * (getC(n - x, 2 * n - x - y) - getC(n - x + 1, 2 * n - x - y)) % MOD;

        (res < 0) && (res += MOD);

        write(res), putchar_('\n');

    }

    flush(); return 0;

}

巴特西

[HG]提高组题解

最新文章

热门文章

巴特西

[HG]提高组 题解

最新文章

热门文章

[HG]提高组题解