当前位置: 首页 > news >正文

题解:loj154 集合划分计数

题意:给出一个大小为 \(n\) 的全集 \(A = \{1,2,\cdots n\}\),再给出 \(m\) 个集 \(S_1,S_2\cdots S_m\),要求从这些集里选出至多 \(k\) 个,满足 \(S\) 间没有交集且并集是全集,\(k\le n\le 21,m\le 262144\)

做法:

以下多项式乘法若没有特殊说明均是多项式乘法而非子集卷积。

看到这个东西,没有交集求并集,很有子集卷积的感觉,先上占位多项式试一下。设 \(z_S(t) = \sum\limits_{i=0}^n t^i fwt(f_i)[s]\),也就是我们视 \(f_t = \sum\limits_{i=0}^{2^n-1} cnt_ix^i[\operatorname{popcount}(i) ==t]\),这个东西是一行,那么 z 就是一列并加上占位的出来的多项式。

考虑然后该怎么做,本来应该是直接对 \(f\) 这个拆成 \(n\) 位的东西直接做 \(k\) 次子集卷积得到,但是比较难算因为我们这里要的是无序对,需要除掉一个阶乘有点麻烦,同时我们没有必要每次 fwt 重新做,所以我们考虑先转成 \(z_S(t)\) 处理,因为 fwt 之后每一位就独立了,然后再 fwt 回来。

有这个 \(z_S(t)\) 还不够,我们还没算选 \(k\) 个集的事情,考虑直接枚举选了 \(i\) 个,那么就是 \(w_S(t) = \sum\limits_{i=1}^k\frac{z_S(t)^i}{i!}[t^n]\),感觉很像一个 exp 的 形式,但是这里被 \(k\) 限制了,但是我们仍然考虑对两侧求导。

我们这里为了方便,用 \(G=w_S(t),F=z_s(t)\),那么有

\[G=\sum_{i=1}^k\frac{F^i}{i!} \]

两侧求导,得到:

\[G'=\sum_{i=1}^k\frac{F^{i-1}\times F'}{(i-1)!} \]

同一提出去一个 \(F'\)

\[G'=F'\sum_{i=0}^k\frac{F^{i-1}}{(i-1)!} \]

注意到后面这个求和式和 \(G\) 相当像,只是差两位求和,直接写开得到:

\[G'=F'(G-\frac{F^k}{k!}+1) \]

直接对着这个柿子做就行,这里全都是多项式乘法,不要和我一样傻乎乎地想不明白还以为是位运算相关的。

我因为比较懒,这里求 \(k\) 次直接用的是快速幂,但是也可以 \(O(n^2)\) 递推 ln, exp 但是因为这里 \(F\) 并不一定具有末尾为 1 的性质所以非常恶心。

但是这个做法不知道为什么我写的奇慢无比,本地能跑出 2min 的超快速度,这里挂了一个我本地 30s 但是 loj 上 5s 的代码:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int_;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
inline int readint() {int a = 0;char c = getchar(), f = 1;for (; c < '0' || c > '9'; c = getchar())if (c == '-')f = -f;for (; '0' <= c && c <= '9'; c = getchar())a = (a << 3) + (a << 1) + (c ^ 48);return a * f;
}const int Mod = 998244353;namespace Math {
const int MaxN = 262150;
int jc[MaxN], inv[MaxN];
int jc_inv[MaxN];
void import(int n = MaxN - 1) {jc[1] = inv[1] = 1;rep(i, 2, n) {jc[i] = 1ll * jc[i - 1] * i % Mod;inv[i] = (0ll + Mod - Mod / i) * inv[Mod % i] % Mod;}jc_inv[0] = jc[0] = 1;rep(i, 1, n)jc_inv[i] = 1ll * jc_inv[i - 1] * inv[i] % Mod;
}
inline int C(int n, int m) {if (n < m || m < 0)return 0;return 1ll * jc[n] * jc_inv[m] % Mod * jc_inv[n - m] % Mod;
}
}const int MaxN = 22;
struct Poly {int a[MaxN];int &operator[](const int &x) {return a[max(0, x)];}void operator += (const Poly &b) {rep(i, 0, MaxN - 1)a[i] = (a[i] + b.a[i]) % Mod;}
};
Poly operator * (const int &v, const Poly &f) {Poly g;rep(i, 0, MaxN - 1)g[i] = 1ll * f.a[i] * v % Mod;return g;
}
Poly operator * (const Poly &f, const Poly &g) {Poly h;memset(h.a, 0, MaxN << 2);rep(i, 0, MaxN - 1) if (f.a[i])rep(j, 0, MaxN - 1 - i)h[i + j] = (h[i + j] + 1ll * f.a[i] * g.a[j]) % Mod;return h;
}
Poly qkpow(Poly b, int q) {Poly a;a[0] = 1;rep(i, 1, MaxN - 1) a[i] = 0;for (; q; q >>= 1, b = b * b)if (q & 1)a = a * b;return a;
}void FWT(Poly a[], int n) {rep(i, 0, n - 1) rep(j, 0, (1 << n) - 1)if (j >> i & 1)a[j] += a[j ^ (1 << i)];
}Poly a[1 << MaxN];
int cnt[1 << MaxN];
int main() {int n = readint(), m = readint();int k = readint();Math::import();rep(i, 1, (1 << n) - 1) // bitcntcnt[i] = cnt[i >> 1] + (i & 1);rep(i, 1, m) {int x = readint();++ a[x][cnt[x]];}FWT(a, n);int ans = 0;Poly g_, now, gg;for (int i = 0; i < (1 << n); ++i) {rep(j, 1, n) g_[j - 1] = a[i][j] * j;g_[n] = 0;gg = qkpow(a[i], k);rep(j, 0, n) gg[j] = 1ll * gg[j] * Math::jc_inv[k] % Mod;now = gg * g_;rep(j, 0, n) now[j] = Mod - now[j];now += g_;rep(j, 1, n - 1) {int delta = 1ll * Math::inv[j] * now[j - 1] % Mod;drep(k, n, j) g_[k] = g_[k - 1]; // shiftg_[j - 1] = 0;now += delta * g_;}if (cnt[((1 << n) - 1)^i] & 1)ans = (ans + Mod - 1ll * now[n - 1] * Math::inv[n] % Mod) % Mod;elseans = (ans + 1ll * now[n - 1] * Math::inv[n]) % Mod;}printf("%d\n", ans);return 0;
}
http://www.hskmm.com/?act=detail&tid=25652

相关文章:

  • 为什么 Java 中打印Object类型的变量无需强转,而从Object类型的数组中取元素却要强转?
  • WinReanimator恶意软件清除指南:详细步骤与工具使用
  • 251006
  • 2025国庆Day5
  • 字节跳动开源图标库:2000+图标一键换肤的魔法 - 教程
  • 换根DP学习笔记
  • 自动化数据操作平台获3000万美元融资
  • 模块
  • 实用指南:【相机基础知识与物体检测】更新中
  • AtCoder Beginner Contest 422 游记(VP)
  • 详细介绍:无人机光纤FC接口模块技术分析
  • 2025 --【J+S 二十连测】-- 第十三套 总结
  • 文件提供的基本操作
  • 深入解析:MySQL(50)如何使用UNSIGNED属性?
  • 迈向人机价值共生文明:AI元人文范式下的演化架构与协同治理
  • 10.6
  • 文件存储空间管理
  • 详细介绍:关于ios点击分享自动复制到粘贴板的问题
  • 新一代数据平台替代传统大数据技术栈
  • 攻击者如何绕过macOS内置安全防护机制
  • 在A列连续且相等行的最后插入空行,并求和
  • 10.6集训改错
  • @Prometheus 监控-MySQL (Mysqld Exporter) - 教程
  • AI元人文:走向人机价值共生的文明新范式
  • 实用指南:【机器学习基础】机器学习入门核心算法:层次聚类算法(AGNES算法和 DIANA算法)
  • CSP-J 第二轮集训 :总结 + 专题细分精讲_from_黄老师
  • ROIR 2024
  • 软件工程第一次随笔 - Nicholas
  • 深入解析:【数据库】关系数据库标准语言-SQL(金仓)下
  • Codeforces Round 1056 (Div. 2) (4/6)