Участник:PinkHedgehog/Student-attendance-record

Материал из DISCOPAL
< Участник:PinkHedgehog
Версия от 19:07, 26 мая 2020; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
int checkRecord(int n)
{
    unsigned long long trib[100001];
    unsigned long long acc = 0;
    trib[0] = 1; trib[1] = 2; trib[2] = 4; trib[3] = 7;
    for (int i = 4; i <= n; i++)
    {
        trib[i] = 0;
        trib[i] += trib[i-1] % 1000000007;
        trib[i] += trib[i-2] % 1000000007;
        trib[i] += trib[i-3] % 1000000007;
        trib[i] %= 1000000007;
    }
    for (int i = 0; i < n; i++)
    {
        acc += (trib[i] * trib[n - 1 - i]) % 1000000007;
    }
 
    acc = (acc + trib[n]) % 1000000007;
    return (int) acc;
}