题目链接
题目描述
给定一个正整数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。
输入
输入文件sequence.in 只有1行，为2个正整数，用一个空格隔开：k N（k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）。
输出
输出文件sequence.out 为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*10^9）。（整数前不要有空格和其他符号）。
样例输入
3 100
样例输出
981
数据范围限制
做法
其实就是一道递推题。
以样例数据为准，如图。
我们设序列为
f
f
f ，会发现一个规律：
-
f 2 = f 1 ∗ k , f 3 = f 1 ∗ k + 1 f_2=f_1*k,f_3=f_1*k+1 f2=f1∗k,f3=f1∗k+1，即 3 = 1 ∗ 3 , 4 = 1 ∗ 3 + 1 3=1*3,4=1*3+1 3=1∗3,4=1∗3+1
-
f 4 = f 2 ∗ k , f 5 = f 2 ∗ k + 1 f_4=f_2*k,f_5=f_2*k+1 f4=f2∗k,f5=f2∗k+1，即 9 = 3 ∗ 3 , 10 = 3 ∗ 3 + 1 9=3*3,10=3*3+1 9=3∗3,10=3∗3+1
-
f 6 = f 3 ∗ k , f 7 = f 3 ∗ k + 1 f_6=f_3*k,f_7=f_3*k+1 f6=f3∗k,f7=f3∗k+1，即 12 = 4 ∗ 3 , 13 = 4 ∗ 3 + 1 12=4*3,13=4*3+1 12=4∗3,13=4∗3+1
-
f 8 = f 4 ∗ k , f 9 = f 4 ∗ k + 1 f_8=f_4*k,f_9=f_4*k+1 f8=f4∗k,f9=f4∗k+1，即 27 = 9 ∗ 3 , 28 = 9 ∗ 3 + 1 27=9*3,28=9*3+1 27=9∗3,28=9∗3+1
-
f 10 = f 5 ∗ k , f 11 = f 5 ∗ k + 1 f_{10}=f_5*k,f_{11}=f_5*k+1 f10=f5∗k,f11=f5∗k+1，即 30 = 10 ∗ 3 , 31 = 10 ∗ 3 + 1 30=10*3,31=10*3+1 30=10∗3,31=10∗3+1
-
f 12 = f 6 ∗ k , f 13 = f 6 ∗ k + 1 f_{12}=f_6*k,f_{13}=f_6*k+1 f12=f6∗k,f13=f6∗k+1，即 36 = 12 ∗ 3 , 37 = 12 ∗ 3 + 1 36=12*3,37=12*3+1 36=12∗3,37=12∗3+1
我们可以通过模拟直接得出答案：
#include<cstdio>
#define min(a,b) (a<b?a:b)
long long f[1001]={0,1},a=1;
int k,n,l=1;
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
scanf("%d%d",&k,&n);
while(l<=n)
{
f[++l]=a*k;
f[++l]=a*k+1;
a=f[(l+1)/2];
}
printf("%lld",f[n]);
fclose(stdin);
fclose(stdout);
return 0;
}
上述代码挺一目了然的，但是我们做这道题的方法的主题是递推，所以我们应该要用递推的方式去做这道题。
通过刚刚我们发现的规律，即可得到的递推式为： f [ i ] = f [ ( ( i − ( i f[i]=f[((i-(i f[i]=f[((i−(i% 2 ) ) / 2 ) ] ∗ k + ( i 2))/2)]*k+(i 2))/2)]∗k+(i% 2 ) 2) 2) 。
#include<cstdio>
long long f[1005];
int k,n;
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
scanf("%d%d",&k,&n);
for(int i=1;i<=n;i++) f[i]=f[((i-(i%2))/2)]*k+(i%2);
printf("%lld",f[n]);
fclose(stdin);
fclose(stdout);
return 0;
}
当然，我们通过 i i i& 1 = i 1=i 1=i% 2 2 2 可知，递推式也可以改成 f [ i ] = f [ ( ( i − ( i f[i]=f[((i-(i f[i]=f[((i−(i& 1 ) ) / 2 ) ] ∗ k + ( i 1))/2)]*k+(i 1))/2)]∗k+(i& 1 ) 1) 1) 。
#include<cstdio>
long long f[1005];
int k,n;
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
scanf("%d%d",&k,&n);
for(int i=1;i<=n;i++) f[i]=f[((i-(i&1))/2)]*k+(i&1);
printf("%lld",f[n]);
fclose(stdin);
fclose(stdout);
return 0;
}