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

· · 题解

简单组合题。

题目分析

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

假设现在这个序列由 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;
}