牛客练习赛 113F 小红的好子序列（easy）题解

因为 $nn$ 比较小，考虑枚举子序列长度 $ll$。

开个 std::map 记录每一种数出现的次数；令 $xx$ 的出现次数为 $c_{x}c\_x$，则 $xx$ 可以成为出现次数不小于一半的那个数的充要条件即为 $c_x\ge \lceil \frac{l}{2}\rceil c\_x\backslash ge\backslash left\backslash lceil\backslash frac\{l\}\{2\}\backslash right\backslash rceil$，再枚举其在子序列中的出现次数 $tt$（从 $\lceil \frac{l}{2}\rceil \backslash left\backslash lceil\backslash frac\{l\}\{2\}\backslash right\backslash rceil$ 枚举到 $c_{x}c\_x$），则根据乘法原理，方案数为 $C_{c_x}^t\cdot C_{n-c_x}^{l-t}C\_\{c\_x\}^t\backslash cdot\; C\_\{n-c\_x\}^\{l-t\}$（注意可能出现 的情况，直接判掉，这一部分答案即为 $00$）。

但是上面的解法可能导致 $ll$ 为偶数时，枚举到两个不同的 $x_1,x_{2}x\_1,x\_2$（出现次数不小于一半的数）时导致 $x_1,x_{2}x\_1,x\_2$ 各出现一半的情况被计算两次。这个只需要在枚举到 $xx$ 时，枚举比 $xx$ 小且可能与 $xx$ 导致上述情况的 $yy$，将答案减去 $C_{c_x}^{i\mathrm{/}2}\cdot C_{c_y}^{i\mathrm{/}2}C\_\{c\_x\}^\{i/2\}\backslash cdot\; C\_\{c\_y\}^\{i/2\}$。记得作减法时加上模数再取模，防止产生负数。

组合数取模的计算可以使用费马小定理求解模意义下的乘法逆元。预处理出阶乘 $f_x=x!f\_x=x!$，$C_n^{m}C\_n^m$ 的值即为 $\frac{f_n}{f_m\cdot f_{n-m}}\backslash frac\{f\_n\}\{f\_m\backslash cdot\; f\_\{n-m\}\}$。

参考实现代码（C++17）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[200001];
const int mod=1e9+7;
int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=r%mod*a%mod;
    a=a%mod*a%mod; b>>=1;
  }
  return r;
}
int inv(int x){
  return qpow(x,mod-2);
}
int com(int n,int m){
  if(m>n||m<0||n<0)return 0;
  return f[n]*inv(f[m]*f[n-m]%mod)%mod;
}
signed main(){
  ios::sync_with_stdio(false);
  int n,c; cin>>n; c=n;
  for(int i=f[0]=1;i<=n;i++)
    f[i]=f[i-1]*i%mod;
  map<int,int> m;
  for(int i=1;i<=n;i++){
    int x; cin>>x; m[x]++;
  }
  for(int i=2;i<=n;i++)
    for(auto [x,y]:m)
      if(y>=(i+1>>1)){
        for(int j=i+1>>1;j<=y;j++)
          (c+=com(y,j)*com(n-y,i-j)%mod)%=mod;
        if(~i&1)
          for(auto [x2,y2]:m){
            if(x==x2)break;
            (c+=mod-com(y,i>>1)*com(y2,i>>1)%mod)%=mod;
          }
      }
  cout<<c<<endl;
  return 0;
}