Codechef问题的运行时错误：修改过的Fibonacci系列。怎么了？

Question

我正在尝试解决codechef上的问题，这是链接：

https://www.codechef.com/problems/KFIB

给出的问题陈述是：

Chef最近一直在研究Fibonacci数字，并编写了一个代码来打印斐波纳契系列的第k个术语（1,1,2,3,5,8,13 ......）。他想知道他是否可以编写一个程序来生成类似系列的第k个术语。进一步来说：

• 如果n <= k，则T（n，k）为1
• 如果n> k，则T（n，k）= T（n-1，k）+ T（n-2，k）+ T（n-3，k）... + T（n-k，k）。

给定n和k，输出T（n，k）％（1000000007）作为答案可能非常大

输入：两个整数，N和K.

输出：一个整数，系列的第n个项mod 1000000007

约束条件：1≤N，K≤2* 105

例：

输入：7 5

输出：9

该系列如下{1,1,1,1,1,5,9}

 void fibo(int n, unsigned long k) {
     unsigned long *a, c;

     a = (unsigned long *)malloc(sizeof(unsigned long) * k);

     for (unsigned long i = 0; i < k; i++) {  //T(n,k)=1 when n<=k
         *(a + i)=1;
     }

     for (unsigned long m = 0; m < n - 1; m++) {
         c = *(a);
         for (unsigned long j = 0; j < k - 1; j++) {
             *(a + j) = *(a + j + 1);
             c = c + *(a + j);
         }
         *(a + k - 1) = c;
     }
     printf("%d ", *(a) % 1000000007);
}

这适用于较小的值，但不是非常大的值。我得到了示例的结果，但是当我输入值200000 500时，我得到的答案不正确

Answer 1

为避免溢出，您可以更改以下语句

c=c+*(a+j);

至

c=(c+*(a+j))%1000000007;

这意味着只有剩余部分将保留在您的堆中。这不会影响最终结果。

这是更新的代码，由clang编译。（根据@ bruno的评论更新）

#include <stdlib.h>
#include <stdio.h>
#define DIVIDER 1000000007ul
#define U4 unsigned long

U4 fibo(U4 n,U4 k)
{
    U4 *a,c ;
    if(n<=k) return 1;

    a= (U4*) malloc (sizeof(U4)*k);

    for (U4 i=0;i<k;i++)   //T(n,k)=1 when n<=k
    {
        *(a+i)=1;
    }

    for (U4 m=k;m<n; m++)
    {
        c=*(a);
        for (U4 j=0;j<k-1;j++)
        {
          *(a+j)= *(a+j+1);
          c=(c+*(a+j))%DIVIDER;
        }
        *(a+k-1)=c;
    }
    free(a);
    return c;
}

int main(int argc, char *argv[])
{
    U4 n, k;
    char *endptr;
    if(argc <= 2){
        printf("usage: t.exe n k");
        return 0;
    }
    n = strtoul(argv[1], &endptr, 10);
    k = strtoul(argv[2], &endptr, 10);
    printf("%lu", fibo(n,k));
}

编译命令：

$ clang test.c -o test.exe
$ test.exe 200000 500
80391289

Answer 2

问题是你计算模ULONG_MAX的值并在结尾减少结果模1000000007。这没有给出正确的结果。您必须在每一步减少模数1000000007以避免潜在的算术溢出（这不会导致类型unsigned long的未定义行为，但会产生与预期的不同的结果）。

以下是代码的修改版本，具有更快的替代方案（在我的笔记本电脑上快两倍）：

#include <stdio.h>
#include <stdlib.h>

#define DIVIDER 1000000007ul

unsigned long fibo(unsigned long n, unsigned long k) {
    unsigned long c = 1;

    if (n > k) {
        unsigned long *a = (unsigned long *)malloc(sizeof(*a) * k);

        for (unsigned long i = 0; i < k; i++) {  //T(n,k)=1 when n<=k
            a[i] = 1;
        }
        for (unsigned long m = k; m < n; m++) {
            c = a[0];
            for (unsigned long j = 0; j < k - 1; j++) {
                a[j] = a[j + 1];
#if 0
                // slower version using modulo
                c = (c + a[j]) % DIVIDER;
#else
                // faster version with a test
                if ((c += a[j]) >= DIVIDER)
                    c -= DIVIDER;
#endif
            }
            a[k - 1] = c;
        }
        free(a);
    }
    return c;
}

int main(int argc, char *argv[]) {
    if (argc <= 2) {
        printf("usage: fibo n k");
        return 1;
    } else {
        unsigned long n = strtoul(argv[1], NULL, 10);
        unsigned long k = strtoul(argv[2], NULL, 10);
        printf("%lu\n", fibo(n, k));
    }
    return 0;
}

输出：

$ time ./fibo 200000 100000
871925546

real    0m34.667s
user    0m34.288s
sys     0m0.113s

$ time ./fibo-faster 200000 100000
871925546

real    0m15.073s
user    0m14.846s
sys     0m0.064s

鉴于输入值的限制：

• T(n, k)的值在[0..1000000006]范围内，适合int32_t。
• k项的总和在[0..200000 * 1000000006]范围内，适合int64_t。
• 因此，我们可以用64位计算下一个项，并在结果上使用单个模。

这样可以提供更快的版本（速度提高3倍以上）：

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define DIVIDER 1000000007

uint32_t fibo(uint32_t n, uint32_t k) {
    uint32_t c = 1;

    if (n > k) {
        uint32_t *a = (uint32_t *)malloc(sizeof(*a) * k);
        uint64_t temp;

        for (uint32_t i = 0; i < k; i++) {  //T(n,k)=1 when n<=k
            a[i] = 1;
        }
        for (uint32_t m = k; m < n; m++) {
            temp = a[0];
            for (uint32_t j = 0; j < k - 1; j++) {
                temp += a[j] = a[j + 1];
            }
            a[k - 1] = c = temp % DIVIDER;
        }
        free(a);
    }
    return c;
}

int main(int argc, char *argv[]) {
    if (argc <= 2) {
        printf("usage: fibo n k");
        return 1;
    } else {
        uint32_t n = strtoul(argv[1], NULL, 10);
        uint32_t k = strtoul(argv[2], NULL, 10);
        printf("%lu\n", (unsigned long)fibo(n, k));
    }
    return 0;
}

输出：

$ time ./fibo-faster 200000 100000
871925546

real    0m3.854s
user    0m3.800s
sys     0m0.018s