洛谷1062 数列[数论]

题目描述

给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是:
1,3,4,9,10,12,13,…
(该序列实际上就是:3^0,3^1,3^0+3^1,3^2,3^0+3^2,3^1+3^2,3^0+3^1+3^2,…)
请你求出这个序列的第N项的值(用10进制数表示)。
例如,对于k=3,N=100,正确答案应该是981。

输入输出格式

输入格式:

输入文件只有1行,为2个正整数,用一个空格隔开:
k N (k、N的含义与上述的问题描述一致,且3≤k≤15,10≤N≤1000)。

输出格式:

输出文件为计算结果,是一个正整数(在所有的测试数据中,结果均不超过2.1*109)。(整数前不要有空格和其他符号)。

输入输出样例

输入样例#1:

3 100

输出样例#1:

981

说明

NOIP 2006 普及组 第四题

题解

以下是痴狂的飞鼠的解释,然后改动了一点:
我们在弄清了题意之后,来找一下规律
假设k=3,将数据排列出来,就可以得到下面的序列(省略3^):
0,1,0+1,2,0+2,1+2,0+1+2,3,0+3,1+3,0+1+3,2+3,0+2+3,1+2+3,0+1+2+3……
好像没有什么规律哎……
但是!我们把上面的序列加上分割线,然后加上括号:
0 | 1 , 1+0 | 2 , 2+0 , 2+1 , 2+(1+0) | 3 , 3+0 , 3+1 , 3+(1+0) , 3+2 , 3+(2+0) , 3+(2+1) , 3+(2+(1+0))…… 好像有规律了……
我们可以看出,第一部分有1项,第二部分有2项。第n部分就有2^n项
第n部分的第一项就是k^n,第n部分的第二项就是k^n+f[1],第n部分的第i项就是k^n+f[i-1],规律就找到了~
但是题目的数据好像有点问题,cpp和c可以用%d输出,pascal只能加一个特判语句了~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<set>    
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm> //一大堆头文件
#define LL unsigned long long
using namespace std;
long long a[10];//1024是2^10,1000<1024,所以0~9够了
long long f[1010];//long long 防炸
int main()
{
long long k,n;
cin>>k>>n;
int i,j;
a[0]=1;//求出k^0~k^9
int s=1;
for (i=1;i<=9;i++)
a[i]=a[i-1]*k;//这样推比用pow要快些吧。
for (i=0;i<=9;i++)//分成九段去枚举 a[i]表示第i段的开头的值
{
f[s]=a[i];//找规律可得第i组的第一个是k^i
for (j=1;j<=s;j++)
f[s+j]=f[s]+f[j];//开始找规律得到的,f[i]=f[这一段的第一个的位置]+f[i-这一段的第一个的位置]
s*=2;// s表示2^i 相当于pow(2,i);
if (f[n]!=0)//如果f[n]求出来了
{
printf("%d",f[n]); //用%d才能a,不然就要打标
return 0;//节约时间
}
}
return 0;
}