三重模块化乘法

Question

我正在计算以下总和：

（a[x]+m a[x-1]+2m a[x-2]+3m*a[x-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;

但是，这仍然给我带来了溢出错误。基本错误，我猜是在（abc）%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