AT_awc0001_a バクテリアの増殖実験 题解

通过观察样例可以发现答案就是 $n+1$。下面给出一个简单的说明：

关键结论 $1$

多个相同大小的菌落只需要考虑一个即可。

证明

显然每个大小为 $2^x$ 的菌落在一个时刻之后都会变成一个大小为 $2^x$ 的菌落和一个大小为 $2^{x+1}$ 的菌落，也就是说两个大小均为 $2^x$ 的菌落在任何时候其扩展得到的菌落都是完全相同的。因此保留一个即可。

关键结论 $2$

大小最小的菌落大小是 $2^0=1$，大小最大的菌落大小是 $2^n$。

关键结论 $3$

大小为 $2^0,2^1,\ldots,2^n$ 的菌落都会出现。

证明

对于大小为 $2^i$ 的菌落，只需要让其在其中 $i$ 个时刻大小翻倍，另外 $n-i$ 个时刻大小不变即可。

本题解法

问题可被转化为是求 $2^0,2^1,\ldots,2^n$ 中有多少个不同的数。显然答案为 $n-0+1=n+1$，可以在 $O(1)$ 时间复杂度内解决。