ARC096E题解

TempestMiku · 2023-08-03 16:40:49 · 题解

题目传送门

今天模拟赛考了这道题，然后保龄了。

思路

• 首先可以对第二个限制做二项式反演：

设 f[i] 为钦定 i 种配料出现次数小于等于 1 的方案数。

那么就有 ans=\sum_{i=0}^{n}{(-1)^{i}}{C_n^i}{f[i]}。

• 考虑计算 f[i]：

首先枚举出现次数小于等于 1 次的配料中有几个配料出现了和有几碗面中出现了这些配料，设有 j 个配料出现在了 k 碗面中。

那么容易想到第二类斯特林数。

第二类斯特林数 \operatorname{S2}(n,m) 表示的是把 n 个不同元素划分到 m 个集合的方案数。表示为 n \brace m。

将 j 个不同元素划分到 k 个集合中，即为 k \brace j。

斯特林数处理的是只能是非空集合，所以先考虑所有数都加入集合的情况，即为k \brace j ，然后考虑有数没有加入集合的情况，我们可以加入一个第 k+1 集合，把 1 到 k 都不放元素的元素加入这个集合中，然后每个集合都可以是第 k+1 个集合，所以方案数为 {(j+1)}\times {{k+1} \brace j }。

另外，这 k 种面的其他配料可以随便加而不用担心出现重复的碗，方案数即为 2^{{n-i}^{k}}。

题目中说有 n 种元素,总共有 2^{n} 种集合，去掉已经钦定的 i 种元素之后，剩下 2^{n-i} 种集合。对于 i 个元素之外的 n-i 个数组成的 2^{n-i} 个集合可以选也可以不选，所以是 2^{2^{n-i}} 种方案。 这里有一个细节就是幂次的处理需要用费马小定理。

• 所以答案表达式即为：

预处理出斯特林数后 O(n^2+logP) 计算即可。

• 代码：

  #include<bits/stdc++.h>
  using namespace std;
  #define int long long
  namespace Testify{
  inline int read(){
      int f(1),x(0);
      char ch=getchar();
      for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
      for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
      return f*x;
  }
  inline void Write(int x){
      if(x>9) Write(x/10);
      putchar(x%10+'0');
  }
  inline void write(int x){
      if(x<0) putchar('-'),x=-x;
      Write(x);
      putchar('\n');
  }
  }
  using namespace Testify;
  // const int mod=1e9+7;
  int mod;
  const int N=5555;
  int n,m,fac[N],inv[N],S[N][N];
  inline int qpow(int a,int b,int mod){
  int res=1;
  while(b){
      if(b&1) res=res*a%mod;
      b>>=1;
      a=a*a%mod;
  }
  return res;
  }
  inline int C(int n,int m){
  if(n<m) return 0;
  return ((fac[n]%mod*inv[n-m]%mod)%mod*inv[m]%mod)%mod;
  }
  signed main(void){
  n=read(),mod=read();
  fac[0]=inv[0]=1;
  for(register int i=1;i<=n;i++){
      fac[i]=fac[i-1]*i%mod;
      inv[i]=inv[i-1]*qpow(i,mod-2,mod)%mod;
  }
  S[0][0]=1;
  for(register int i=1;i<=n+1;i++){//加一是因为下面可能用到j+1
      for(register int j=1;j<=i;j++){
          S[i][j]=(S[i-1][j-1]+S[i-1][j]*j%mod)%mod;
      }
  }
  int Tempestissimo(0);
  for(register int i=0;i<=n;i++){//枚举第i个元素
      int tmp(0);
      for(register int j=0;j<=i;j++){//枚举划分k个集合
          tmp=((tmp+(S[i][j+1]*(j+1)+S[i][j])%mod*(qpow(2,(n-i)*j,mod))%mod))%mod;
      }
      tmp=(tmp*qpow(2,qpow(2,n-i,mod-1),mod)%mod*C(n,i)%mod)%mod;//注意费马小定理
      Tempestissimo=(Tempestissimo+qpow(-1,i,mod-1)*tmp)%mod;
  }
  write((Tempestissimo%mod+mod)%mod);
  return 0;
  }