题解 P1028 【数的计算】
Vel_
2019-01-25 20:44:15
## Code $O(n)$
### Force 25% $O(n^n)$
递归是过不了的。。与Fibonacci相似。可以分析递归复杂度。
$(n) = \sum_{i=1}^{n/2}f(i)+o(1)$
求上界的话，放缩一下：
$f(n) = nf(n-1)+o(1)$
显然，递推一下就有（$n!=O(n^n)$），比指数还吓人。。
$f(n) = O(n^n)$
```c++
#include <bits/stdc++.h>
using namespace std;
int f(int n){
if(n == 1) return 1;
int result = 0;
for(int i = 1; i <= n/2; ++i) //通项
result += f(i);
return result + 1; //算上自己
}
int main(){
int n; cin>>n;
cout<<f(n);
}
```
### Force+记忆剪枝 $O(n^2)+O(n)$
```c++
#include <bits/stdc++.h>
using namespace std;
int f_remember[1005];
int f(int n){
if(n == 1) return 1;
if(f_remember[n]) return f_remember[n];
int result = 0;
for(int i = 1; i <= n/2; ++i)
result += f(i);
return f_remember[n] = result + 1; //记忆
}
int main(){
int n; cin>>n;
cout<<f(n);
}
```
### 迭代/传播 $O(n^2)+O(n)$
> 此方法相当于记忆剪枝的迭代版改写。
状态方程：（先求小，再求大）
$f(n) = \sum_{i=1}^{n/2}f(i), f(1)=1$
注意到从递推式的基本项可以向上**传播**。
```c++
#include <bits/stdc++.h>
using namespace std;
int f[1005];
int main(){
int n; cin>>n;
f[1] = 1;
for(int i = 2; i <= n; ++i){
for(int j = 1; j <= i/2; ++j) //通项
f[i] += f[j];
f[i] ++; //算上自己
}
cout<<f[n];
}
```
### 递推优化 $O(n)+O(0.5n)$
注意到，
$f(n) = \sum_{i=1}^{n/2}f(i)+o(1),\quad f(n-1) = \sum_{i=1}^{(n-1)/2}f(i)+o(1)$
> 显然每一步的**求和**中，**存在大量的重复计算**。
递推公式可以优化为：
$f(n) = SUM(n/2)+1,\quad SUM(i) = SUM(i-1)+f(i)$
这时内部求和的$O(n)$变为分摊常数。同样可以采用递归或迭代方法。
#### 记忆剪枝 $O(n)+O(n)$
```c++
#include <bits/stdc++.h>
using namespace std;
int f[1005], sum[505];
int F(int i); int Sum(int i);
int main(){
int n; cin>>n;
f[1] = sum[1] = 1;
cout<<F(n);
}
int F(int i){
if(f[i]) return f[i]; //剪枝
return f[i] = Sum(i/2) + 1; //利用赋值，记忆
}
int Sum(int i){
if(sum[i]) return sum[i]; //剪枝
return sum[i] = Sum(i - 1) + F(i); //利用赋值，记忆
}
```
#### 迭代传播 $O(n)+O(n)$
```c++
#include <bits/stdc++.h>
using namespace std;
int f[1005], sum[505];
int main(){
int n; cin>>n;
f[1] = 1;
for(int i = 2; i <= n; ++i){
sum[i/2] = sum[i/2 - 1] + f[i/2];
f[i] = sum[i/2] + 1;
}
cout<<f[n];
}
```
#### 就地传播 $O(n)+O(0.5n)$
> 前面两种的空间准确来讲其实是$O(n)+O(1.5n)$。通过就地可以进行空间优化。
>
> 理论上任何传播算法都可以做到就地，因为每一状态都只与**紧邻的前一状态**有关。
>
> 由于本题的**<font color=red>两个</font>**传播公式**相互耦合**，同时实现两个状态的就地传播是**不可能的**。
>
> > 可以理解为：当`i`取值较大时，`sum`的某一项`sum[i]`可以传播到`f`相对很远的两项`f[2i],f[2i+1]`，为了之后计算`sum[2i]`和`sum[2i+1]`，`f`的两项必须被动态缓存起来。可以预见，最多的缓存项可以达到$n/4$的规模。
>
> 但是，`sum`和`f`**分别的就地传播**，两种方案都可行。如下图所示：
再关注一下递推公式：
$f(n) = SUM(n/2)+1,\quad SUM(i) = SUM(i-1)+f(i)$
于是我们可以由此写就地传播辣~～
##### **sum就地**： $O(n)+O(1.0n)$
```c++
#include <bits/stdc++.h>
using namespace std;
int f[1005], sum;
int main(){
int n; cin>>n;
for(int i = 1; i <= n; i++){
f[i] = sum + 1;
if(i%2) sum += f[(i+1)/2];
}
cout<< f[n];
}
```
##### **f就地**： $O(n)+O(0.5n)$
```c++
#include <bits/stdc++.h>
using namespace std;
int f, sum[505];
int main(){
int n; cin>>n;
for(int i = 1; i <= n/2; i++){
f = sum[i/2] + 1;
sum[i] = f + sum[i - 1];
}
cout<< sum[n/2] + 1;
}
```
#### 就地+队列 $O(0.5n)+O(0.25n)$
我们之前已经提到，`f`可以用动态缓存的方式记录。并且，每一个`f[i]`的调用都是先进先出的，因此可以采用队列。。
> `sum`只要求到`n/2`就可以求出`f[n]`，`sum`只要求到`n/4`就可以求出`f[n/2]`。
>
> 因此，`sum`求到`n/4`（此时积累了`n/4`的缓存），然后卸载缓存到`f[n/2]`求得`sum[n/2]`，即可求出`f[n]`。如图：
```c++
#include <bits/stdc++.h>
using namespace std;
queue<int> f; int sum = 0; //sum[0] = 0
int main(){
int n; cin>>n;
int i;
f.push(1); //initialize f as sum[1]
for(i = 1; i <= (n >> 2); i++){
sum += f.front(); f.pop(); //reserve f in queue buffer
f.push(sum+1); f.push(sum+1);
}
for( ; i <= (n >> 1); i++){
sum += f.front(); f.pop(); //clear the buffer(maybe 1 element left sometime)
}
cout<< sum + 1;
}
```