Link,限制依次为:
\(1\):球之间互不相同,盒子之间互不相同。
\(2\):球之间互不相同,盒子之间互不相同,每个盒子至多装一个球。
\(3\):球之间互不相同,盒子之间互不相同,每个盒子至少装一个球。
\(4\):球之间互不相同,盒子全部相同。
\(5\):球之间互不相同,盒子全部相同,每个盒子至多装一个球。
\(6\):球之间互不相同,盒子全部相同,每个盒子至少装一个球。
\(7\):球全部相同,盒子之间互不相同。
\(8\):球全部相同,盒子之间互不相同,每个盒子至多装一个球。
\(9\):球全部相同,盒子之间互不相同,每个盒子至少装一个球。
\(10\):球全部相同,盒子全部相同。
\(11\):球全部相同,盒子全部相同,每个盒子至多装一个球。
\(12\):球全部相同,盒子全部相同,每个盒子至少装一个球。
可否把所有球都扔进去。
同。
每个球依次选盒子。
选 \(n\) 个盒子装球。
选 \(n\) 个盒子,塞完球然后排列。
插板法。
插板法,先给每个盒子塞一个球保证正整数。
第二类斯特林数定义。
枚举非空盒子个数。把第二类斯特林数·行贺过来即可。
容斥,枚举 \(k\) 表示至多有 \(k\) 个有球的盒子。
记 \(p(n,m)\) 表示将 \(n\) 分拆成至多 \(m\) 个正整数的方案数。那么
\(n-m\) 意为事先给每个盒子扣掉一个球。
把 \(p(n,m)\) 的方案用点阵表示出来(此处 \(n=7,m=3\)):
其行数 \(\le m\)。将其转置(顺时针转 \(90^\circ\) 然后水平翻转):
那么其列数 \(\le m\)。这个矩阵还是表示一种拆分方案,且容易知道新矩阵和原矩阵一一对应。
于是 \(p(n,m)\) 变成了:将 \(n\) 分拆成任意多个 \(\le m\) 的正整数的方案数。
这个是付公主的背包。记
按照原题,可以对每个 \(i\) 求 \(\ln\) 之后一通操作 \(O(m\ln n)\) 得到答案的 \(\ln\) 值,然后 \(\exp\) 回来即可。然后有
于是