AtCoder Regular Contest 096 E - Everything on It 容斥+第二类斯特林数

题意

给你一个n，一共有2^n种组合，你要选择一些组合，使得每个数都出现至少两次，答案模m，m是一个质数，n<=5000

分析

这道题是计数题，很容易想到容斥

$$\sum\limits_{i=0}^{n} (-1)^i 2 ^ {2^{n-i}} \binom{n}{i} \sum\limits_{j=0}^{i} \binom{i}{j} \sum\limits_{k=1}^{j} S(j,k) (2^{n-i})^k$$
就是枚举有i个不合法，j个1，1分成k个集合

然后这样是 O(n3logm) O ( n 3 l o g m ) $O(n^3logm)$的，你可以拿到600分

考虑优化

$$\sum\limits_{i=0}^{n} (-1)^i 2 ^ {2^{n-i}} \binom{n}{i} \sum\limits_{k=1}^{i} (2^{n-i})^k \sum\limits_{j=k}^{i} \binom{i}{j} S(j,k)$$

因为

$$\sum\limits_{j=k}^{i} \binom{i}{j} S(j,k) = S(i+1,k+1)$$
这个式子可以反着理解，枚举多少个跟i+1一个集合

然后答案就是

$$\sum\limits_{i=0}^{n} (-1)^i 2 ^ {2^{n-i}} \binom{n}{i} \sum\limits_{k=1}^{i} (2^{n-i})^kS(i+1,k+1)$$

这样时间复杂度就是 O(n2logm) O ( n 2 l o g m ) $O(n^2logm)$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N = 3010;
inline LL read()
{
  LL p=0; LL f=1; char ch=getchar();
  while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();}
  while(ch>='0' && ch<='9'){p=p*10+ch-'0'; ch=getchar();}
  return p*f;
}
LL C[N][N],S[N][N];
LL qpow(LL x,LL k,LL mo){LL s=1; while(k){if(k&1) s=s*x%mo; x=x*x%mo; k>>=1;} return s;}
int main()
{
  LL n = read(); LL p = read();
  C[0][0] = 1; for(LL i=1;i<=n+1;i++)
  {
    C[i][0] = 1; for(LL j=1;j<=i;j++) C[i][j] = (C[i-1][j] + C[i-1][j-1]) % p;
  }
  S[0][0] = 1; for(LL i=1;i<=n+1;i++)
  {
    S[i][1] = 1; for(LL j=2;j<=i;j++) S[i][j] = (S[i-1][j] * j + S[i-1][j-1]) % p;
  }

  LL ans = 0;
  for(LL i=0;i<=n;i++)
  {
    LL s = C[n][i] * qpow(2,qpow(2,n-i,p-1),p) % p;
    LL fr = 0; for(LL j=0;j<=i;j++) fr = (fr + qpow(2,(n-i)*j%(p-1),p) * S[i+1][j+1] % p) % p;
    // printf("%lld %lld\n",s,fr);
    ans =( (ans + ((i&1) ? (-1) : 1) * s % p * fr % p ) % p + p ) % p;
  }
  return printf("%lld\n",ans),0;
}