一个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,不过为什么用正常递推无法通过呢?

我想这个问题还是你自己研究解决吧！！！ 恐怕论坛里没人能帮你。
俺也爱莫能助，惭愧！

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

这个Judge现在有问题，全部的CODE都判成编译错，我觉得这个代码应该没问题

#include <stdio.h>

int main()
{
    int k,n;
    while(scanf(\"%d %d\",&k,&n)!=EOF){
        int res=0,t=1;
        while(n){
            if(n%2){
                res+=t;
            }
            t*=k;
            n/=2;
        }
        printf(\"%d\n\",res);
    }    
}    

正常了，过了

[此贴子已经被作者于2007-8-12 22:28:23编辑过]

编译通过...
├ 测试数据 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递增

就是利用
m-1
∑k^i < k^m
i=0
然后把
3^0，3^1，3^0+3^1，3^2，3^0+3^2，3^1+3^2
和
1, 2, 3, 4, 5, 6
通过进制转换建立双射关系。

如果将3^0，3^1，3^0+3^1，3^2，3^0+3^2，3^1+3^2用3进制表示
恰好和1, 2, 3, 4, 5, 6用2进制表示
时候的形式上是一致的。

对于一般的情况，就是将n视作2进制表示的串所对应的k进制表示的数就是要输出的。