Codechef 问题的运行时错误：修改后的斐波那契数列。怎么了？

Question

我正在尝试解决 codechef 上的问题，这里是 link:

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

给出的问题陈述是：

Chef recently had been studying about Fibonacci numbers and wrote a code to print out the k-th term of the Fibonacci series (1, 1, 2, 3, 5, 8, 13….). He was wondering whether he could write a program to generate the k-th term for similar series. More specifically:

T(n, k) is 1 if n <= k and

T(n, k) = T(n-1, k) + T(n-2, k) + T(n-3, k) … + T(n-k, k) if n > k.

Given n and k, output T(n, k) % (1000000007) as the answer could be very large

Input : Two integers, N and K

Output : One integer, the nth term of the series mod 1000000007

Constraints : 1 ≤ N, K ≤ 2*10⁵

示例：

Input: 7 5

Output: 9

The series is as follows {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

Codechef 问题的运行时错误：修改后的斐波那契数列。怎么了？

Runtime error on a Codechef problem: modified Fibonacci series. What's the mistake?

c

fibonacci