思路
为使描述方便，先令题目描述中的“完美序列”反转（即序列单调递增且每一个数都是上一个数的倍数）。原“完美序列”与反转后的本质相同。
先考虑最大长度。
显然，当完美序列为 \(1,2,4,…,2^k\ (2^k\le n<2^{k+1}\text{，即 }k=\left\lfloor\log_2n\right\rfloor)\) 时长度最大，长度为 \(k+1\)（下文的 \(k\) 均指代 \(\left\lfloor\log_2n\right\rfloor\)）。
考虑有没有其他符合要求且长度为 \(k+1\) 的序列。
序列的所有数都小于等于 \(n\)，等价于序列的最大值小于等于 \(n\)。序列的最大值可以看作是 \(k\) 个大于 \(1\) 的正整数相乘，目前 \(k\) 个数都是 \(2\)。考虑调整这 \(k\) 个数。
-
如果调整一个 \(2\)，将其变成 \(3\)，那么最大值为 \(2^{k-1}\times3\)，可能小于等于 \(n\)；但如果将一个 \(2\) 变为 \(4\)，那么最大值为 \(2^{k-1}\times4=2^{k+1}>n\)，因此不可以，而将 \(2\) 变为大于 \(4\) 的数显然也不可以。
-
如果调整两个 \(2\)，将其变成两个 \(3\)，那么最大值为 \(2^{k-2}\times3^2>2^{k-2}\times2^3>n\)，因此不可以调整两个 \(2\)。调整两个以上的 \(2\) 显然也不可以。
综上，符合条件的序列只有以下两种情况：
-
\(\begin{cases}a_1=1\\a_i=a_{i-1}\times2&i\in[2,k+1]\end{cases}\)
-
\(\begin{cases}a_1=1\\a_i=a_{i-1}\times2&i\in[2,k+1]\text{ 且 }i\ne t\\a_t=a_{t-1}\times3&t\text{ 为 }[2,k+1]\text{ 中的一个常数}\end{cases}\)
第一种情况一定成立，第二种情况在 \(2^{k-1}\times3\le n\) 时才成立。
因此，总共有 \(1\) 种或 \(k+1\) 种不同的最长完美序列。
不管有几种序列，所有最长完美序列的长度都是一样的，因此他们在所有 \(n\) 的排列中出现的次数都相同。我们只需计算出所有序列的价值之和，再乘上每一种序列的出现次数即可。
计算每一种序列的出现次数只需用插板法，原本有 \(k+1\) 个不同的数，需在其中不断插入不同的数，直到最终有 \(n\) 个数，因此出现次数为 \((k+2)\times(k+3)\times …\times n=\dfrac{n!}{(k+1)!}\)。
设所有最长完美序列的价值之和为 \(sum\)，答案即为 \(sum\times\dfrac{n!}{(k+1)!}\)。
对于每次询问，计算 \(sum\) 的时间复杂度为 \(O(\log^2n)\)；预处理 \(n\) 以内的阶乘与阶乘逆元的时间复杂度为 \(O(n)\)。因此总时间复杂度为 \(O(Tn+\log^2n)\)。
代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline int read() {
int s=0,f=1; char ch=getchar();
while (ch<48 || ch>57) {if (ch=='-') f=-1; ch=getchar();}
while (ch>=48 && ch<=57) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}
return s*f;
}
const int N=1e6+5,P=1e9+7;
LL fac[N],facinv[N];
LL getinv(LL x) {
LL res=1;
for (int y=P-2;y;y>>=1) {
if (y&1) res=res*x%P;
x=x*x%P;
}
return res;
}
void init(int n) {
fac[0]=1;
for (int i=1;i<=n;++i)
fac[i]=fac[i-1]*i%P;
facinv[n]=getinv(fac[n]);
for (int i=n;i>=1;--i)
facinv[i-1]=facinv[i]*i%P;
}
int T,n;
int main() {
init(1e6);
T=read();
while (T--) {
n=read();
int k=log2(n);
LL sum=(1<<k+1)-1;
if ((1<<k-1)*3<=n) {
for (int i=1;i<=k;++i) {
int x=1; sum=(sum+1)%P;
for (int j=1;j<=k;++j) {
if (i==j) x*=3;
else x<<=1;
sum=(sum+x)%P;
}
}
}
printf("%lld\n",sum*(fac[n]*facinv[k+1]%P)%P);
}
return 0;
}
\(\text{114ms / 15.71MB}\)
原文地址：http://www.cnblogs.com/2Bpencil/p/16861471.html
