传送门

  • 题目:
  • 思路:
    n个元素有一对相同的,那么n个数***有n-1个不同的数,从m个数中选n-1,方法数: C m n 1 C_m^{n-1} Cmn1
    从n-1个不同的数中选择一个数使其在要构造的数组中出现两次,最大的数是唯一的,不能选它,所以方法数为:n-2
    除了重复出现的数一个在最大数的左边,一个在右边外,其他n-3个数可以出现在最大数的左边/右边,方法数为: 2 n 3 2^{n-3} 2n3
    a n s = C m n 1 ( n 2 ) 2 n 3 ans=C_m^{n-1}*(n-2)*2^{n-3} ans=Cmn1(n2)2n3,注意用逆元求解。
  • ac代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
const ll mod = 998244353;
ll n, m;
ll fac[maxn], p2[maxn];
ll qpow(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b&1) ans = ans*(a%mod)%mod;
        a = (a%mod)*(a%mod)%mod;
        b >>= 1;
    }
    return ans%mod;
}
void pre()
{
    fac[0] = p2[0] = 1;
    for(ll i = 1; i <= 2e5; i++)
    {
        fac[i] = fac[i-1]*i%mod;
        p2[i] = p2[i-1]*2%mod;
    }
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%lld %lld", &n, &m);
    if(n==2) printf("0");
    else
    {
        pre();
        ll di = fac[n-1]*fac[m-n+1]%mod;
        ll ans = fac[m]*(n-2)%mod*p2[n-3]%mod*qpow(di, mod-2)%mod;
        printf("%lld", ans);
    }
    return 0;
}