RT,看到这篇讨论之后把题解区翻了一遍 ,因为太菜了每一篇都看了好久。
发现这篇题解的第一个柿子就和别的题解不一样(在状态表示相同的情况下)。
这篇题解转移中是 (i−j−1),但我觉得是 (i−j+1)?后来题解中将状态改掉了,表示前 i 个格子中有 j 个格子没填数的方案数,转移就一下子变成了斯特林数的递推式。
可是我觉得转移应该是 fi,j=(j+1)×fi−1,j+fi−1,j−1,改成 (j+1) 的之后等于斯特林数就不那么显然了。
题解最后也没有说明 fn−1,n−k 就是斯特林数的 S(n,n−k)。
所以上述转换状态表示,变成显然的斯特林递推式的方法是正确的吗?太菜了,求解答。
与此无关,题解区很多 fn,k 表示的都是 “前 n−1 个”的方案数,但是大多数(好像是全部?)都没有写原因,前 n 个也能做,我理解的是最终推出来答案要平移使得与斯特林数对应(可以看这个帖子)。太菜了想了好久才发现问题,在此提醒初学斯特林数的后人。