自动搬运

查看原文

来自洛谷，原作者为

	wangyizhi 昨夜西风凋碧树。独上高楼，望尽天涯路。

搬运于2025-08-24 22:42:09，当前版本为作者最后更新于2025-06-26 20:04:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单组合题。

题目分析

先考虑什么时候会有最长完美序列。

假设现在这个序列由 $x=\prod p_i ^ {\alpha _i}$ 开头，那么我们每次都除以其中的一个质因子得到下一项，显然这样得到的序列是最长的，且长度为 $1+\sum \alpha_i$。显然只要贪心地令 $x=2^k$，就能取到最大值，为 $k+1$。所以序列长度为 $\lfloor \log_2 n \rfloor+1$。

但其实不止 $x=2^k$ 能取到最大值。我们不妨把其中一个 $2$ 换成 $3$，得 $x'=3 \times 2^{k-1}$。若 $x'\le n$，此时也可取到最大值。但若把其中这个 $3$ 再换成 $4$，此时 $\lfloor \log_2 n \rfloor +1$ 的值就会增大，不可能。

再来求由这两种数开头的完美序列的权值和。

设 $f(k)$ 表示由 $2 \times 2^k$ 开头的序列权值和。容易发现此时只有一个序列 $2^{k+1},2^k,2^{k-1},...,2,1$，所以有 $f(k)=f(k-1)+2^{k+1}$，$f(0)=3$。

设 $g(k)$ 表示由 $3 \times 2^k$ 开头的序列权值和。把新加入的 $3 \times 2^k$ 与其余分开考虑。$3 \times 2^k$ 去掉一个质因数后可以变成 $2^k$ 或 $3 \times 2^{k-1}$，因此这部分贡献为 $f(k-1)+g(k-1)$。 由于这个序列共有 $k+2$ 项，可以在除第一项以外的任意一项去除 $3$ 这个因子，所以共有 $k+1$ 种情况，新加入的数的贡献为 $(k+1) \times 3 \times 2^k$。所以有 $g(k)=f(k-1)+g(k-1)+3(k+1)2^k$。

最后求答案。我们可以钦定使用一种数列在排列的任意位置，即在 $n$ 个位置中选 $k+1$ 个位置依次放；而剩余 $n-k-1$ 个数可以随便排，因此方案数为 $\binom{n}{k+1}(n-k-1)!$。乘上前面算出来的结果即可。

预处理复杂度 $O(n)$，单组询问复杂度 $O(1)$。

AC Code

#include<bits/stdc++.h>
//#include<bits/extc++.h>
//bool Mst;
using namespace std;
using ll=long long;
using ld=long double;
//#define int ll
using pii=pair<int,int>;
const int N=1e6+5,mod=1e9+7;
inline ll rd(ll x,ll M=mod){return x>=M?x-M:x;}
inline ll pr(ll x,ll M=mod){return x<0?x+M:x;}
namespace CM
{
	int inv[N],jc[N],invjc[N];
	void init()
	{
		inv[0]=jc[0]=invjc[0]=inv[1]=jc[1]=invjc[1]=1;
		for(int i=2;i<N;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod,jc[i]=1ll*jc[i-1]*i%mod,invjc[i]=1ll*invjc[i-1]*inv[i]%mod;
	}
	inline int C(int n,int m){return (n<0||m<0||m<n)?0:1ll*jc[m]*invjc[n]%mod*invjc[m-n]%mod;}
	inline int A(int n,int m){return (n<0||m<0||m<n)?0:1ll*jc[m]*invjc[m-n]%mod;}
}
int res2[N],res3[N];
//bool Med;
signed main()
{
//	cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
//	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	CM::init();
	res2[0]=3;
	for(int i=1,pw=4;i<=25;i++,pw=rd(pw*2)) res2[i]=rd(res2[i-1]+pw);
	res3[0]=4;
	for(int i=1,pw=6;i<=25;i++,pw=rd(pw*2)) res3[i]=(1ll*(i+1)*pw+rd(res2[i-1]+res3[i-1]))%mod;
	int t;
	cin>>t;
	while(t--) [&]()->void
	{
		int n,ans=0;
		cin>>n;
		if(n==1) return cout<<"1\n",void();
		int k=__lg(n),p=1<<k;
		ans=res2[k-1];
		if(n&(p>>1)) ans=rd(ans+res3[k-1]);
		ans=1ll*ans*CM::A(n-(k+1),n)%mod;
		cout<<ans<<"\n";
	}();
	return 0;
}