AcWing 428.数列
题目描述
给定一个正整数$k$,把所有$k$的方幂及所有有限个互不相等的$k$的方幂之和构成一个递增的序列.
例如,当$n=3$时,序列为:
$1(3^0),3(3^1),4(3^0+3^1),9(3^2),10(3^0+3^2),12(3^1+3^2),13(3^0+3^1+3^2),…$
请你求出这个序列的第$n$项的值.
$3\leq k \leq 15,10\leq n \leq 1000$
样例
输入数据:
3 100
输出数据:
981
方法1.枚举/打表
因为$k,n$的范围都很小,考虑枚举或打表,这里不过多赘述.
方法2.二进制拆分
首先思考一个问题:序列中第$n$个数为哪几项之和?
不难发现,第$n$个数为$n$的二进制拆分后,按最后一位为第$0$位计算,第$i$位为$1$的$\sum k^i$.
以样例数据为例:
$(100)_{10}=(1100100)_2$.
所以第$100$个数即为$3^2+3^5+3^6=981$.
下面讲一下做法:
观察数据范围:$10\leq n\leq 1000$,又因为$2^{10}=1024>1000$,所以最终的结果最大只会包含$k^9$.
这里我们预处理出num[]
数组,其中num[i]
存储$k^i$的值.
获取答案时只需将$n$每次右移$1$位后,判断末位是否为$1$,末位为$1$则ans+=num[i]
.
直到$n=0$时,最后结果即为正确答案.
时间复杂度 $O(\log n)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int k,n,ans;
int num[10];
//预处理
void init(){
num[0]=1;
for(int i=1;i<10;i++)
num[i]=num[i-1]*k;
}
//获取答案
void getans(){
for(int i=0;n;i++,n>>=1)
if(n&1) ans+=num[i];
}
int main(){
scanf("%d%d",&k,&n);
init();
getans();
printf("%d",ans);
return 0;
}
看y总的没看懂,看你的看明白了谢谢