CF1174E

非常好题目，使我的大脑旋转（？）

还是一样，介绍思路。

既然题目让我们计算 $f_{\max}(n)$ 的数量，则先考虑 $f_{\max}(n)$ 的值怎样求得。容易发现，设 $n=\prod p_i^{k_i},p_i\in \operatorname{prime}$ ，则 $f(n)=\sum k_i+1$ 。注意是 $f(n)$ 不是 $f_{\max}(n)$ 。简单贪心，发现当 $x=2^m$ 时， $f(x)$ 会尽可能大。

但是还需要知道有没有其他可能的 $x$ 会有一样大的结果。首先发现 $x$ 不能为一个大于 $3$ 的质数的倍数，否则一定可以拆成至少两个 $2$ ，这样更优。并且， $3$ 对应的指数不能 $>1$ ，因为 $3^2>2^3$ ，就可以拆成 $3$ 个 $2$ 了。

综上，得出结论： $f_{\max}(n)$ 会在这样的 $f(x)$ 中取到：设 $k=\left\lfloor \log x\right\rfloor$ ， $x=2^k$ 或 $x=2^{k-1}\times 3$ 。

对于这两个数，他们有一个性质：因数不会太多。也就意味着， $f_{\max}(n)$ 里包含的不同的前缀 $\gcd$ 可能取到的值的数量是 $O(\log n)$ 级别的。

于是可以考虑 dp，并存下来当前选了几个数，以及前缀 $\gcd$ 。转移则考虑当前 $\gcd$ 没变/为原来 $\dfrac{2}{1}$ /为原来 $\dfrac{3}{1}$ 。具体可以手推一下。

其实状态两维就够。

code：

int n,m,k,a[N],b[N],dp[N][47];
il int Mod(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int solve(int x){
	k=0,mems(b,0);
	drep(i,n,1)if(x%i==0)a[++k]=i,b[i]=k;
	mems(dp,0),dp[1][1]=1;
	rep(i,2,n){
		rep(j,1,k){
			dp[i][j]=1ll*dp[i-1][j]*(n/a[j]-i+1)%mod;
			if(a[j]*2<=n&&b[a[j]*2])dp[i][j]=Mod(dp[i][j],1ll*dp[i-1][b[a[j]*2]]*(n/a[j]-n/(a[j]*2))%mod);
			if(a[j]*3<=n&&b[a[j]*3])dp[i][j]=Mod(dp[i][j],1ll*dp[i-1][b[a[j]*3]]*(n/a[j]-n/(a[j]*3))%mod);
		}
	}
	return dp[n][k];
}
void Yorushika(){
	scanf("%d",&n),m=__lg(n);
	int x=1<<__lg(n);
	if(x/2*3<=n)printf("%d\n",Mod(solve(x),solve(x/2*3)));
	else printf("%d\n",solve(x));
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}

感谢您的支持，我会继续努力的!