CF-1312D

66/100

题意：

给你一个数组，大小为$n$，和$1\sim m$的数，要求数组内的数满足：存在一个下标$i$满足$i$左边是单调增，$i$右边是单调减，且数组内必须且只能出现一对相同的数，问能构造多少个这样的数组，答案对998244353取模。

题解：

首先考虑取数，因为有$1$个数会重复，那么我们需要在$m$个数中取$n-1$个数，即$m\choose{n-1}$，然后我们需要在这些数中挑出一个重复，注意到最大的数不能重复，那么有$n-2$种取法，最后考虑这些数的左右问题，考虑到重复的数左右都会出现，那么有$2^{n-3}$种取法，答案就是${m\choose{n-1}}(n-2)2^{n-3}$，注意到$n=2$时会出错，需要特判。

AC代码

const int N=2e5+5;
const int MOD = 998244353;
int fac[N],invf[N];
int C(int n,int m){
  return 1ll*fac[n]*invf[m]%MOD*invf[n-m]%MOD;
}
signed main() {
  fac[0]=invf[0]=1;
  _for(int,i,1,N)fac[i]=1ll*fac[i-1]*i%MOD;
  invf[N-1]=inv(fac[N-1]);
  _rfor(int,i,N-2,0)invf[i]=1ll*invf[i+1]*(i+1)%MOD;
  int n,m;cin>>n>>m;
  if(n==2)cout<<0;
  else cout<<1ll*C(m,n-1)*(n-2)%MOD*qpow(2,n-3,MOD)%MOD;
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2021/06/16/CF-1312D/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！