《Ctrl-C Ctrl-V》题目分析

首先，对于最优方案，Ctrl-A + Ctrl-C + 若干个Ctrl-V一定是连在一起的。

例如 Ctrl-A + A + Ctrl-C + Ctrl-V，一定不如把A放在Ctrl-A之前，即: A + Ctrl-A + Ctrl-C + Ctrl-V

Ctrl-A + Ctrl-C + A + Ctrl-V 一定不如 A + Ctrl-A + Ctrl-C + Ctrl-V。

我们用f[i]表示i个操作最多能输出多少个A。对于最优解，最后一个操作一定是A或者Ctrl-V。

如果最后一个操作是A，则f[i] = f[i-1] + 1；如果最后一个操作是Ctrl-V，我们假设最后一共有连续K个Ctrl-V，则f[i] = f[i-2-K] * (K+1)。

于是我们可以得到一个O(N^2)的DP算法。

当然本题数据范围很大，O(N^2)的DP没办法通过所有的数据。不过我们可以用这个算法得到前若干项的值。例如N=1..25的答案如下：

1 1
2 2
3 3
4 4
5 5
6 6
7 9
8 12
9 16
10 20
11 27
12 36
13 48
14 64
15 81
16 108
17 144
18 192
19 256
20 324
21 432
22 576
23 768
24 1024
25 1296

可以看出，对于N >= 16，f[N] = f[N - 5] * 4。换句话说，当N足够大的时候，最优的策略就是用Ctrl-A + Ctrl-C + Ctrl-V + Ctrl-V + Ctrl-V 5个操作把长度变成4倍。

于是f[N] = f[x] * 4^K， 其中11 <= x <= 15 且 N = x + 5K。其中4^K需要用快速幂实现。