取模的问题
我的例子:
cnt[i]+=cnt[i+1];
if(cnt[i]<0) cout<<"Warning";
cnt[i]%=MOD;
if(o[i]==1){
a[x[i]]=(a[x[i]]+y[i]*cnt[i]%MOD)%MOD;
}
else{
cnt[y[i]]+=cnt[i],cnt[x[i]-1]-=cnt[i];
cnt[y[i]]%=MOD,cnt[x[i]-1]%=MOD;//这里的问题,因为一旦cnt过大,cnt[y[i]]可能被膜掉a倍MOD,故cnt[y[i]]就有可能小于cnt[x[i]-1],导致前缀和推到cnt[x[i]-1]时为负数
}
那怎么规避呢,一旦cnt[i]<0时,我们只需要不断地加上MOD使cnt[i]>0。
cnt[i]+=cnt[i+1];
while(cnt[i]<0) cnt[i]+=MOD;
if(cnt[i]<0) cout<<"Warning";
cnt[i]%=MOD;
if(o[i]==1){
a[x[i]]=(a[x[i]]+y[i]*cnt[i]%MOD)%MOD;
}
else{
cnt[y[i]]+=cnt[i],cnt[x[i]-1]-=cnt[i];
cnt[y[i]]%=MOD,cnt[x[i]-1]%=MOD;
}
那又有一个问题了,如果cnt[y[i]]大得不止一倍MOD呢,我用两方面来解释。
第一种:因cnt[i]<MOD,所以cnt[y[i]]+=cnt[i]后应<2*MOD,故不成立。
第二种:就算cnt[y[i]]比cnt[x[i]-1]大了很多倍MOD,那这些多余的MOD在计算a[x[i]时也会被模掉,所以也不影响。
口胡的说法也不知道对不对