P8757 完美序列 题解

· · 题解

首先考虑对于一个确定的 n ，n 阶最大完美长度是多少？

不难发现，由于完美子序列后一项是前一项的因子，排列又没有重复元素，所以完美子序列每一项至少除以二，那最优的子序列当然是 2^k,2^{k-1},2^{k-2},....,2^{0} 如此排列，那么 n 阶最大完美长度就应该为 \lfloor \log n \rfloor + 1 ，接下来我们用 x 代替。

确定完 x 的值，我们接下来试着推导一下对于一个 1 到 n 的排列，它可能的长度等于 x 的完美子序列有哪些？

首先一个直观也可说是省事的想法就是只有上面所说的最优子序列一种，可当 n = 3 时我们发现 (3,1) 就出现了例外。这时不要急于否定自己，让我们仔细想想这样的例外多吗？

其实是不多的。从 x 的表达式可以看出，类似 2^k - 1 的这种 n 最容易出现例外，当你随便列举几个例如 3,7,15 这样的 n 时就会发现：咦？好像例外最多就是在某一处相邻两项不是二倍关系，而是三倍关系。

这也很容易证明：因为完美子序列必须满足有 x 项，第一项又不能超过 2^x - 1 ，那么如果存在一个有多个三倍关系或者一个更高倍关系的子序列，那 n 阶最大完美长度的值就不会只是 x 了。

那么哪些 n 可能出现例外呢？必须是满足 2^{x-2} \times 3 \leq n 才行。否则就只有最优子序列一种情况。

既然已经确定了有哪些类型的长度为 x 的完美子序列，那接下来就是计算贡献了。

由于贡献是由子序列而来，而不是排列而来，所以我们只需要算出每种合法子序列的权值和，乘上它们在排列中的出现次数，再加起来就行，不需要担心因为两个合法子序列出现在一个排列而算重。

首先看次数，因为每种合法子序列长度相同，且都是在排列中，所以在所有排列中出现的次数也应相同。考虑 x 个数首先排好，剩下 n-x 个数随便排，就是 (n-x)! ，然后我们需要把两组数按序并在一起，用插板法可得方案数为 n \choose x ，那么出现次数就为 (n-x)! \times {n \choose x} 。

接下来看权值和，首先最优子序列的权值和好说，就是 2^x - 1 。而对于例外，相邻两项的商一定是 x-2 个 2 和 1 个 3 ，那么根据 3 的位置的不同就可以列出以下合式：

\sum_{k=0}^{x-2}{(\sum_{i=0}^{k}{2^i} + \sum_{i=k}^{x-2}{3 \times 2^i})}

其中外层 k 是枚举 3 的位置，内层是分两部分计算权值和。

接下来再利用一些基本的和式技巧，就可以得到以下答案：

(3 \times x -4) \times 2^{x-1} - x + 2

那到此为止，这道题就完成了，时间复杂度 O(n) ，下附代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=1e6+10,mod=1e9+7;
int T,Log[N],pw[N],fct[N],inv[N],finv[N];
inline void init()
{
    pw[0]=fct[0]=inv[0]=finv[0]=fct[1]=inv[1]=finv[1]=1;
    pw[1]=2;
    for(int i=2;i<N;i++)
    {
        Log[i]=Log[i/2]+1;
        pw[i]=pw[i-1]*2%mod;
        fct[i]=(LL)fct[i-1]*i%mod;
        inv[i]=(mod-(LL)mod/i*inv[mod%i]%mod)%mod;
        finv[i]=(LL)finv[i-1]*inv[i]%mod;
    }
}
inline LL C(int x,int y)
{
    return (LL)fct[x]*finv[y]%mod*finv[x-y]%mod;
}
int main()
{
    init();
    scanf("%d",&T);
    while(T--)
    {
        int n,x,ans;
        scanf("%d",&n);
        x=Log[n]+1;
        ans=(LL)fct[n-x]*C(n,x)%mod*(pw[x]-1)%mod;
        if(x>=2&&pw[x-2]*3<=n)  ans=(ans+(LL)fct[n-x]*C(n,x)%mod*((((LL)x*3%mod-4+mod)%mod*pw[x-1]%mod-x+mod+2)%mod)%mod)%mod;
        printf("%d\n",ans);
    }
    return 0;   
}