题解：P15995 [ICPC 2020 NAC] Another Coin Weighing Puzzle

· · 题解

进行 m 次称量会得到一个长度为 m 的序列，n 合法也就是对于不同的假币位置，得到的 n 个序列可以区分。那么问题转化为最多有多少个两两可以区分的序列。

一次称量返回的答案显然是 A 中假币数量减去 B 中假币数量乘一个未知的常数 c，考虑每一项除掉这个 c 的序列，每一项取值范围都是 [-k,k] 的整数。

考虑怎样两个序列是可以区分的。由于不知道 c 的值，因此有倍数关系相同的两个序列是不能区分的。这个倍数是指一个序列每一项乘一个 >0 的整数，>0 是因为显然 [1,1],[-1,-1] 可以区分。

还有一个问题是能否保证每一次左右放的硬币数量相等。注意到序列每一项乘 -1 会得到另一个合法序列，所以每次称量左右都是相等的。

答案就很好求了，枚举 i 个 0，令剩下的数取值在 [1,k]，求出 \gcd=1 的方案数，再乘上 2^{m-i} 即可。

\\ &\phantom{=}\sum_{i=0}^m \binom{m}{m-i} 2^{m-i} f(m-i)\\ &= \sum_{i=0}^m \binom{m}{m-i} 2^{m-i} \sum_{d=1}^k \mu(d) \left\lfloor \frac{k}{d} \right\rfloor^{m-i} \\ &= \sum_{d=1}^k \mu(d) \sum_{i=0}^m \binom{m}{i} \left( 2\left\lfloor \frac{k}{d} \right\rfloor \right)^{m-i}\\ &= \sum_{d=1}^k \mu(d) \left( 2\left\lfloor \frac{k}{d} \right\rfloor + 1 \right)^m \end{aligned}

这个算 f(0) 的时候算出来不对，最后修正一下即可。