Educational Codeforces Round 83 (Rated for Div. 2) D. Count the Arrays
D. Count the Arrays
time limit per test2 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
Your task is to calculate the number of arrays such that:
each array contains n elements;
each element is an integer from 1 to m;
for each array, there is exactly one pair of equal elements;
for each array a, there exists an index i such that the array is strictly ascending before the i-th element and strictly descending after it (formally, it means that aj<aj+1, if j<i, and aj>aj+1, if j≥i).
Input
The first line contains two integers n and m (2≤n≤m≤2⋅105).
Output
Print one integer — the number of arrays that meet all of the aforementioned conditions, taken modulo 998244353.
Examples
inputCopy
3 4
outputCopy
6
inputCopy
3 5
outputCopy
10
inputCopy
42 1337
outputCopy
806066790
inputCopy
100000 200000
outputCopy
707899035
Note
The arrays in the first example are:
[1,2,1];
[1,3,1];
[1,4,1];
[2,3,2];
[2,4,2];
[3,4,3].
题意：给了1~m之间的数字，让构造一个长度为n的序列
这个序列必须有一个数字重复 也就是说必须有n-1种数字
对于位置i 前面必须单调递增 后面必须单调递减 求种类数
思路：
m种数字选n-1种 第一步自然就是组合数先求出来C(m,n-1)
然后 我们考虑 重复的数字
因为峰值只能有一个 那么重复的数字一定不是最大值， 所以重复的数字的选择有n-2种
那么对于种类确定了之后，根据题意可以推断出来，重复的数字一定是在峰值的左右个一个，那么去掉这三个数后，还有n-3个数字 并且种类两两不同
对于这n-3个数 也可以说n-3种数，要么他在峰值的左边 要么在右边
其实就是2^(n-3) 种分配方式 不是左就是右 类比二进制位不是0就是1
所以答案就是C(m,n-1)*(n-2)*2^(n-3)
注意特判n==2的时候 因为这时候要选取两个 又因为题中要求要有一对一样数字 这显然不满足峰值那个要求
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll n,m;
ll qpow(ll a,ll b)
{
ll ans=1;
a%=mod;
while(b)
{
if(b&1)
ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
int main()
{
scanf("%lld%lld",&n,&m);
if(n==2) return puts("0"),0;
ll an=1,res=1;
n--;
ll nn=n;
if(nn*2>m) nn=m-nn;
for(int i=0; i<nn; i++)
{
an=an*(m-i)%mod;
res=res*(nn-i)%mod;
}
an=an%mod*qpow(res,mod-2)%mod;
an=an*(n-1)%mod*qpow(2ll,n-2)%mod;
printf("%lld\n",an);
return 0;
}
