ARC096C Everything on It

昨天写了忘发了。。

考虑容斥,设 $f(i)$ 表示钦定了 $i$ 个数只出现了 $\le 1$ 次时的方案数量,那么答案显然等于

考虑我们钦定的 $i$ 个数,显然可以直接假定为 $1\sim i$ ,最后再乘个 $\binom n i$ 的系数即可。

先考虑除开前 $i$ 个的数,这些数是没有限制的,他们可以组成集合的方案数量是 $2^{2^{n-i}}$ 种,因为任何一个这 $n-i$ 个数的子集都可以作为某一种集合出现或者不出现。

再考虑前 $i$ 个数的加入。假设前 $i$ 个数出现在 $j$ 个集合里(因为每个数出现次数不超过 $1$ 所以前 $i$ 个数出现的集合个数 $j$ 也不会超过 $i$ ),考虑枚举这个 $j$ 。

现在我们已经确定了前 $i$ 个数会被分配到 $j$ 个集合里面,其中有些数可能直接被丢掉。然后有两种方法数这个:

  • 考虑新建一个垃圾桶,用来放我们不放进这 $j$ 个集合里面的数。首先假定我们确定这 $i$ 个数在分配后有数在垃圾桶里,但是当我们把这 $i$ 个数分配进这 $j+1$ 个集合后,我们并不确定哪一个是垃圾桶,于是还得乘个 $(j+1)$ 的系数表示枚举哪一个是垃圾桶。还有的情况就是不存在分配在垃圾桶的数。我们知道 $i$ 个数分配进集合的方案数就是第二类斯特林数,于是这里就是

    也就是第二类斯特林数的递推公式。

  • 其实也可以考虑如果我们考虑新加一个 $0$ 进去,然后钦定 $0$ 被分配到的集合就是垃圾桶也是完全没有问题的。这样就可以直接得到答案是 $\begin{Bmatrix}i + 1\\j + 1\end{Bmatrix}$

最后记得在这 $j$ 个集合中也可以任意塞后 $n-i$ 个数中的数,而且明显这 $j$ 个集合不可能重,所以可以直接乘上系数 $(2^{n-i})^j$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 3006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
//#define P 998244353
int n , P;
int S[MAXN][MAXN] , C[MAXN][MAXN];

int Pow( int x , int a ) {
int ret = 1;
while( a ) {
if( a & 1 ) ret = ret * 1ll * x % P;
x = x * 1ll * x % P , a >>= 1;
}
return ret;
}

int p2[MAXN];
void solve() {
cin >> n >> P;
S[0][0] = C[0][0] = 1 , p2[0] = 1;
rep( i , 1 , n + 1 ) {
C[i][0] = 1 , S[i][0] = 0;
rep( j , 1 , i ) S[i][j] = ( S[i - 1][j - 1] + S[i - 1][j] * 1ll * j ) % P , C[i][j] = ( C[i - 1][j - 1] + C[i - 1][j] ) % P;
p2[i] = p2[i - 1] * 2 % ( P - 1 );
}
int ans = 0;
rep( i , 0 , n ) {
int re = 0;
rep( j , 0 , i ) re = ( re + S[i + 1][j + 1] * 1ll * Pow( 2 , ( n - i ) * 1ll * j % ( P - 1 ) ) ) % P;
re = re * 1ll * Pow( 2 , p2[n - i] ) % P * C[n][i] % P;
ans = ( ans + ( ( i & 1 ) ? P - re : re ) ) % P;
}
cout << ans << endl;
}

signed main() {
// freopen("ex_A2.in","r",stdin);
// freopen("out","w",stdout);
// int T;cin >> T;while( T-- ) solve();
solve();
}


文章作者: yijan
文章链接: https://yijan.co/arc096c-everything-on-it/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog