基础计数 盒子与球 默认以下盒子为m 球为n 盒子不同 球相同 不能为空 直接插板-c(n-1,m-1) 可以有空 加入m个球使得变为上面问题 盒子相同 球不同 不能有空 相当于划分集合 方案不同当且仅当有一个集合的元素不同 那么就是第二类斯特林数 可以有空 则枚举空的数量(无序) 盒子相同 球也相同 这就是个数的划分 span "skip"数的划分 span 往往是一类集合无序球也无差别的问题 n划分成k个数(f[n][k]) 就是k个 - 使得最后结果每个位置都=2 则先提出k个来放到每一个位置f[n-k][k] - 有为1的位置 则保证它存在f[n-1][k-1] 不超过k个(可以有0) - 上述第二种变为f[n][k-1] 就相当于放了个0堆 n划分成不大于k的数f[n][k] 可以有重 - 每个数都k f[n][k-1] - 有数为k f[n-m][m] 每个数不同 - 有数为k 使得之前的数不能为k - f[n-m][m-1] span "j mp"#第二类斯特林数span n个有差别元素划分为m个无序集合 求法 递推式 (n^2) 第i个元素放一个新的集合 s[i-1][j-1] 第i个元素放入已有集合 s[i-1][j]*j 通项式求一行(fft - nlogn) [图片上传失败...(image-7439a9-)] 要记的应用 转换下降幂与自然幂 [图片上传失败...(image-bdb879-)] n的k次下降幂是n(n-1)(n-2)...(n-k-1) 有个小性质 n(k+1)=n(k)(n-k) 那么实际上 i^k 就是 sigma(s(k,j)j!*c(i,j))后面那一坨就是下降幂 错排 每个位置都不是原本的数的方案数 两种递推形式 f[i]=(i-1)(f[i-1]+f[i-2]) f[i]=f[i-1]i(-1)^i 一种非递推(也是o(n)不知道有什么意义的形式) f[i]=s m{(-1)^in!i!