C++(g++ 7.5.0) 解法, 执行用时: 961ms, 内存消耗: 4348K, 提交时间: 2022-10-03 23:33:35

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;

vector<int>jie;
unordered_map<int,int>mp[35];
int maxdeep;
int dfs(int n,int k)
{
	//if(k==0)return 1;
	//assert(k>=1);
	if(k==maxdeep)return 1;
	
	if(n==0 || n==1)return 0;
	//assert(n>=2);
	//if(mp.count({n,k}))return mp[{n,k}];
	if(mp[k].count(n))return mp[k][n];
	
	int res=0;
	int zzjie=0;
	int l=2,r;
	while(l<=n)
	{
		r=n/(n/l);
		//if(r>jie[zzjie])r=jie[zzjie];
		
		assert(n/l==n/r);
		int val=dfs(n/l,k+1);
		//res+=1LL*val*(zzjie+1)%mod*(r-l+1)%mod , res%=mod;
		long long tt=0;
		while(jie[zzjie]<r)
		{
			tt+=1LL*(zzjie+1)*(jie[zzjie]-l+1);
			l=jie[zzjie]+1 , ++zzjie;
		}
		tt+=1LL*(zzjie+1)*(r-l+1);
		
		res+=tt%mod*val%mod , res%=mod;
		
		l=r+1;
		while(l>jie[zzjie])++zzjie;
	}
	
	return mp[k][n]=res;
}
int main()
{
	for(int i=2;i<=200000005;i*=2)
	{
		jie.push_back(i);
	}
	int n,k;
	scanf("%d%d",&n,&k);
	maxdeep=k;
	int ans=dfs(n,0);
	printf("%d\n",ans);
	return 0;
}

C++(clang++11) 解法, 执行用时: 466ms, 内存消耗: 4492K, 提交时间: 2021-01-22 21:20:13

#include<stdio.h>
#include<unordered_map>
const int mod=1000000007;
int n,k;
std::unordered_map<int,int> mp[27];
int upLog(int x)
{
	int r=0;
	int v=1;
	while(v<x)
	{
		r++;
		v<<=1;
	}
	return r;
}
int getF(int n,int k)
{
	if(k>=27)
	return 0;
	if(mp[k].find(n)!=mp[k].end())
	return mp[k][n];
	if(k==0)
	return mp[k][n]=1;
	else
	{
		int &cur=mp[k][n];
		for(int w=1;(1<<w)<=n*2;w++)
		{
			int L,R;
			L=(1<<(w-1))+1;
			R=std::min(1<<w,n);
			for(int j=L;j<=R;j++)
			{
				int vl=n/j;
				int r=std::min(R,n/vl);
				cur=(cur+1ll*w*(r-j+1)%mod*getF(vl,k-1))%mod;
				j=r;
			}
		}
		return cur;
	}
}
int main()
{
	scanf("%d%d",&n,&k);
	printf("%d\n",getF(n,k));
}