codeforces-Ed83-D

codeforces-Ed83-D

七月 08, 2020

D. Count the Arrays

题意

构造一个长度n的序列

要求每个数都是在1到m数中的一个

序列中只有一对数相等

这个序列必须先严格递增 再严格递减

现在给出n和m 问能构造出多少个符合这种要求的序列

题解见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# include<bits/stdc++.h>

using namespace std;
typedef long long ll;

# define endl '\n'

const ll mod=998244353;
const ll maxn=2e5+5;
ll fac[maxn];
ll qpow(ll x,ll y){
    ll ans=1;
    while(y){
        if(y&1)ans=(ans*x)%mod;
        x=(x*x)%mod;y>>=1;
    }
    return ans;
}
ll C(ll x,ll y){return ((fac[x]*qpow(fac[y],mod-2)%mod)*qpow(fac[x-y],mod-2))%mod;}
int main(){
    ll n,m;cin>>n>>m;fac[1]=1;
    for(ll i=2;i<maxn;i++)fac[i]=(fac[i-1]*i)%mod;
    ll ans;
    /// 从m个数中选出n-1个不同的数 
    ///从n-1个数中选出成对的那个数有(n-2)种
    ///最大的那个数不能成对否则不能满足严格先递增后递减
    ///其次所有数要么在最大数的左边要么右边 成对的那个数两边都有
    ///因为剩下的数都是唯一的 决定放在哪一侧后一定存在唯一的排序方式 
    ///所以再乘上2^(n-3) (原来有n-1个数 去掉最大的那个数 去掉重复的那个数 剩下n-3个数要选择在右边或左边)
    if(n>2)ans=((C(m,n-1)*(n-2))%mod*qpow(2,n-3))%mod;
    else ans=(C(m,n-1)*(n-2)/2)%mod;
    cout<<ans<<endl;
}