CF1312D Count the Arrays 题解

· · 题解

题意

已知：一个区间长度为 n，需要我们从 1\sim m 中选择一部分数字放入这个区间。

规定：必须有一个数字是重复的。存在下标 i，使得下标小于 i 的数字递增，下标大于 i 的数字递减。

提问：我们总共有多少种不同的方法来放这部分数字。

前置知识

排列组合 乘法逆元

思路

首先，我们可以想到，要使数列左半递增，右半递减。那么数列中最大值肯定位于中间位置，其中两个相同的数肯定分别位于最大值的左右两侧。

然后，因为最大值不能重复，为满足约束，我们可以想到 C^{n-1}_m，即从中选出 n-1 个数字，然后再在其中选择一个非最大值的数作为重复，即 \times (n-2) 。

接着，中间最大值已经放好了，重复数字也放好了，剩下的 n-3 个数既可以放左边也可以放右边，所以还有 2^{n-3} 种可能。

结论：答案为：C^{n-1}_m\times (n-2)\times 2^{n-3}。

Code


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> 
#include <cmath>

using namespace std;

typedef long long LL;

const int N = 3e5 + 10, mod = 998244353;

int n, m;
LL fac[N], inv[N];

LL qpow(LL a, LL b)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = res % mod * a % mod;
        a = a % mod * a % mod;
        b >>= 1; 
    }
    return res;

}

LL C(int x, int y)
{
    LL z = fac[x] % mod * inv[y] % mod;
    return z % mod * inv[x - y] % mod;
}

void init(int M = 200000)
{
    fac[0] = 1;
    for (int i = 1; i <= M; i ++ ) fac[i] = fac[i - 1] % mod * i % mod;
    inv[M] = qpow(fac[M], mod - 2);
    for (int i = M - 1; i >= 0; i -- ) inv[i] = inv[i + 1] * (i + 1) % mod; 
}

int main()
{
    init();

    scanf("%d%d", &n, &m);
    if (n < 3) puts("0");
    else printf("%lld\n", 1LL * qpow(2, n - 3) % mod * C(m, n - 1) % mod * (n - 2) % mod);

    return 0;
}