关于本题题解
查看原帖
关于本题题解
252664
Twig_K楼主2024/12/14 09:00

RT,看到这篇讨论之后把题解区翻了一遍 ,因为太菜了每一篇都看了好久

发现这篇题解的第一个柿子就和别的题解不一样(在状态表示相同的情况下)。

这篇题解转移中是 (ij1)(i-j-1),但我觉得是 (ij+1)(i-j+1)?后来题解中将状态改掉了,表示前 ii 个格子中有 jj 个格子没填数的方案数,转移就一下子变成了斯特林数的递推式。

可是我觉得转移应该是 fi,j=(j+1)×fi1,j+fi1,j1f_{i,j}=(j+1) \times f_{i-1,j}+f_{i-1,j-1},改成 (j+1)(j+1) 的之后等于斯特林数就不那么显然了。

题解最后也没有说明 fn1,nkf_{n-1,n-k} 就是斯特林数的 S(n,nk)S(n,n-k)

所以上述转换状态表示,变成显然的斯特林递推式的方法是正确的吗?太菜了,求解答。


与此无关,题解区很多 fn,kf_{n,k} 表示的都是 “前 n1n-1 个”的方案数,但是大多数(好像是全部?)都没有写原因,前 nn 个也能做,我理解的是最终推出来答案要平移使得与斯特林数对应(可以看这个帖子)。太菜了想了好久才发现问题,在此提醒初学斯特林数的后人。

2024/12/14 09:00
加载中...