3

我正在解决一个名为 shill 和 wave sequence 的 Fenwick 树的问题，它没有通过所有测试用例，直到我添加了一行查看解决方案并且现在想要找到它的目的，这是我的代码

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
long long query(long long index,int p,long long **bit)
{
    long long count=0;
    for(;index>0;index-=(index&(-index)))
    {
        count=(count+bit[index][p])%mod;
    }
    return count;
}
void update(long long **bit,long long index,int p,long long val)
{
    for(;index<=100000;index+=(index&(-index)))
    {
        bit[index][p]=(bit[index][p]+val)%mod;
    }
}

int main()
{
    int n;
    cin>>n;
    long long ans=0;
    long long **bit=new long long*[100000+1];
    for(int i=1;i<=100000;i++)
    {
        bit[i]=new long long[3];
        for(int j=0;j<3;j++)
        {
            bit[i][j]=0;
        }
    }
    for(int i=0;i<n;i++)
    {
        long long x;
        cin>>x;
        long long a=(query(x-1,0,bit)+query(x-1,2,bit))%mod;
        long long b=(query(100000,1,bit)+query(100000,2,bit))%mod-query(x,1,bit)-query(x,2,bit);
        b=(b+mod)%mod;
//WHAT IS THE PURPOSE OF ABOVE LINE?
        ans+=(a+b)%mod;
        update(bit,x,0,b);
        update(bit,x,1,a);
        update(bit,x,2,1);
    }
    cout<<ans%mod;
    return 0;
}

b=(b+mod)%mod 但是为什么呢？

4

2 回答 2

2

对于某些情况b，可能是负面的，并且在%直接执行时可能会导致不正确的结果。这就是为什么在进行%操作之前先加mod然后再做%这将使数字为正然后做模是安全的。

于 2021-09-01T07:55:51.243 回答
-1

这条线的“目的”（或者更确切地说，它有任何影响的原因）可能是

b=(b+mod)%mod;

改变 b 的值。

所以剩下的问题是，在应用 %mod 之前添加“mod”是否重要？

从数学上讲

(x+y) mod y = x mod y

但是，在许多编程语言中，int 有一个最大值，如果加起来太大，就会出现整数溢出。在这种情况下，很容易发生

(x+y) mod y != x mod y

你可能就是这种情况。

于 2021-09-01T07:27:14.287 回答