Тройной Модульный Multiplicaiton

Question

Я вычисления следующую сумму:

(а [х] + т а [х-1] + 2m а [х-2] + 3m * а [х-3] + ....)% MOD (MOD = 1e9 + 7)

Для этого я использую этот цикл.

long long mulmod(long long a,long long b,long long c) 
{ 
    if (a == 0 || b == 0) 
     return 0; 
    if (a == 1) 
     return b; 
    if (b == 1) 
     return a; 
    long long a2 = mulmod(a, b/2, c); 
    if ((b & 1) == 0) 
    { 
     return (a2 + a2) % c; 
    } 
    else 
    { 
     return ((a % c) + (a2 + a2)) % c; 
    } 
} 

res=a[x]%MOD; 
for(i=x-1;i>=1;i--) 
    res=(res%MOD+mulmod(mulmod(x-i,m,MOD),a[i],MOD))%MOD; 

Однако, это все еще дает мне ошибки переполнения. Основная ошибка, я думаю, находится в (a b c)% MOD.

спасибо.

Answer 1

Вам необходимо включить следующие модульные арифметические тождества в программу, чтобы избежать переполнения:

(A + B + ...) mod C = (A mod C + B mod C + ... mod C) mod C

и

(A * B * ...) mod C = (A mod C * B mod C * ... mod C) mod C