Solution #

First of all, there will be $n-1$ distinct elements in the array and there are $m\choose{n-1}$ ways to choose.

Next, there are $n-2$ elements we could choose to duplicate. Finally, some elements will appear before the maximum and some will appear after. However, the duplicated elements will appear on both sides, so there are $2^{n-3}$ ways to choose their positions.

In summary, the answer is ${{m}\choose{n - 1}} (n - 2)2^{n - 3}$ .

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define de(x) cout<<#x<<" = "<<(x)<<endl
#define de2(x,y) cout<<#x<<" = "<<(x) <<' '<< #y<<" = "<<y<<endl;
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int mod=998244353;
ll bipow(ll a,int b){
	ll ans=1;
	for(;b;b>>=1){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	if(n==2) return cout<<0,0;
	ll ans=1,r=1;
	for1(i,m) ans=ans*i%mod;
	for1(i,n-1) r=r*i%mod;
	for1(i,m-n+1) r=r*i%mod;
	ans=ans*bipow(r,mod-2)%mod*(n-2)%mod;
	ans=ans*bipow(2,n-3)%mod;
	cout<<ans;
    return 0;
}

Solution for CodeForces 1312D - Count the Arrays

Solution #

Code #