一个noip题,按理说应该很简单(斐波那契数列变形),不过正常递推(不要位运算的)总是错第九个数据

描述 Description
给定一个正整数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。


输入格式 Input Format
输入只有1行，为2个正整数，用一个空格隔开：
k N
（k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）。


输出格式 Output Format
输出为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*10^9）。（整数前不要有空格和其他符号）。

样例输入 Sample Input

3 100

样例输出 Sample Output

981

可以在http://www.vijos.cn/Problem_Show.asp?id=1319测试

我用的int类型存数按理说就可以了(GCC下int范围与long相同,而数据范围在int之内),不过那样递推只能过5-6个数据,换成double也只能过9个数据,通过高精度运算只能过6个数据,据说位运算可以AC,不过为什么用正常递推无法通过呢?

天外有天，人外有人，一定会有人帮助我的

编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
-------------------------
Accepted 有效得分：100 有效耗时：0ms

通过了．．．．
感谢leeco

不过还有一个问题，这是什么算法？

我的递推过程：
s[i+j]=s[i]+s[j];
s[j]为当前的k^x,不变，i递增

设当前次方为x
x=0;
设存储数组
s[2002];
设临时变量
i,j;
其中i为当前递推数据号
i=0;
while(i<=n)
{
s[i]=pow(k,x);
x++;
for(j=1;j<i;j++)
s[i+j]=s[i]+s[j];
i=i+j;
}

谢谢，你的解法我明白了，不过我在楼上写的递推也应该没有问题啊，为什么那样就过不了一些数据？

3^0 3^1 3^0+3^1 3^2 3^0+3^2 3^1+3^2 3^0+3^1+3^2
s[1] s[2] =s[1]+s[2] s[4] =s[1]+s[4] =s[2]+s[4] =s[3]+s[4]

哦,看看上面这个应该就明白了

编号 0 1 2 3 4 5 6 7
数列 0 3^0 3^1 3^0+3^1 3^2 3^0+3^2 3^1+3^2 3^0+3^1+3^2
对应 0 0+1 0+2 1+2 0+4 1+4 2+4 3+4