Znzryb's Blog
0%

ABC- 378 - E - Mod Sigma Problem

Posted on Edited on

AC代码

image

最主要的思想就是对前缀和进行一个预处理（即mod M）

∑1≤l≤r≤N((∑l≤i≤rAi)modM)=∑1≤l≤r≤N(Sr−Sl−1)modM, \sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right) = \sum_{1 \leq l \leq r \leq N} (S_r - S_{l-1}) \mathbin{\mathrm{mod}} M,

再说的透一点，就是想怎么把这个对拍程序时间复杂度最高的这部分给化简

1
2
3
4
5
for(int i=1;i<=n;i++) {
        for(int j=i;j>=1;j--) {
            ans=ans+(sumA[i]-sumA[j-1])%m;
        }
    }

这题如果你比较老实，你可能需要使用平衡树，但是你永远可以相信vector大法（虽然好像有点极限）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>

using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,m,A[N],dp[N],ans;
ll sumA[N];         // 经过mod M预处理的前缀和数组A
ll ss[N];           // sumA[]的前缀和（即前缀和的前缀和）
vector<ll> front;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>A[i];
        sumA[i]=(sumA[i-1]+A[i])%m;
    }
    for(int i=1;i<=n;i++) {
        ss[i]=ss[i-1]+sumA[i];
    }
    for(int i=1;i<=n;i++) {
        ll dis=0;
        dis=upper_bound(front.begin(),front.end(),sumA[i])-front.begin()+1;
        // m*(i-1-dis+1) i-1为multiset的长度，-dis后要+1，故抵消
        ans=ans+(sumA[i]*i-(ss[i-1]-ss[0])+m*(i-dis));
        front.insert(lower_bound(front.begin(),front.end(),sumA[i]),sumA[i]);
    }
    cout<<ans<<endl;
}

心路历程（WA，TLE，MLE……）

对拍程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,m,A[N],dp[N],sumA[N],ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>A[i];
        sumA[i]=sumA[i-1]+A[i];
    }
    for(int i=1;i<=n;i++) {
        for(int j=i;j<=n;j++) {
            ans=ans+(sumA[j]-sumA[i-1])%m;
        }
    }
    cout<<ans<<endl;
}

distance 常数太大了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>

using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,m,A[N],dp[N],ans;
ll sumA[N];         // 经过mod M预处理的前缀和数组A
ll ss[N];           // sumA[]的前缀和（即前缀和的前缀和）
multiset<ll> front;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>A[i];
        sumA[i]=(sumA[i-1]+A[i])%m;
    }
    for(int i=1;i<=n;i++) {
        ss[i]=ss[i-1]+sumA[i];
    }
    for(int i=1;i<=n;i++) {
        ll dis=0;
        dis=distance(front.begin(),front.upper_bound(sumA[i]))+1;
        // m*(i-1-dis+1) i-1为multiset的长度，-dis后要+1，故抵消
        ans=ans+(sumA[i]*i-(ss[i-1]-ss[0])+m*(i-dis));
        front.insert(sumA[i]);
    }
    cout<<ans<<endl;
}