P13275 [NOI2025] 集合 题解
luanyanjia
·
·
题解
我虽然没能场切此题，但是也获得了很高的分数，算是拯救了我整个 Day 2 了。
首先有 O(8^n) 的 DP。设 f_{i,j,k}，表示前 i 个数的情况确定了，使得 f(P) = j，f(Q) = k 的方案数。有如下转移：
f_{i,j,k} \times a_i \rightarrow f_{i+1,j \cap (i+1),k}
f_{i,j,k} \times a_i \rightarrow f_{i+1,j,k \cap (i+1)}
f_{i,j,k} \rightarrow f_{i+1,j,k}
到此为止就可以集合幂级数暴做了。
每次转移就是 \operatorname{and} 卷积。考虑 FMT 之后的 [x^j y^k]。每次相当于点乘 FMT 后的 x^i + y^i + 1。也就是乘上 a_i \times ([j \subseteq i] + [k \subseteq i]) + 1。这样下来我们可以轻松算出一个 [x^j y^k] 处的值 g_{j,k}。
设：
ss_i = \prod\limits_{i \subseteq j} (2a_j + 1),s_i = \prod\limits_{i \subseteq j} (a_j + 1)
那么有：
g_{j,k} = \dfrac{s_j s_k ss_{j \cup k}}{s_{j \cup k} ^ 2}
意思就是同时是 j,k 超集的需要乘 2a_i + 1，只是一个的超集的要乘 a_i + 1。
可能会除以 0，只需要记录 c_i 表示 i 超集中 0 因子的数量，然后判断是否有 c_j = c_k = c_{j \cup k} 即可。
至此我们可以 O(2^n n) 预处理，O(1) 查询 g_{j,k} 一个位置的值。全部查一遍再 IFMT 回来需要 O(4^n n) 的复杂度。可以获得 36 分。
我们发现最后其实只用了 f_{i,i} 的值，考虑把 IFMT 拆开式子：
\begin{align*}
f_{i,i} & = \sum\limits_{i \subseteq j,i \subseteq k} (-1)^{\left|j-i\right| + \left|k-i\right|}g_{j,k} \\
& = \sum\limits_{i \subseteq j,i \subseteq k}(-1)^{\left|j\right|+\left|k\right|}g_{j,k}
\end{align*}
这相当于对于 g_{j,k}，有 2^{\left|{j \cap k}\right|} 个 i 统计到了他。因此答案就是：
\begin{align*}
ans & = \sum\limits_{j,k} (-1)^{\left|j\right|+\left|k\right|}2^{\left|{j \cap k}\right|}g_{j,k}\\
& = \sum\limits_{j,k} (-2)^{\left|j\right|+\left|k\right|}2^{- \left|{j \cup k}\right|} \dfrac{s_j s_k ss_{j \cup k}}{s_{j \cup k} ^ 2}
\end{align*}
注意这里用到了 \left|j\cap k\right| = \left|j\right| + \left|k\right| - \left|j \cup k\right|。
这已经变成了或卷积的形式！不考虑 a_i = mod - 1 的情况，可以直接做到 O(2^n n)，拼上暴力获得 68 分。
我赛时的想法就止步于此。a_i = mod - 1 时我们该怎么办呢？
一个想法是根据上面暴力的结论，只有 c_i 相同的才能互相转移，因此按照 c_i 分类分别跑 FMT。但是这个复杂度是错的。A 性质也只能过一个点。
但是 c_i 还有一个性质就是如果 i \subseteq j，那么 c_i > c_j，而 FWT 时我们只会和自己的子集进行运算。所以 i 存在一个子集 j 满足 c_j > c_i 时 j 的子集 k 也一定满足 c_k > c_i 所以 j 的一切信息对于 i 就没用了。因此我们只需要在 c_j = c_i 的时候才转移即可。类似于其他题解说的只保留低次项。
可以获得 100 分。
### 代码
```cpp
inline void Add(int &a,int b){(a+=b)>=mod?a-=mod:1;}
inline void FWT(int *a,int n,int x){
for(int t=2,k=1;t<=n;t<<=1,k<<=1)
for(int i=0;i<n;i+=t)
for(int j=0;j<k;j++){
if(c[i+j]==c[i+j+k])Add(a[i+j+k],1ll*a[i+j]*x%mod);
}
}
inline void Solve(){
rd(n);
V=(1<<n);
for(int i=0;i<V;i++)rd(a[i]);
for(int i=0;i<V;i++){
s[i]=a[i]+1;c[i]=0;
ss[i]=(2*a[i]+1)%mod;
if(a[i]==mod-1)s[i]=c[i]=1;
}
for(int t=0;t<n;t++){
for(int i=0;i<V;i++){
if(!(i>>t&1)){
s[i]=1ll*s[i]*s[i^(1<<t)]%mod;
ss[i]=1ll*ss[i]*ss[i^(1<<t)]%mod;
c[i]+=c[i^(1<<t)];
}
}
}
for(int i=0;i<V;i++)ss[i]=1ll*ss[i]*KSM(s[i],(mod-2)*2)%mod;
for(int i=0;i<V;i++)f[i]=1ll*s[i]*KSM(mod-2,__builtin_popcount(i))%mod;
FWT(f,V,1);
for(int i=0;i<V;i++)f[i]=1ll*f[i]*f[i]%mod;
FWT(f,V,mod-1);
int res=0;
for(int i=0;i<V;i++){
Add(res,1ll*f[i]*ss[i]%mod*KSM((mod+1)/2,__builtin_popcount(i))%mod);
}
printf("%d\n",res);
}
```