Triple Modular Multiplicaiton

Question

je calcule la somme suivante:

(a [x] + m a [x-1] + 2m A [X-2] + 3m * a [x-3] + ....)% MOD (MOD = 1e9 + 7)

Pour cela, j'utilise cette boucle.

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; 

Cependant, cela me donne toujours des erreurs de débordement. L'erreur de base, je suppose est dans (b c)% MOD.

Merci.

Answer 1

Vous devez intégrer les identités arithmétiques modulaires suivantes dans votre programme pour éviter tout débordement:

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

et

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