This is not the end.

0%

BZOJ2498 Xavier is Learning to Count

Posted on

Sol

容易想到$O(Bell(P))$地枚举$P$的集合划分，然后进行容斥（强制同一个集合里的数取值相同），但是容斥系数应该如何取呢？

对于一个大小为$x$的集合，设它的容斥系数为$f_x$。一种集合划分的容斥系数为每个集合的容斥系数的乘积。

对于某一种选$P$个数的方案，假设其中第$a_{1,1},a_{1,2},\cdots a_{1,k_1}$个数相同，第$a_{2,1},a_{2,2},\cdots a_{2,k_2}$个数相同，……第$a_{m,1},a_{m,2},\cdots a_{m,k_m}$个数相同，那么这种方案将会被计算的次数是

根据定义我们需要让这个式子在至少有一个$k_i > 1$的时候为$0$，所有的$k_i$都为$1$的时候为$1$。

记

我们相当于是要让

枚举$n$所属的集合的大小得

因为$\forall i>1, g(i)=0$，所以

令$f(n) = -(n-1)f(n-1), f(1) = 1$，也就是$f(i) = (-1)^{i-1}(i-1)!$，即得到一组满足条件的容斥系数。

Code

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define FIR first
#define SEC second
#define ll long long
#define db long double
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=(1<<16)+10;
const db Pi=acos(-1.0);
struct Comp {
    db a,b;
    Comp (db a=0,db b=0): a(a),b(b) {}
    friend Comp operator *(Comp A,Comp B){return Comp(A.a*B.a-A.b*B.b,A.a*B.b+A.b*B.a);}
    friend Comp operator +(Comp A,Comp B){return Comp(A.a+B.a,A.b+B.b);}
    friend Comp operator -(Comp A,Comp B){return Comp(A.a-B.a,A.b-B.b);}
    friend Comp operator /(Comp A,db B){return Comp(A.a/B,A.b/B);}
    friend Comp operator *(Comp A,db B){return Comp(A.a*B,A.b*B);}
    Comp conj(){return Comp(a,-b);}
};
int rev[N];
void getr(int l){for(int i=1;i<(1<<l);++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<l-1);}
void FFT(Comp A[],int len,int f)
{
    for(int i=0;i<len;++i) if(rev[i]<i) swap(A[i],A[rev[i]]);
    for(int l=2;l<=len;l<<=1)
    {
        Comp wn=Comp(cos(2*Pi/l),f*sin(2*Pi/l));
        for(int i=0;i<len;i+=l)
        {
            Comp w=Comp(1,0);
            for(int k=i;k<i+(l>>1);++k,w=w*wn)
            {
                Comp t1=A[k],t2=A[k+(l>>1)]*w;
                A[k]=t1+t2,A[k+(l>>1)]=t1-t2;
            }
        }
    }
    if(f==-1) for(int i=0;i<len;++i) A[i]=A[i]/len;
}

Comp A[6][N],B[N];
db frac[6];
int n,m,len;
int buc[6];
void dfs(int u,int mx) {
	if(u==m+1) {
		db coe=1;
		for(int i=1;i<=mx;++i) coe*=frac[buc[i]-1]*(buc[i]&1?1:-1);
		for(int j=0;j<len;++j) {
			Comp t=Comp(coe,0);
			for(int i=1;i<=mx;++i) t=t*A[buc[i]][j];
			B[j]=B[j]+t;
		}
		return;
	}
	for(int i=1;i<=mx+1;++i)
		buc[i]++,dfs(u+1,max(i,mx)),buc[i]--;
}
int main() {
	frac[0]=1; for(int i=1;i<=5;++i) frac[i]=frac[i-1]*i;
	int T,cas=0; rd(T);
	while(T--) {
		int num; rd(num),rd(m);
		n=0;
		for(int i=1,x;i<=num;++i) {
			rd(x);
			for(int j=1;j<=m;++j) A[j][x*j].a+=1;
			n=max(n,x*m);
		}
		len=1; int cnt=0; while(len<=n) len<<=1,cnt++; getr(cnt);
		for(int j=1;j<=m;++j) FFT(A[j],len,1);
		dfs(1,0);
		FFT(B,len,-1);
		printf("Case #%d:\n",++cas);
		for(int i=0;i<=n;++i) {
			db ans=B[i].a/frac[m];
			if(ans>0.5) printf("%d: %.0Lf\n",i,ans);
		}
		puts("");
		for(int j=1;j<=m;++j) for(int i=0;i<len;++i) A[j][i].a=A[j][i].b=0;
		for(int i=0;i<len;++i) B[i].a=B[i].b=0;
	}
	return 0;
}