<p>答案是一个非常简单的递归。<code>F(1) = 2</code>对于{<cd2>}我们有两个选择:</p>
<ul>
<li><code>n = H</code>,那么亲吻剩下的客人的方法就只是<code>F(n-1)</code></li>
<li><code>n = K</code>,那么亲吻剩余客人的方式是<code>2 ** k</code>,其中{<cd7>}是公主没有被迫亲吻的剩余客人的数量。因为她每秒钟都要亲吻剩下的客人,<code>k = ceil((n - 1) / 2)</code></li>
</ul>
<p>把它们放在一起,我们得到<code>F(n) = F(n - 1) + 2 ** ceil((n - 1) / 2)</code></p>
<p>我的尝试,包括拿走所有的mod 100000007:</p>
<pre><code>from math import ceil
def F(n):
m = 1000000007
a = 2
for i in range(2, n+1):
a = (a + pow(2, int(ceil((i - 1.0) / 2)), m)) % m
return a
</code></pre>
<p><strong>编辑:</strong>更新(更快,更不可读!<code>F(1e9)</code>大约需要3分钟):</p>
^{pr2}$
<p><strong>编辑2:</strong>经过进一步思考,我意识到上面的事实只是:</p>
<pre><code>F(n) = (1 + 1) + (2 + 2) + (4 + 4) + ... + (2 ** n/2 + 2 ** n/2)
= 2 * (1 + 2 + 4 + ... + 2 ** n/2)
= 2 * (2 ** (n/2 + 1) - 1)
= 2 ** (n/2 + 2) - 2
</code></pre>
<p>但是如果<code>n</code>是偶数,最后一个<code>2 ** n/2</code>只出现一次,所以我们有:</p>
<pre><code>def F(n):
m = 1000000007
z = pow(2, n/2, m)
if (n % 2 == 0):
return (z * 3 - 2) % m
else:
return (z * 4 - 2) % m
</code></pre>
<p>跑得快多了!(受限于<code>pow(x, y, z)</code>的速度,我认为是<code>O(lg n)</code>?)在</p>
<p>只是因为,这里有一条线:</p>
<pre><code>def F(n):
return (pow(2, n/2, 1000000007) * (3 + n % 2) - 2) % 1000000007
</code></pre>
<p>结果:</p>
<pre><code>1 => 2
2 => 4
3 => 6
4 => 10
5 => 14
6 => 22
7 => 30
8 => 46
9 => 62
10 => 94
1e6 => 902893650
1e7 => 502879941
1e8 => 251151906
1e9 => 375000001
</code></pre>