A A bit common_牛客博客

枚举有 $i$ 个数末尾是 1，那么其他 $n-i$ 个数有 $C_n^{n-i}$ 种放置方法，且总共有 $(n-i)\times (m-1)$ （每个数有 $m-1$ 个自由位）个可以自由放置的数位。所以这一部分可能性数为 $C_n^{n-i}\times 2^{(n-i)\times (m-1)}$ 。

然后考虑那 $i$ 个数。PPT 里的做法是，由于这些数全部 AND 起来一定是 $1$ ，所以每一位一定不能都是 $1$ 。所以每一位的填写方案数为 $2^i-1$ 种。因为一共有 $m-1$ 位，所以这些数总填写方法数为 $(2^i-1)^{m-1}$ 。

于是上下相乘，总方法数为 $\sum_iC_n^{n-i}\times 2^{(n-i)\times (m-1)}\times (2^i-1)^{m-1}$ 。

我赛时做法是考虑所有数 AND 起来不为 1 的方案数，然后我打了个表，发现 $i$ 个 $m-1$ 位数的答案是 $(2^i)^{m-1}-(2^i-1)^{m-1}$ ，然后用总数减掉即可。