题意
给你一个含有 $n$ 个元素的可重集合 $A$，集合 $A$ 的每个元素是一个单元素集合 ${a_i}$。
定义一次操作由以下两步构成：
- 选择 $A$ 中两个交集为空的集合 $S$, $T$。
- 删除这两个集合，将它们的并添加进 $A$。
之后, 我们构造一个可重集合 $M$，表示当前剩下的所有集合的大小。
你可以执行任意多次操作，问所有不同的 $M$ 的总数。
做法
如果初始的元素互不相同，显然原问题等价于分拆数，虽然原问题是以合并的方式给出的。
那么原问题等价于带有某种限制的分拆数，限制为某些元素之间必须分拆。
分拆数我们知道有很多高级做法。。。比如欧拉五边形数、生成函数云云。。。。但是这个题 $n$ 只有 2000，大概率都用不到。
考虑分拆数最朴素的 DP。。。我们把分拆的结果按照从大到小排序。。那么每一种情况唯一对应一个单调递减且和为 n 的序列。
dp[i][s][j]: 当前考察前 i 个位置，和为 s 且末尾为 j 的方案数。
有：
const int N = int(1e3) + 9;
int dp[2][N][N];
int n;
int main() {
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
RD(n);
int p = 0, q = 1; RST(dp[p]); dp[p][0][n] = 1;
REP_1(i, n) {
swap(p, q); RST(dp[p]);
#define u dp[q][s][j]
#define v dp[p][s+k][k]
REP(s, n+1) REP(j, n+1) if (u) {
DWN_1(k, min(j, n-s), 0) v += u;
}
cout << dp[p][i][0] + 1 << " ";
}
cout << endl;
}
这个 DP 可以用部分和优化到 $O(n^3)$。
dp[i][s][j]: 当前考察前 i 个位置，和为 s 且末尾 >= j 的方案数。
const int N = int(1e3) + 9;
int dp[2][N][N];
int n;
int main() {
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
RD(n);
int p = 0, q = 1; RST(dp[p]); dp[p][0][n] = 1;
REP_1(i, n) {
swap(p, q); RST(dp[p]);
#define u dp[q][s][j]
#define v dp[p][s+j][j]
REP(s, n+1) DWN(j, n+1, 0) u += dp[q][s][j+1];
REP(s, n+1) REP(j, n+1) if (u) v += u;
cout << dp[p][i][0] + 1 << " ";
}
cout << endl;
}
继续考察限制。。。结论是。。。它等价于 $s \leq \sum \min(i, c)$
其中 $c$ 遍历过初始集合中的每个元素出现的次数。。。
这个结论真的不是很显然。。。感觉需要用共轭的性质 + 各种归纳 yy 出来。。。
于是加上上面的限制作为剪枝就可以 O(n2logn) 跑出来。。。
但是我们知道其实分拆数的朴素 dp 可以进一步优化到 $O(n2)$。。。
原因是分差数本身就更特殊。。。状态可以进一步简化。。。
