D. Count the Arrays （思维 + 简单数学）

题目：传送门

题意：问有多少长度为 n 的序列，满足：

1、序列上的每个元素 ai 都满足 1 <= ai <= m

2、恰好只有一对元素相等

3、存在一个下标 i 使得 aj<aj+1, if j<i, and aj>aj+1, if j≥i

 

思路：

长度为 n 的序列，且恰好有一对数相等，那么就有 n - 1 个不同的元素，每个元素都介于 1~m，那有 C(n - 1, m) 种方式取 n - 1 个不同的数。

恰有一对相等的元素，相等的数不能是最大的数，其他的都可以，那相等的数就有 (n - 2) 种取法。

由 n 个不同的数组成的长度为 n 的满足条件 3 的序列总共有 2^(n-1) 种。

相等的数肯定位于最大值的两侧，其他的数没限制，则最大值不能在两侧，且互不相等的 n - 2 个数若已放置好，则相等的那对数的位置也随之确定。

所以满足条件 3 的有 2^(n - 3) 种，腾出两侧作为空位，其他数确定下来后，再填上相等的两个数。

#include <bits/stdc++.h>
#define LL long long
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF INT_MAX
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
using namespace std;

const int mod = 998244353;

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

LL C(int n, int m) {
    LL resdw1 = 1;
    rep(i, 1, n) resdw1 = resdw1 * i % mod;
    LL resdw2 = 1;
    rep(i, 1, m - n) resdw2 = resdw2 * i % mod;
    LL resup = 1;
    rep(i, 1, m) resup = resup * i % mod;
    return resup * ksm(resdw1, mod - 2) % mod * ksm(resdw2, mod - 2) % mod;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    if(n == 2) puts("0");
    else {
        LL ans = ksm(2LL, n - 3) * 1LL * (n - 2) % mod * C(n - 1, m) % mod;
        printf("%lld
", ans);
    }
    return 0;
}