analyse

improve process：优化分析结合下面的代码食用风味更佳

• 暴力
  • $O(N^3)$
• 1：空间换时间——存前缀和
  • 优化结果：$O(N^2)$
• 2：空间换时间——存取余后的数
  • 1.在$O(N^2)$的代码中，右端点是i时，res++条件是(s[i]-s[i-j])%k==0，即在区间长度j∈[1,i]中，有几个j满足s[i]%k == s[i-j]%k;
  • 2.记右端点为i，满足1中条件的个数为c[i]，mod_num[x]为s[0]~s[i]中，余数的个数，则等价变形c[i] = mod_num[s[i]%k], mod_num[s[i]%k]++, res += mod_num[s[i]%k]++;
  • 3.但是！上面的变形并不是等价的，由于2中条件(s[i]-s[i-j])%k==0，包括了j==i的情况，也就是区间长度为i，即s[i]%k==0(s[0]==0)的情况；而等价变形后的条件res += mod_num[s[i]%k]++，对区间长度为i的情况，即s[i]%k==0时未处理，应该加上额外条件if(s[i]%k==0) res++, 或者初始化的时候mod_num[0] = 1，或者最后的res += mod_num[0]；
  • 优化结果：$O(N)$
• 3：代码优化
  • 输入的同时计算前缀和；
  • 前缀和直接取余数；
  • 一次循环完成结果计算。

code

// 优化 1 n^3 -> n^2
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 100005;
long long s[N];
int c[N];
int mod_num[N]; // 记录s[0]~s[i]中，余数的个数，随着i增大动态更新，实际k空间就够了，因为余数只有0~k-1种情况 
int n,k;

int main(int argc, char** argv) {
    cin >> n >> k;
    long long res = 0;
    for(int i = 1; i <= n; i ++) {
        scanf("%d", s+i);
        s[i] = s[i-1] + s[i];
    }
    for(int i = 1; i <= n; i++)      // i:右端点
        for(int j = 1; j <= i; j++)  // j:区间长度
            if((s[i]-s[i-j])%k == 0)
                res++;
    cout << res;
    return 0;
}

// 优化 2
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 100005;
long long s[N];
int c[N];
int mod_num[N]; // 记录s[0]~s[i]中，余数的个数，随着i增大动态更新，实际k空间就够了，因为余数只有0~k-1种情况 
int n,k;

int main(int argc, char** argv) {
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) {
        scanf("%d", s+i);
        s[i] = s[i-1] + s[i];
    }
    long long res = 0;
    for(int i = 1; i <= n; i++) {
        int mod = s[i]%k;     // s[i]除k的余数 
        c[i] = mod_num[mod];  // c[i]记录与s[i]余数相同的个数,但是区间长度为i的情况，未处理 
        if(mod == 0) res++;   // 处理区间长度为i的情况
        mod_num[mod]++;       // 记录s[1]~s[i]中，余数的个数
        res += c[i];
    }
    cout << res;
    return 0;
}
// 优化 3
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 100005;
int s[N];
int mod_num[N]; // 记录s[0]~s[i]中，余数的个数，随着i增大动态更新，实际k空间就够了，因为余数只有0~k-1种情况
int n,k;

int main(int argc, char** argv) {
    cin >> n >> k;
    long long res = 0;
    for(int i = 1; i <= n; i ++) {
        scanf("%d", s+i);
        s[i] = (s[i-1] + s[i])%k; // 计算前缀和同时取余
        if(!s[i]) res++;          // 处理区间长度为i的情况
        res += mod_num[s[i]]++;   // 更新结果
    }
    cout << res;
    return 0;
}