题目：传送门
题意：问有多少长度为 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\n", ans); } return 0; }
D. Count the Arrays （思维 + 简单数学）
原文：https://www.cnblogs.com/Willems/p/12465248.html