对题解的一些疑问
查看原帖
对题解的一些疑问
833124
BIOS楼主2024/10/11 17:49

看的是第二篇题解,上面说f(i,j)计算了前i种糖中有至少j个人不变的方案数。 我看式子感觉f(i,j)只是挑选了包含最多i种糖果的j个人,使得这些人的糖果不变的方案数,并没有体现出最少,因为其它人并没有处理。真正使至少成立的应该是f(m,i)* (n-i)!这个东西,因为它对剩下的n-i个位置随意排列了,因为不能保证所有排列情况都让每个人的糖果不同所以才产生了“至少”的性质,因为这个式子可能对应了超过i个位置糖果种类不变。 然后,这个二项式反演最终式应该还有一个组合数是C(i,0),因为恒等于1所以没写出来,因为正着推的时候凑“至少x个”需要从x加到n,系数是C(i,x)所以反演过来的时候也是从x加到n,但是因为求恰好0个相同,所以x=0,因此系数变成C(i,0)==1

临时学了些二项式反演皮毛,不知道这样的理解对不对,因为这个最终式看起来跟标准反演式有些变化

2024/10/11 17:49
加载中...