526互联

题解 P8757 [蓝桥杯 2021 省 A2] 完美序列

发布时间 2023-06-30 10:15:03作者: 洛谷Augury

题解 P8757 [蓝桥杯 2021 省 A2] 完美序列

题意

如果一个序列是单调递减的，而且除了第一个数以外的任何一个数都是上一个数的因数，则称这个序列为一个完美序列。

一个序列中的一个子序列如果是完美序列，则称为该序列的一个完美子序列。一个序列的最长完美子序列长度，称为该序列的完美长度。

给定正整数 \(n\)，\(1\) 至 \(n\) 的所有排列的完美长度的最大值，称为 \(n\) 阶最大完美长度。

给定正整数 \(n\)，请求出 \(1\) 至 \(n\) 的所有排列中长度正好为 \(n\) 阶最大完美长度的所有完美子序列的价值的和。

思路

显然地，\(n\) 阶最大完美长度 \(len=\lfloor\log_2n\rfloor+1\)，因为从 \(highbit(n)\) 开始，每次除 \(2\) 一定不会更劣。

考虑如何证明。考虑每次除的数，构成了一个长为 \(len-1\) 的序列。

  1. 如果替换掉一个数。显然只可能替换成质数。
    如果 \(n\ge\frac{3}{2}highbit(n)\)，那么可以将序列中的一位替换成 \(3\)，此时最大完美长度不变。
    如果替换成 \(5\)，显然 \(n<\frac{5}{2}highbit(n)\)。这样最大位就比 \(n\) 大了，肯定是不行的。
    大于 \(5\) 的数同理。
    因此，只可能把序列中的某位替换成 \(3\)。
  2. 如果替换掉多个数。还是值可能替换成质数。
    如果替换两个 \(3\)，显然 \(n<\frac{9}{4}highbit(n)\)。这样最大位就比 \(n\) 大了，肯定不行。
    显然，如果替换成更大或者更多的数，也一定不行。

在这个过程中，我们发现，这个序列中，只可能有 \(2\) 和 \(3\)，而且最多只会有一个 \(3\)。

考虑计算每个数可以贡献多少次。假设现在是从小到大的第 \(i\) 个数，这个数为 \(x\)。

首先，要在 \(n\) 个位置中选 \(len\) 个位置作为完美序列，剩下的 \(n-len\) 个位置随便排，这部分是 \(\binom{n}{len}\times(n-len)!\)。

现在排列的位置确定了，考虑有多少种排列会让 \(x\) 产生贡献。

  1. 如果 \(x\) 的因子中没有 \(3\)，那么如果 \(n\ge\frac{3}{2}highbit(n)\)，则有 \(len-i\) 个位置可以被替换成 \(3\)。
    再加上全部是 \(2\) 的一种，总共就是 \(1+[可以有3](n-len)\) 种。
  2. 如果 \(x\) 的因子中有 \(3\)，那么有 \(i\) 个位置可以放 \(3\)。
    总共就是 \([可以有3]len\) 种。

枚举即可，复杂度 \(O(n\log n+n\log P)\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int ans=0;bool op=0;char ch=getchar();
	while(ch<'0'||'9'<ch){if(ch=='-')op=1;ch=getchar();}
	while('0'<=ch&&ch<='9'){ans=(ans<<1)+(ans<<3)+(ch^48);ch=getchar();}
	if(op)return -ans;
	return ans;
}
const int maxn=1e6+10;
const int mod=1e9+7;
int n;
int fact[maxn];
int ifac[maxn];
int len;
int base;
int ans=0;
int inv(int a){
	int ans=1;
	for(int i=mod-2;i;i>>=1){
		if(i&1)ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
int C(int a,int b){
	if(b>a||a<0||b<0)return 0;
	return fact[a]*ifac[b]%mod*ifac[a-b]%mod;
}
void real_main(){
	n=read();
	if(n==1){
		puts("1");
		return;
	}
	len=__lg(n)+1;
	base=1;
	ans=0;
	for(int i=1;i<=len;i++){//只有2的
		ans=(ans+C(n,len)*base%mod*fact[n-len]%mod)%mod;
		base<<=1;
	}
	if((1<<(len-2))*3>n){
		cout<<ans<<'\n';
		return;
	}
	base=1;
	for(int i=1;i<=len;i++){//不含3的
		ans+=C(n,len)*base*(len-i)%mod*fact[n-len]%mod;
		ans%=mod;
		base<<=1;
	}
	base=3;
	for(int i=2;i<=len;i++){//含3的
		ans+=C(n,len)*base*(i-1)%mod*fact[n-len]%mod;
		ans%=mod;
		base<<=1;
	}
	cout<<ans<<'\n';
}
signed main(){
	fact[0]=1;
	for(int i=1;i<maxn;i++)fact[i]=fact[i-1]*i%mod;
	for(int i=0;i<maxn;i++)ifac[i]=inv(fact[i]);
	int T=read();
	while(T--)real_main();
	return 0;
}

优化

这样已经可以过了，但是还可以优化一下。

容易发现，每个式子都含有C(n,len)*fact[n-len]。

定义 \(tot=\binom{n}{len}*(n-len)!\)，即可避免预处理逆元。

或者，容易发现，\(\binom{n}{len}\times(n-len)!=\frac{n!}{len!}\)，而 \(len=\lfloor\log_2n\rfloor+1\)。所以只要预处理出前 \(20\) 个阶乘的逆元即可。

观察全 \(2\)，除了 \(tot\) 之外的部分等于 \(\sum_{i=1}^{len}2^{i-1}=\sum_{i=0}^{len-1}2^i=2^{len}-1\)。

观察不含 \(3\)，除了 \(tot\) 之外的部分：

\[\begin{align} &f(len)\nonumber\\ =&\sum_{i=1}^len2^{i-1}(len-i)\nonumber\\ =&\sum_{i=1}^{len-1}2^{i-1}(len-1-i+1)\nonumber\\ =&\sum_{i=1}^{len-1}2^{i-1}(len-1-i)+\sum_{i=1}^{len-1}2^{i-1}\nonumber\\ =&f(len-1)+\sum_{i=0}^{len-2}2^i\nonumber\\ =&f(len-1)+2^{len-1}-1\nonumber\\ \end{align} \]

观察含 \(3\)，除了 \(tot\) 之外的部分 \(g(len)=g(len-1)+base\times(len-1)\)。\(base\) 的含义见上面的代码。

现在，我们把每一个计算都优化成了递推，可以预处理。单次询问 \(O(1)\)。

复杂度 \(O(T+\log_2n)\)。卡到了本题最优解。

提交记录

@TQI_II为机房公用账号，上面也是我交的，会在下面发个评论证明一下。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int ans=0;bool op=0;char ch=getchar();
	while(ch<'0'||'9'<ch){if(ch=='-')op=1;ch=getchar();}
	while('0'<=ch&&ch<='9'){ans=(ans<<1)+(ans<<3)+(ch^48);ch=getchar();}
	if(op)return -ans;
	return ans;
}
const int maxn=1e6+10;
const int mod=1e9+7;
int n;
int fact[maxn];
int ifac[maxn];
int len;
int base;
int ans=0;
int pre2[maxn];
int pre23[maxn];
int pre33[maxn];
int inv(int a){
	int ans=1;
	for(int i=mod-2;i;i>>=1){
		if(i&1)ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
signed main(){
	fact[0]=1;
	for(int i=1;i<maxn;i++)fact[i]=fact[i-1]*i%mod;
	ifac[20]=inv(fact[20]);
    for (int i=19;i>=0;i--)ifac[i]=(ifac[i+1]*(i+1))%mod;
	base=1;
	for(int i=1;(1<<(i-1))<maxn;i++){
		pre2[i]=(pre2[i-1]+base)%mod;
		pre23[i]=(pre23[i-1]+base-1)%mod;
		base<<=1;
	}
	base=3;
	for(int i=2;(1<<(i-1))<maxn;i++){
		pre33[i]=(pre33[i-1]+base*(i-1))%mod;
		base<<=1;
	}
	int T=read();
	while(T--){
		n=read();
		if(n==1){
			puts("1");
			continue;;
		}
		len=__lg(n)+1,ans=0;
		int tot=fact[n]*ifac[len]%mod;
		ans=(ans+pre2[len]*tot%mod)%mod;
		if((1<<(len-2))*3>n)cout<<ans<<'\n';
		else cout<<(ans+tot*(pre23[len]+pre33[len])%mod)%mod<<'\n';
	}
	return 0;
}