P6561 人

masonpop · 2022-12-09 09:02:38 · 个人记录

其实是一个结论题，做法有很多种，这里介绍一种最神奇最易懂的。

• 首先，我们把问题转化一下，设相邻两个数为一"组",有 m 组。则每组最多选择一个数。
• 我们设一组中，选择第一个数(即奇数)为 "A选择"，第二个数为 "B 选择"，都不选为 "C选择"。那么就是让你求把 a 个 A,b 个 B, m-a-b 个 C 排成一排，且不能有 BA 型组合的方案数。
• 首先考虑排列 B,C. 没有限制，因此就是 C_{m-a}^b.
• 然后考虑插入 a 个 A.原本有 m-a+1 个位置，由于 b 个 B 后面不能填 A,因此就是求在 m-a-b+1 个位置中填入 a 个 A 的方案数。
• 考虑隔板法。由于可以不放，因此方案数就是

  C_{m-a-b+1+a-1}^{m-a-b+1-1}=C_{m-b}^{m-a-b}=C_{m-b}^{a}.

• 所以答案就是

  C_{m-b}^a\times C_{m-a}^b.

• 然后预处理一下阶乘的逆元和阶乘就行了。

  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  const int mod=998244353;
  const int maxn=1e6+10;
  int t;
  inline int qpow(int x,int y)//快速幂 
  {
  int res=1;
  while(y)
  {
      if(y&1)res=res*x%mod;
      x=x*x%mod;
      y>>=1;
  }
  return res;
  }
  int fac[maxn],inv[maxn];//inv[i]:inv(i!)
  inline int C(int n,int m)
  {
  if(n<m)return 0;
  return fac[n]*inv[n-m]%mod*inv[m]%mod;
  }
  signed main()
  {
  scanf("%lld",&t);
  fac[0]=1;
  for(int i=1;i<=maxn-10;i++)fac[i]=fac[i-1]*i%mod;
  inv[maxn-10]=qpow(fac[maxn-10],mod-2);
  for(int i=maxn-10-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
  while(t--)
  {
      int m,a,b;
      scanf("%lld%lld%lld",&m,&a,&b);
      printf("%lld\n",C(m-a,b)*C(m-b,a)%mod);
  }
  return 0;
  }