【整除分块】【DP】ABC239Ex Dice Product 2 题解

ABC239H

简单题。

令 \(f_i\) 表示乘到 \(\ge i\) 的期望。

容易得到 \(f_i=\dfrac{\sum\limits_{j=1}^{n}f_{\lceil\frac{i}{j}\rceil}}{n}\)。

将 \(f_i\) 移到同一边，去掉系数，有 \(f_i=\dfrac{n\sum\limits_{j=2}^{n}f_{\lceil\frac{i}{j}\rceil}}{n-1}\)。

提出 \(\frac{n-1}{n}\) 后显然可以使用数论分块计算后面的一部分。由于有很多 \(f\) 的值并不会用到，采用记忆化搜索即可，注意实现的细节。

使用 umap 后，时间复杂度为 \(\mathcal{O}(n^{\frac{3}{4}})\)，空间复杂度 \(\mathcal{O}(n^{\frac{1}{2}})\)。

代码：

#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
int n,m;
unordered_map<int,int> f;

int power(int a,int b){
	int res=1;
	for(;b>0;a=1ll*a*a%mod,b>>=1)if(b&1)res=1ll*res*a%mod;
	return res;
}
int dfs(int x){
	if(x==1)return 0;
	if(f[x])return f[x];
	for(int l=2,r;l<=n;l=r+1){
		if((x-1)/l==0)r=n;
		else r=min(n,(x-1)/((x-1)/l));
		f[x]=(f[x]+(r-l+1)*1ll*dfs((x-1)/l+1)%mod)%mod;
	}
	f[x]=(1ll*f[x]%mod+n)*power(n-1,mod-2)%mod;
	return f[x];
}

int main(){
	cin>>n>>m;
	cout<<dfs(m+1)<<"\n";
	return 0;
}