[ABC275D] Yet Another Recursive Function 题解

FFTotoro · 2022-11-02 18:09:00 · 题解

本题可以使用记忆化搜索。

用一个 std::map 来存储 f(i) 的值。

具体地，按照题目要求，f(i)=f\left(\left\lfloor\frac{i}{2}\right\rfloor\right)+f\left(\left\lfloor\frac{i}{3}\right\rfloor\right)，每计算到一个答案，就将它存入 map 中。下次再求解到同样的直接返回 map 中存储的元素即可。

时间复杂度 O(\log^2 N)，可以轻易地通过本题。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
map<int,int> m; // 存储答案的 map
int f(int n){
  if(m[n])return m[n]; // 存储过答案
  if(!n)return m[0]=1; // 递归边界
  return m[n]=f(n>>1ll)+f(n/3);
}
main(){
  int n; cin>>n;
  cout<<f(n)<<endl;
  return 0;
}