题解 P8757 [蓝桥杯 2021 省 A2] 完美序列
题意
如果一个序列是单调递减的，而且除了第一个数以外的任何一个数都是上一个数的因数，则称这个序列为一个完美序列。
一个序列中的一个子序列如果是完美序列，则称为该序列的一个完美子序列。一个序列的最长完美子序列长度，称为该序列的完美长度。
给定正整数 \(n\)，\(1\) 至 \(n\) 的所有排列的完美长度的最大值，称为 \(n\) 阶最大完美长度。
给定正整数 \(n\)，请求出 \(1\) 至 \(n\) 的所有排列中长度正好为 \(n\) 阶最大完美长度的所有完美子序列的价值的和。
思路
显然地，\(n\) 阶最大完美长度 \(len=\lfloor\log_2n\rfloor+1\)，因为从 \(highbit(n)\) 开始，每次除 \(2\) 一定不会更劣。
考虑如何证明。考虑每次除的数，构成了一个长为 \(len-1\) 的序列。
- 如果替换掉一个数。显然只可能替换成质数。
如果 \(n\ge\frac{3}{2}highbit(n)\)，那么可以将序列中的一位替换成 \(3\)，此时最大完美长度不变。
如果替换成 \(5\)，显然 \(n<\frac{5}{2}highbit(n)\)。这样最大位就比 \(n\) 大了，肯定是不行的。
大于 \(5\) 的数同理。
因此，只可能把序列中的某位替换成 \(3\)。 - 如果替换掉多个数。还是值可能替换成质数。
如果替换两个 \(3\)，显然 \(n<\frac{9}{4}highbit(n)\)。这样最大位就比 \(n\) 大了，肯定不行。
显然，如果替换成更大或者更多的数，也一定不行。
在这个过程中，我们发现，这个序列中，只可能有 \(2\) 和 \(3\)，而且最多只会有一个 \(3\)。
考虑计算每个数可以贡献多少次。假设现在是从小到大的第 \(i\) 个数，这个数为 \(x\)。
首先，要在 \(n\) 个位置中选 \(len\) 个位置作为完美序列，剩下的 \(n-len\) 个位置随便排，这部分是 \(\binom{n}{len}\times(n-len)!\)。
现在排列的位置确定了，考虑有多少种排列会让 \(x\) 产生贡献。
- 如果 \(x\) 的因子中没有 \(3\)，那么如果 \(n\ge\frac{3}{2}highbit(n)\)，则有 \(len-i\) 个位置可以被替换成 \(3\)。
再加上全部是 \(2\) 的一种，总共就是 \(1+[可以有3](n-len)\) 种。 - 如果 \(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)\)，卡到了本题最优解（2023.6.30）。
@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;
}