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

· · 题解

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

题意

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

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

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

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

思路

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

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

  1. 如果替换掉一个数。显然只可能替换成质数。 如果 n\ge\frac{3}{2}\operatorname{highbit}(n)，那么可以将序列中的一位替换成 3，此时最大完美长度不变。 如果替换成 5，显然 n<\frac{5}{2}\operatorname{highbit}(n)。这样最大位就比 n 大了，肯定是不行的。 大于 5 的数同理。 因此，只可能把序列中的某位替换成 3。
  2. 如果替换掉多个数。还是值可能替换成质数。 如果替换两个 3，显然 n<\frac{9}{4}\operatorname{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}\operatorname{highbit}(n)，则有 len-i 个位置可以被替换成 3。 再加上全部是 2 的一种，总共就是 1+\left [n\ge\frac{3}{2}\operatorname{highbit}(n)\right](n-len) 种。
  2. 如果 x 的因子中有 3，那么有 i 个位置可以放 3。 总共就是 \left[n\ge\frac{3}{2}\operatorname{highbit}(n)\right]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}\times(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{array}{c} f(len)\\ =\sum_{i=1}^len2^{i-1}(len-i)\\ =\sum_{i=1}^{len-1}2^{i-1}(len-1-i+1)\\ =\sum_{i=1}^{len-1}2^{i-1}(len-1-i)+\sum_{i=1}^{len-1}2^{i-1}\\ =f(len-1)+\sum_{i=0}^{len-2}2^i\\ =f(len-1)+2^{len-1}-1 \end{array}

观察含 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;
}

update 2023.6.30

修 \LaTeX/kk

update 2023.7.2

修 \LaTeX/kk