题解 AT4119 【[ARC096C] Everything on It】

· · 题解

考虑容斥。

设 F(i) 表示至少有 i 个数的出现次数不多于 1 次。

则答案为：

\sum\limits_{i=0}^n(-1)^iF(i)

枚举 j,表示将这 i 个数划分到 j 个非空集合中。但是由于限制是不多于一次，意味着可能存在一些数没有出现过。

如何解决呢？我们考虑新加入一个集合当做“垃圾堆”，该集合中的数即为没有出现的数。但是还有一个问题：“垃圾堆”可能为空。所以我们新加入一个数字 0，0 所在集合即为垃圾堆。

于是将 i 个数划分到 j 个非空集合的方案数为 \begin{Bmatrix} i+1\\j+1 \end{Bmatrix}。

然后考虑剩下来的 n-i 个数可以形成 2^{n-i} 个集合。我们可以枚举这些集合有没有被选择，那么方案数就是 2^{2^{n-i}}。最后，剩下的 n-i 个数还可以往之前的 j 个集合里面放，所以再乘上 (2^{n-i})^j。

于是答案为：

\sum\limits_{i=0}^n(-1)^iF(i) =\sum\limits_{i=0}^n(-1)^i\begin{pmatrix}n\\i\end{pmatrix}\sum\limits_{j=0}^i\begin{Bmatrix}i+1\\j+1\end{Bmatrix}\cdot 2^{2^{n-i}}\cdot (2^{n-i})^j =\sum\limits_{i=0}^n(-1)^i\cdot 2^{2^{n-i}}\begin{pmatrix}n\\i\end{pmatrix}\sum\limits_{j=0}^i\begin{Bmatrix}i+1\\j+1\end{Bmatrix}\cdot (2^{n-i})^j 
#include<cctype>
#include<cstdio>
using namespace std;
#define getchar() (SS == TT && (TT = (SS = BB) + fread(BB,1,1 << 15,stdin),TT == SS) ? EOF : *SS++)
char BB[1 << 15],*SS = BB,*TT = BB;
inline int read()
{
    register int x = 0;
    register char ch = getchar();
    for(;!isdigit(ch);ch = getchar());
    for(;isdigit(ch);ch = getchar())
        x = x * 10 + (ch ^ 48);
    return x;
}
inline void print(int x)
{
    char ch = x % 10 + '0';
    if(x > 9)
        print(x / 10);
    putchar(ch);
}

int mod;
inline int add(int a,int b)
{
    a += b;
    return a >= mod ? a - mod : a;
}
inline int qpow(long long a,int b,int p = mod)
{
    register long long ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % p;
        a = a * a % p,b >>= 1;
    }
    return ans;
}

const int N = 3010;
int n;
long long s[N][N],c[N][N],ans;

inline void init()
{
    c[0][0] = s[0][0] = 1;
    for(register int i = 1;i <= n + 1;i++)
    {
        c[i][0] = 1;
        for(register int j = 1;j <= i;j++)
            s[i][j] = (s[i - 1][j - 1] + s[i - 1][j] * j) % mod,
            c[i][j] = add(c[i - 1][j - 1],c[i - 1][j]);
    }
}

int main()
{
    n = read(),mod = read();
    init();

    for(register int i = 0;i <= n;i++)
    {
        register long long _2 = qpow(2,n - i);

        long long mul = i & 1 ? mod - 1 : 1,res = 0;
        mul = mul * c[n][i] % mod * qpow(2,qpow(2,n - i,mod - 1)) % mod;

        register long long _2j = 1;
        for(register int j = 0;j <= i;j++)
            res = (res + s[i + 1][j + 1] * _2j) % mod,
            _2j = _2j * _2 % mod;

        ans = (ans + res * mul) % mod;
    }
    print(ans);
}