首页 > 其他分享 >洛谷P8757 [蓝桥杯 2021 省 A2] 完美序列 题解

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

时间:2022-11-05 22:12:52浏览次数:91  
标签:ch 洛谷 int 题解 最大值 蓝桥 完美 text 序列

思路

为使描述方便,先令题目描述中的“完美序列”反转(即序列单调递增且每一个数都是上一个数的倍数)。原“完美序列”与反转后的本质相同。

先考虑最大长度。

显然,当完美序列为 \(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\) 显然也不可以。

综上,符合条件的序列只有以下两种情况:

  1. \(\begin{cases}a_1=1\\a_i=a_{i-1}\times2&amp;i\in[2,k+1]\end{cases}\)

  2. \(\begin{cases}a_1=1\\a_i=a_{i-1}\times2&amp;i\in[2,k+1]\text{ 且 }i\ne t\\a_t=a_{t-1}\times3&amp;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}\)

标签:ch,洛谷,int,题解,最大值,蓝桥,完美,text,序列
From: https://www.cnblogs.com/2Bpencil/p/16861471.html

相关文章

  • 洛谷P8775 [蓝桥杯 2022 省 A] 青蛙过河 题解 贪心+二分答案
    题目链接​​https://www.luogu.com.cn/problem/P8775​​题目大意小青蛙住在一条河边,它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。河里的石头排成了一条......
  • 洛谷-P8814 题解
    前言蒟蒻感叹!许多大佬的思路真的很复杂,于是为了部分没学过的人写了这篇题解(其实就是为了咕值),值得一看!正文♦算法:式子推导从题中可得\(\begin{cases}n_i=p_i\times......
  • 「题解报告」[POI2008]PER-Permutation
    「题解报告」[POI2008]PER-Permutation点击查看目录目录「题解报告」[POI2008]PER-Permutation思路代码不理解哪里难了,学过扩卢并且推一下式子基本就是两眼切吧。......
  • Luogu P5816[CQOI2010]内部白点题解
    LinkLuoguP5816Description一个平面直角坐标系内有\(n\)个黑点,其余点为白点,将会进行若干次变换,每次变换会把上下左右方向都有黑点的白点变成黑点,直到找不到符合要求......
  • python print 打印延迟问题解决
    转载:https://wenku.baidu.com/view/ffc89347bb4ae45c3b3567ec102de2bd9705de56.html?wkts=1667639107060&bdQuery=python+print%E7%AB%8B%E5%8D%B3%E6%89%93%E5%8D%B0......
  • 【题解】洛谷P2946 [USACO09MAR]Cow Frisbee Team S
    这题乍一看是一个朴素的01背包问题,将所有方案的集合按照能力值的和来划分成1~m,然后把m当作体积,把n当作物品数,做一个01背包的代码。于是我兴冲冲地写了代码交上去,然后十组样......
  • accoders NOI #5047. 猜数游戏 题解
    题目描述Alice和Bob玩游戏。Alice有一个\(1~n\)中的正整数\(y\)。Bob不知道这个数。游戏中的每一轮,Bob选一个正整数\(x\),并提问Alice:\(y\)是否大于等于\(x......
  • 「题解」Codeforces 1612F Armor and Weapons
    首先可以不管套件,假定\(n<m\),那么答案不超过\(\mathcal{O}(\logn+\frac{m}{n})\),也就是先倍增把\(n\)造出来,然后一步步造\(m\).答案这么小,那么常见的套路就是把答案......
  • 问题解决:vscode运行python找不到文件
    问题描述:使用VSCode执行Python代码调用其他文件时报FileNotFound错误,终于发现是VSCode工作路径默认是当前文件所在工作区的根目录,而不是当前文件所在目录。发生条件:根......
  • P8618 [蓝桥杯 2014 国 B] Log 大侠
    简要题意给你一个长度为\(n\)的正整数序列\(a\),有\(m\)个询问,每一个询问给出一个区间\([l,r]\)。定义函数\(f(x)=\lfloor\log_{2}(x)+1\rfloor\)。将\([l,r]\)的......