Ошибка во время выполнения проблемы Codechef: модифицированная серия Фибоначчи. В чем ошибка?

Question

Я пытаюсь решить проблему с codechef, вот ссылка:

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

Дано постановка задачи:

Шеф недавно изучал числа Фибоначчи и написал код для вывода k-го члена ряда Фибоначчи (1, 1, 2, 3, 5, 8, 13 ...).Он задавался вопросом, может ли он написать программу для генерации k-го термина для подобных рядов.Более конкретно:

• T (n, k) равно 1, если n <= k, и </li>
• T (n, k) = T (n-1, k) + T (n-2, k) + T (n-3, k)… + T (nk, k), если n> k.

При заданных n и k, выходной T (n, k)%(1000000007) поскольку ответ может быть очень большим

Входные данные: два целых числа, N и K

Выходные данные: одно целое число, n-й член ряда мод 1000000007

Ограничения: 1 ≤ N, K ≤ 2 * 10 ⁵

пример:

Вход: 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

Проблема в том, что вы вычисляете значение по модулю 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

Answer 2

Чтобы избежать переполнения, вы можете изменить приведенную ниже инструкцию

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