c - Codechef 问题 : modified Fibonacci series. 的运行时错误是什么错误？

Question

我正在尝试解决 codechef 上的一个问题，这里是链接:

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

问题是您计算值模 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 100000871925546real    0m34.667suser    0m34.288ssys     0m0.113s$ time ./fibo-faster 200000 100000871925546real    0m15.073suser    0m14.846ssys     0m0.064s

Given the restrictions on input values:

• the values of T(n, k) are in the range [0..1000000006] which fits in an int32_t.
• the sum of k terms is in the range [0..200000*1000000006] which fits in an int64_t.
• hence we can compute the next term in 64 bits and use a single modulo on the result.

This gives an even faster version (more than 3 times faster):

#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 100000871925546real    0m3.854suser    0m3.800ssys     0m0.018s