C++(g++ 7.5.0) 解法, 执行用时: 2ms, 内存消耗: 420K, 提交时间: 2023-03-10 18:48:16

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,mod=1e9+7;
map<ll,ll>m;
ll f(ll x)
{
    if (m[x]!=0)return m[x];
    ll y=x/2;
    m[x]=((f(y)*f(x-y+1))%mod+(f(y-1)*f(x-y))%mod)%mod;
    return m[x];
}
int main()
{
    cin>>n;
    m[1]=1;
    m[2]=1;
    m[3]=2;
    cout<<(f(n)*f(n+1))%mod;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 624K, 提交时间: 2020-02-25 13:38:02

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,mod=1e9+7;
map<ll,ll>m;
ll f(ll x)
{
	if(m[x]!=0) return m[x];
	ll y=x/2;
	m[x]=((f(y)*f(x-y+1))%mod+(f(y-1)*f(x-y))%mod)%mod;
	return m[x];
}
int main()
{
	cin>>n;
	m[1]=1;
	m[2]=1;
	m[3]=2;
	cout<<(f(n)*f(n+1))%mod;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 504K, 提交时间: 2020-08-13 18:10:49

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,mod=1e9+7;
map<ll,ll>m;
ll f(ll x){
	if(m[x]!=0) return m[x];
	ll y=x/2;
	m[x]=((f(y)*f(x-y+1))%mod+(f(y-1)*f(x-y))%mod)%mod;
	return m[x];
}
int main(){
	cin>>n;
	m[1]=1;
	m[2]=1;
	m[3]=2;
	cout<<(f(n)*f(n+1))%mod;
return 0;
}