社区讨论

警示后人:关于第一篇题解

P8923『MdOI R5』Many Minimizations参与者 4已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mkb5dwty
此快照首次捕获于
2026/01/12 20:37
上个月
此快照最后确认于
2026/01/16 19:55
上个月
查看原帖
题解中提到:
设走到 (n,i)(n,i) 的方案数为 wiw_i。我们要求的是 ii×wi\sum\limits_i i\times w_i
这里应该是作者笔误了,反悔贪心里的贡献是减少的1,不是剩下的1。所以应该是"向右上走的次数减去i"。
也就是说下文的式子里:
i0wi×i=i0ii+2jnxj(mx)nj((ni+j)(ni+j+1))\sum\limits_{i\ge 0} w_i\times i=\sum\limits_{i\ge 0} i\sum\limits_{i+2j\ge n}x^j(m-x)^{n-j}\left(\dbinom{n}{i+j}-\dbinom{n}{i+j+1}\right)
=i0xi(mx)nijmax{i,ni}(ji)((nj)(nj+1))=\sum\limits_{i\ge 0} x^i(m-x)^{n-i}\sum\limits_{j\ge\max\{i,n-i\}} (j-i)\left(\dbinom{n}{j}-\dbinom{n}{j+1}\right) 应该改为:
i0wi×(ji)=i0i+2jn(ji)xj(mx)nj((ni+j)(ni+j+1))\sum\limits_{i\ge 0} w_i\times (j-i)=\sum\limits_{i\ge 0} \sum\limits_{i+2j\ge n}(j-i)x^j(m-x)^{n-j}\left(\dbinom{n}{i+j}-\dbinom{n}{i+j+1}\right)
=i0xi(mx)nijmax{i,ni}(2ij)((nj)(nj+1))=\sum\limits_{i\ge 0} x^i(m-x)^{n-i}\sum\limits_{j\ge\max\{i,n-i\}} (2i-j)\left(\dbinom{n}{j}-\dbinom{n}{j+1}\right)

回复

7 条回复,欢迎继续交流。

正在加载回复...