题解：P15889 [COCI 2025/2026 #6] 零花钱 / Džeparac

Shellchen · 2026-04-18 15:38:56 · 题解

这个计数题还是挺有意思的。

首先两个儿子拿的钱一定要相等，所以可以先 n \gets \lfloor \frac{n}{2} \rfloor。

为什么可以下取整呢？显然如果 n 是奇数，那么多出来的 1 元一定会被母亲拿走，所以无所谓。

接下来就会变成一个经典的插板法问题。考虑把钱变成小球，分日给钱相当于往小球之间插隔板，第一块板左边的相当于母亲自己留的钱。

那么隔板可以放在这么几种地方：

|O|O|O|O

| 是隔板，O 是小球。注意到最左边有个隔板因为母亲可以一点钱不留。

那么这里每种放隔板的方法都对应一种不同的分钱方案，所以有 2^n 种。（注意之前 n \gets \lfloor \frac{n}{2} \rfloor 过）

但其实还有一些特殊情况：

• 一个隔板都不放，显然不存在第一块板所以母亲拿的是滚木，方案数需要减一。
• 母亲把钱全拿走，相当于只在最后一个小球的右边放隔板，其它地方都不放。这个上面放隔板的方式没办法表示出来，所以方案数加一。

所以刚才的 2^n 就是答案。

省流：读入 n，输出 2^{\frac{n}{2}} \bmod (10^9+7)。代码就不放了。