NOIP2020 题解

    NOIP2020 题解

    T1. 排水系统

    LOJ 3386

    Solution

    将每个 “ 排水节点 “ 看成是一个 “ 点 “,将每个 “ 单向排水管道 “ 看成是一条 “ 单向边 “。

    不难发现,得到的图是一张 DAG。

    直接模拟题意即可。依次松弛每个节点的蓄水量,直至到达最终排水口。需要注意的是,在松弛任意一个节点 vv 的蓄水量时,需要保证:对于图中的每一条有向边 (u,v)(u, v),uu 的蓄水量都被松弛过了。

    发现可以通过拓扑序来转移。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    #include <vector>
    
    #define u128 __int128 
    
    using namespace std;
    
    inline void print(u128 x) {
        if (x > 9) print(x / 10);
        putchar('0' + x % 10);
    }
    
    u128 gcd(u128 a, u128 b) {
        if (!b) return a;
        return gcd(b, a % b);
    }
    
    const int N = 400100;
    
    struct Node {
        u128 x, y;
    } a[N];
    
    Node operator + (Node a, Node b) {
        Node c;
        c.y = a.y * b.y;
        c.x = a.x * b.y + b.x * a.y;
        u128 S = gcd(c.x, c.y);
    
        if (!S) {
            c.x = 0;
            c.y = 1;
        } else {
            c.x /= S;
            c.y /= S;
        }
    
        return c;
    }
    
    Node operator / (Node a, int num) {
        Node b;
        b.x = a.x;
        b.y = 1ll * a.y * num;
        u128 S = gcd(b.x, b.y);
    
        if (!S) {
            b.x = 0;
            b.y = 1;
        } else {
            b.x /= S;
            b.y /= S;
        }
    
        return b;
    }
    
    int n, m;
    
    vector<int> to[N];
    
    int deg[N];
    
    void topsort() {
        queue<int> q;
        for (int i = 1; i <= n; i ++)
            if (deg[i] == 0) q.push(i);
    
        while (q.size()) {
            int u = q.front(); q.pop();
            if (to[u].size() == 0) continue;
            Node give = a[u] / to[u].size();
            for (int i = 0; i < (int)to[u].size(); i ++) {
                int v = to[u][i];
                a[v] = a[v] + give;
                if (-- deg[v] == 0) q.push(v);
            }
        }
    }
    
    int main() {
        scanf("%d%d", &n, &m);
    
        for (int i = 1, S; i <= n; i ++) {
            scanf("%d", &S);
    
            while (S --) {
                int x;
                scanf("%d", &x);
                to[i].push_back(x);
            }
        }
    
        for (int i = 1; i <= m; i ++)
            a[i].x = 1, a[i].y = 1;
    
        for (int i = m + 1; i <= n; i ++)
            a[i].x = 0, a[i].y = 1;
    
        for (int i = 1; i <= n; i ++)
            for (int j = 0; j < (int)to[i].size(); j ++) {
                int v = to[i][j];
                deg[v] ++;
            }
    
        topsort();
    
        for (int i = 1; i <= n; i ++)
            if (to[i].size() == 0) {
                print(a[i].x);
                printf(" ");
                print(a[i].y);
                puts(""); 
            }
    
        return 0;
    }
    
    // I hope changle_cyx can pray for me.

    T2. 字符串匹配

    LOJ 3387

    Solution

    算法一

    部分分:n≤217n \leq 2^{17}。

    一个较为简单的做法,基本不用怎么思考。

    注意到答案是要求将字符串划分成 S=(AB)iCS = (AB)^iC 的形式。

    记 F(S)F(S) 的表示字符串 SS 中出现奇数次的字符的数量。需要先预处理出:

    • 每一个前缀 S1..iS_{1 .. i} 出现奇数次的字符的数量,即 F(S1..i)F(S_{1..i})。
    • 每一个后缀 Si..nS_{i .. n} 出现奇数次的字符的数量,即 F(Si..n)F(S_{i .. n})。

    考虑枚举 T=(AB)T = (AB),那相当于是枚举一个前缀。此基础上,再从小到大枚举一个 ii,使用 hash 判断子串是否完全相等。

    此时整个字符串的划分结构就已经是确定的了。F(C)F(C) 已经预处理好了,那这种情况对答案的贡献,相当于要在 TT 里数出有多少个真前缀 AA 满足 F(A)≤F(C)F(A) \leq F(C),那直接用树状数组动态维护一下即可。

    时间复杂度 O(nlog⁡n+nlog⁡∣∑∣)\mathcal{O}(n \log n + n \log |\sum|),其中 ∑\sum 表示字符集。期望得分 84∼10084 \sim 100。

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 2000000;
    const unsigned long long P = 13331;
    
    int n;
    char S[N];
    
    // suf & pre
    
    bool exist[30];
    int num;
    
    int suf[N];
    int pre[N];
    int c[N][30];
    
    // hash
    
    unsigned long long power[N];
    unsigned long long hash[N];
    
    unsigned long long H(int l, int r) {
        return hash[r] - hash[l - 1] * power[r - l + 1];
    }
    
    void work() {
        scanf("%s", S + 1);
        n = strlen(S + 1);
    
    // suf
    
        for (int i = 0; i < 26; i ++)
            exist[i] = 0;
    
        num = 0;
        for (int i = n; i >= 1; i --) {
            int ch = S[i] - 'a';
    
            exist[ch] ^= 1;
    
            if (exist[ch]) num ++;
            else num --;
    
            suf[i] = num;
        }
    
    // pre
    
        for (int i = 0; i < 26; i ++)
            exist[i] = 0;
    
        num = 0;
        for (int i = 1; i <= n; i ++) {
            int ch = S[i] - 'a';
    
            exist[ch] ^= 1;
    
            if (exist[ch]) num ++;
            else num --;
    
            pre[i] = num;
        }
    
        for (int i = 1; i <= n; i ++) {
            for (int j = 0; j <= 26; j ++)
                c[i][j] = c[i - 1][j];
            for (int j = pre[i]; j <= 26; j ++)
                c[i][j] ++;
        }
    
    // hash
    
        for (int i = 1; i <= n; i ++)
            hash[i] = hash[i - 1] * P + (S[i] - 'a');
    
    // work
    
        long long ans = 0;
    
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= n / i; j ++) {
                int l = (j - 1) * i + 1, r = j * i;
    
                if (H(1, i) != H(l, r)) break;
                if (r + 1 > n) break;
    
                ans += c[i - 1][suf[r + 1]];
            }
        }
    
        printf("%lld\n", ans);
    }
    
    int main() {
        power[0] = 1;
        for (int i = 1; i <= 1500000; i ++) power[i] = power[i - 1] * P;
    
        int T; scanf("%d", &T);
    
        while (T --)    work();
    
        return 0;
    }
    
    // I hope changle_cyx can pray for me.

    算法二

    「算法一」没有怎么用到题目中的一些性质,还是考虑枚举 T=(AB)=S1..xT = (AB) = S_{1 .. x}。

    对于当前枚举到的一个 xx。考虑计算出一个最大的 ii,使得 SS 可以被划分成 (AB)iC(AB)^iC 的形式,记这个量为 kk。

    引理:若一个长度为 nn 的字符串 SS 的前 n−mn - m 位和后 n−mn - m 是相等的且 m∣nm \mid n,则 SS 有一个长度为 mm 的整除循环节。

    根据该引理,考虑求出字符串 SS 的 ZZ 函数,其中 ZiZ_i 表示:后缀 Si..nS_{i .. n} 与 SS 的最长公共前缀(LCP)的长度。

    注意到若 SS 可以被划分成 (AB)iC(AB)^iC 的形式,则必满足 x(i−1)≤Zx+1x(i - 1) \leq Z_{x + 1} 且 xi<nxi < n。解得

    i≤Zx+1x+1i<nxi \leq \frac{Z_{x + 1}}{x}+ 1 \\i < \frac{n}{x}

    则

    k=min⁡{⌊Zx+1x⌋+1,⌈nx⌉−1}k = \min \left\{ \left\lfloor \frac{Z_{x + 1}}{x} \right\rfloor + 1, \left\lceil \frac{n}{x} \right\rceil - 1 \right\}

    接下来考虑 F((AB)i)F\left((AB)^i\right) 的重复性,注意到:

    • 当 ii 为奇数时 F((AB)i)F\left( (AB)^i \right) 均等。当 ii 为奇数时,对于每个 (AB)i(AB)^i 划分出来的 CC,都有 F(C)=F(Sx+1..n)F(C) = F(S_{x + 1 .. n})。

    • 当 ii 为偶数时 F((AB)i)=0F\left( (AB)^i \right) = 0。当 ii 为偶数时,对于每个 (AB)i(AB)^i 划分出来的 CC,都有 F(C)=F(S)F(C) = F(S)。

    那么我们可以知道,划分出来的 F(C)F(C) 的也就只有两种情况,要么是 F(Sx+1..n)F(S_{x + 1 .. n}) 要么是 F(S)F(S)。其中 ⌈k2⌉\left\lceil \frac{k}{2} \right\rceil 个 ii 为奇数,⌊k2⌋\left\lfloor \frac{k}{2} \right\rfloor 个 ii 为偶数。

    F(Sx+1..n)F(S_{x + 1 .. n}) 在枚举 xx 的时候顺便处理一下即可,F(S)F(S) 直接处理即可。

    那么现在就是要分别数出 TT 中有多少个真前缀 AA 满足 F(A)≤F(Sx+1..n)F(A) \leq F(S_{x + 1 .. n}),F(A)≤F(S)F(A) \leq F(S)。

    注意到 F(S)F(S) 是不变的,那么在枚举的时候直接判断一下即可。至于 F(Sx+1..n)F(S_{x + 1 .. n}),当 xx 加 11 的时候也只会导致 F(Sx+1..n)F(S_{x + 1 .. n}) 变化 11,稍微判断一下补补贡献即可。

    时间复杂度 O(n)\mathcal{O}(n)。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = (1 << 20) + 1000;
    
    int T;
    
    int n;
    char s[N];
    
    int Z[N];
    
    void Z_algorithm() {
        for (int i = 1; i <= n; i ++) Z[i] = 0;
        for (int i = 2, l = 0, r = 0; i <= n; i ++) {
            if (i <= r) Z[i] = min(Z[i - l + 1], r - i + 1);
            while (i + Z[i] <= n && s[1 + Z[i]] == s[i + Z[i]])
                Z[i] ++;
            if (i + Z[i] - 1 > r)
                l = i, r = i + Z[i] - 1;
        }
    }
    
    int pre, suf, Fs;
    int cnt[26];
    bool flag1[26], flag2[26];
    
    int cur1, cur2;
    long long ans;
    
    void work() {
        scanf("%s", s + 1);
        n = strlen(s + 1);
    
        Z_algorithm();
    
        memset(flag1, 0, sizeof(flag1));
        memset(flag2, 0, sizeof(flag2));
        for (int i = 1; i <= n; i ++) {
            int ch = s[i] - 'a';
            flag2[ch] ^= 1;
        }
    
        Fs = 0;
        for (int i = 0; i < 26; i ++)
            if (flag2[i]) Fs ++;
    
        pre = 0, suf = Fs;
        ans = 0, cur1 = cur2 = 0;
        memset(cnt, 0, sizeof(cnt));
    
        for (int i = 1; i < n; i ++) {
            int ch = s[i] - 'a';
    
            flag1[ch] ^= 1, flag2[ch] ^= 1;
    
            if (flag1[ch]) pre ++;
            else pre --;
    
            if (flag2[ch]) suf ++, cur1 += cnt[suf];
            else cur1 -= cnt[suf], suf --;
    
            int k = min((Z[i + 1] / i) + 1, (n - 1) / i);
            int odd = (k + 1) / 2, even = k / 2;
    
            ans += 1ll * odd * cur1;
            ans += 1ll * even * cur2;
    
            cnt[pre] ++;
            if (pre <= suf) cur1 ++;
            if (pre <= Fs) cur2 ++;
        }
    
        printf("%lld\n", ans);
    }
    
    int main() {
        scanf("%d", &T);
    
        while (T --)    work();
    
        return 0;
    }
    
    // I hope changle_cyx can pray for me.

    T3. 移球游戏

    LOJ 3388

    Solution

    感谢 xyz32768 的指导,以及他的题解。

    算法一

    部分分:n=2n = 2。

    现在有三个柱子 x,y,zx, y, z。 其中 xx 号柱与 yy 号柱是满的,zz 号柱是空的。这 2m2m 个球中有 mm 个关键球,现在要将所有关键球移动到同一根柱子上。

    设 xx 柱上有 cc 个关键球,操作如下:

    • (1):将 yy 号柱上的 cc 个球移动到 zz 号柱上。

    • (2):依次考虑 xx 号柱里的每一个球。

      若该球为关键球,则将其移动到 yy 号柱。
      若该球不为关键球,则将其移动到 zz 号柱。

    • (3):将 zz 号柱上方的 m−cm - c 个球移回 xx 号柱。

    • (4):将 yy 号柱上方的 cc 个球移动到 xx 号柱。

    • (5):将 zz 号柱里的 cc 个球移动到 yy 号柱。

    • (6):将 xx 号柱上方的 cc 个球移动到 zz 号柱。

    • (7):依次考虑 yy 号柱里的每一个球。

      若该球为关键球,则将其移动到 zz 号柱。
      若该球不为关键球,则将其移动到 xx 号柱。

    此时 n=2n = 2 就做完了,复杂度是 O(m)\mathcal{O(m)} 的。

    「算法一」是本题中最基本的操作。

    算法二

    部分分:n≤50n \leq 50,m≤300m \leq 300。

    可以一个颜色一个颜色来考虑。假设考虑到第 nn 个颜色,现在要将所有颜色为 nn 的球移动到同一根柱子上:

    1. 枚举 i=1→(n−1)i = 1 \to (n - 1),将 ii 号柱里所有颜色为 nn 的球都移动到 ii 号柱子的最顶端。记 ii 号柱共有 cic_i 个颜色为 nn 的球,操作如下:

      • (1):将 nn 号柱移出 cic_i 个空位。

      • (2):依次考虑 ii 号柱里的每一个球。

        若该球的颜色为 nn,则将其移动到 nn 号柱。
        若该球的颜色不为 nn,则将其移动到 n+1n + 1 号柱。

      • (3):将 n+1n + 1 号柱上方的 m−cim - c_i 个球移回 ii 号柱。

      • (4):将 nn 号柱上方的 cic_i 个球移回 ii 号柱。

      • (5):将 n+1n + 1 号柱上方的 cic_i 个球移回 nn 号柱。

    2. 枚举 i=1→(n−1)i = 1 \to (n - 1),将 ii 号柱子最顶端所有颜色为 nn 的球都移动到 n+1n + 1 号柱上。

    3. 依次考虑 nn 号柱子里的每一个球。

      若该球的颜色为 nn,则将其移动到 n+1n + 1 号柱。
      若该球的颜色不为 nn,则将其补到 11 至 n−1n - 1 号柱里的一个空位上。

    这样的话就得到了一个规模为 n−1n - 1 的子问题,直接递归即可。

    复杂度是 O(n2m)\mathcal{O}(n^2m) 的。可以计算得出该算法最坏情况下的严格操作数为 m(n−1)(n+4)m(n - 1)(n + 4)。

    发现刚好可以过掉 7070 分。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f; 
    }
    
    const int N = 60, M = 450;
    
    int n, m;
    
    int top[N], a[N][M];
    int cnt[N][M];
    
    int t;
    pair<int, int> ans[820001];
    
    void move(int x, int y) {
        ans[++ t] = make_pair(x, y);
    
        int u = a[x][top[x]];
    
        cnt[x][u] --;
        cnt[y][u] ++;
    
        a[y][++ top[y]] = a[x][top[x] --];
    }
    
    void solve(int u) {
        if (u == 1)
            return;
    
        for (int i = 1; i < u; i ++) {
            int c = cnt[i][u];
    
            for (int j = c; j; j --)
                move(u, u + 1);
    
            for (int j = m; j; j --)
                if (a[i][j] == u) move(i, u);
                else move(i, u + 1);
    
            for (int j = m - c; j; j --)
                move(u + 1, i);
    
            for (int j = c; j; j --)
                move(u, i);
    
            for (int j = c; j; j --)
                move(u + 1, u);
        }
    
        for (int i = 1; i < u; i ++)
            while (a[i][top[i]] == u)
                move(i, u + 1);
    
        int p = 1;
        for (int j = top[u]; j; j --) {
            if (a[u][j] == u) move(u, u + 1);
            else {
                while (top[p] >= m) p ++;
                move(u, p);
            }
        }
    
        solve(u - 1);
    }
    
    int main() {
        n = read(), m = read();
    
        for (int i = 1; i <= n; i ++) {
            top[i] = m;
            for (int j = 1; j <= m; j ++)
                a[i][j] = read(), cnt[i][a[i][j]] ++;
        }
    
        solve(n);
    
        printf("%d\n", t);
        for (int i = 1; i <= t; i ++)
            printf("%d %d\n", ans[i].first, ans[i].second);
    
        return 0;
    }
    
    // I hope changle_cyx can pray for me.

    算法三

    注意到「算法二」中,一个颜色一个颜色来考虑有点浪费。可不可以多个颜色一起考虑呢?这启发我们分治。

    定义分治函数 solve(l, r),取中点 mid=⌊l+r2⌋\text{mid} = \left\lfloor \frac{l + r}{2} \right\rfloor。

    在每一轮中我们的目的是:将所有 “ 颜色 ≤mid\leq \text{mid} 的球 “ 与 “ 颜色 >mid> \text{mid} 的球 “ 区分开来。
    即:经过一系列操作过后,不存在一根柱子上同时有 “ 颜色 ≤mid\leq \text{mid} 的球 “ 和 “ 颜色 >mid> \text{mid} 的球 “。

    随后调用 solve(l, mid) 与 solve(mid + 1, r)。

    问题的关键在于如何区分。

    在每一轮中,我们将这 r−l+1r - l + 1 根柱子取出来。每次我们可以挑出两根柱子:

    • (1):如果 “ 颜色 ≤mid\leq \text{mid} 的球 “ 超过了 mm 个。
      则选取任意 mm 个 “ 颜色 ≤mid\leq \text{mid} 的球 “ 作为关键球,进行「算法一」中的基本操作。
    • (2):如果 “ 颜色 >mid> \text{mid} 的球 “ 超过了 mm 个。
      则选取任意 mm 个 “ 颜色 >mid> \text{mid} 的球 “ 作为关键球,进行「算法一」中的基本操作。

    这样进行 r−lr - l 次,这 r−l+1r - l + 1 根柱子也就达到了每一轮的目的,递归下去解决即可。

    考虑分治树的结构,共有 O(log⁡n)\mathcal{O(\log n)} 层。对于每层的所有节点,进行上述的基本操作的复杂度是 O(nm)\mathcal{O(nm)} 的。

    时间复杂度为 O(nmlog⁡n)\mathcal{O(nm \log n)}。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f; 
    }
    
    const int N = 60, M = 410;
    
    int n, m;
    
    int top[N], a[N][M];
    int em;
    
    int t;
    pair<int, int> ans[820001];
    
    void move(int x, int y) {
        ans[++ t] = make_pair(x, y);
    
        a[y][++ top[y]] = a[x][top[x] --];
    }
    
    bool impx[M], impy[M];
    
    int merge(int x, int y, int mid) {
        int cx = 0, cy = 0;
    
        for (int i = 1; i <= m; i ++)
            impx[i] = a[x][i] <= mid,
            impy[i] = a[y][i] <= mid;
    
        for (int i = 1; i <= m; i ++)
            cx += impx[i], cy += impy[i];
    
        if (cx + cy > m) {
            cx = m - cx, cy = m - cy;
    
            for (int i = 1; i <= m; i ++)
                impx[i] ^= 1, impy[i] ^= 1;
        }
    
        for (int i = 1; i <= m; i ++)
            if (!impx[i] && cx + cy < m)
                impx[i] = 1, cx ++;
    
        for (int i = cx; i; i --)
            move(y, em);
    
        for (int i = m; i; i --)
            if (impx[i]) move(x, y);
            else move(x, em);
    
        for (int i = m - cx; i; i --)
            move(em, x);
    
        for (int i = cx; i; i --)
            move(y, x);
    
        for (int i = cx; i; i --)
            move(em, y);
    
        for (int i = cx; i; i --)
            move(x, em);
    
        for (int i = m; i; i --)
            if (impy[i]) move(y, em);
            else move(y, x);
    
        int p = em; em = y;
        return p;
    }
    
    void solve(int l, int r) {
        if (l == r) return;
        int mid = (l + r) >> 1;
    
        vector<int> now;
        for (int i = 1; i <= n + 1; i ++) {
            if (i == em) continue;
            if (l <= a[i][1] && a[i][1] <= r) now.push_back(i);
        }
    
        for (int i = 0; i + 1 < (int)now.size(); i ++)
            now[i + 1] = merge(now[i], now[i + 1], mid);
    
        solve(l, mid), solve(mid + 1, r);
    }
    
    int main() {
        n = read(), m = read();
    
        em = n + 1;
    
        for (int i = 1; i <= n; i ++) {
            top[i] = m;
            for (int j = 1; j <= m; j ++)
                a[i][j] = read();
        }
    
        solve(1, n);
    
        printf("%d\n", t);
        for (int i = 1; i <= t; i ++)
            printf("%d %d\n", ans[i].first, ans[i].second);
    
        return 0;
    } 
    
    // I hope changle_cyx can pray for me. 

    T4. 微信步数

    LOJ 3389

    Solution

    算法一

    部分分:wi≤106w_i \leq 10^6。

    不难想到,可以考虑计算 “ 走完了第 ii 步后恰好走出场地 “ 的所有点对答案的贡献。

    为了方便叙述,约定:

    • 一个周期:前 nn 步组成的路线。
    • LiL_i:在第 ii 个维度上,当前仍然在场地内的点的坐标的最小值。
    • RiR_i:在第 ii 个维度上,当前仍然在场地内的点的坐标的最大值。
    • v→\overrightarrow{v}:经过了一个周期后的位移向量;viv_i:位移向量 v→\overrightarrow{v} 在第 ii 个维度上的位移。

    引理 1

    若会出现某一个点死循环,则满足以下两个条件。

    (1):经过了一个周期后,存在一个点没有走出场地。

    (2):v→=0→\overrightarrow{v} = \overrightarrow{0}。

    证明

    必要性:显然。

    充分性:考虑满足(11)的点,因为 v→=0→\overrightarrow{v} = \overrightarrow{0},所以无论走了多少个周期,该点始终呆在原地,也不会在走周期的过程中走出场地。故出现死循环。

    故命题得证,QED。

    考虑一下什么情况下会对答案造成贡献。

    引理 2

    若第 ii 步对答案有贡献,则当前在第 cic_i 维上的位移,一定是向 “ 正方向 “ 走或向 “反方向 “ 走的历史位移最大值(即可以更新 LciL_{c_i} 或 RciR_{c_i})。

    证明

    考虑 LiL_i 和 RiR_i 的定义,不难发现:在第 cic_i 维中,所有离开场地的点的坐标一定在 [1,Lci) ⋃ (Rci,wci][1, L_{c_i}) \ \bigcup \ (R_{c_i}, w_{c_i}] 内。

    那么,若第 ii 步后 LciL_{c_i} 或 RciR_{c_i} 没有得到更新,那么 [1,Lci) ⋃ (Rci,wci][1, L_{c_i}) \ \bigcup \ (R_{c_i}, w_{c_i}] 是不会变的,故离开场地的点的集合也没变。故在该种情况下,第 ii 步不对答案造成贡献。

    进一步分析可知:若第 ii 步后 LciL_{c_i} 或 RciR_{c_i} 得到了更新,那么这一批离开场地的点的坐标均为更新后的 Lci−1L_{c_i} - 1 或 Rci+1R_{c_i} + 1。

    故命题得证,Q.E.D

    考虑一下该种情况下会造成多少贡献。

    引理 3

    若第 ii 步对答案有贡献,则该贡献值为 i×∏j≠ci(Rj−Lj+1)i \times \prod\limits_{j \neq c_i} (R_j - L_j + 1)。

    证明

    对于第 cic_i 维,这一批离开场地的点的坐标均为更新后的 Lci−1L_{c_i} - 1 或 Rci+1R_{c_i} + 1。

    对于除了第 cic_i 维的任意一个维度,现在考虑第 pp 维。
    显然,这一批离开场地的点的坐标可以在 [Lp,Rp][L_p, R_p] 中任意做选择。

    根据乘法原理,这一批离开场地的点共有:

    (R1−L1+1)×⋯×(Rci−1−Lci−1+1)×1×(Rci+1−Lci+1+1)×⋯×(Rk−Lk+1)(R_1 - L_1 + 1) \times \cdots \times (R_{c_i - 1} - L_{c_i - 1} + 1) \times 1 \times (R_{c_i + 1} - L_{c_i + 1} + 1) \times \cdots \times (R_k - L_k + 1)

    即为:

    ∏j≠ci(Rj−Lj+1)\prod\limits_{j \neq c_i} (R_j - L_j + 1)

    将上式乘上 ii,即为第 ii 步对答案的贡献值。

    故命题得证,Q.E.D

    至此,我们已经有方法可以计算出正确的答案。只不过,要是直接枚举 ii 的话,时间复杂度是不能接受的。

    我们还没有利用到移动路线的 “ 周期性 “,接下来就来讨论一下 “ 周期性 “ 在本题中的特殊效果。为了方便叙述,我们称可以对答案造成贡献的一步为 ” 特殊步 “。

    引理 4

    (1):当第一周期中的第 ii 步为 “ 特殊步 “ 时:

    • 则第二周期中的第 i+ni + n 步,第三周期中的第 i+2ni + 2n 步,…,均不一定为 “ 特殊步 “。

    (2):当第一周期中的第 ii 步为 “ 特殊步 “,且第二周期中的第 i+ni + n 步也为 “ 特殊步 “ 时:

    • 第三周期中的第 i+2ni + 2n 步,第四周期中的第 i+3ni + 3n 步,…,一定均为 “ 特殊步 “。

    引理 4 的推论

    第一周期中 “ 特殊步 “ 的分布是特殊的; 第二、三、四、… 周期中 “ 特殊步 “ 的分布是相同的。

    根据引理 44 的推论,我们可以先计算出第一周期中 “ 特殊步 “ 对答案的贡献。

    对于第二、三、四、… 周期,考虑步数模 nn 的结果,对于模 nn 的所有同余类 1‾,2‾,⋯ ,n−1‾,0‾\overline{1}, \overline{2}, \cdots, \overline{n - 1}, \overline{0},我们可以分别计算每个同余类对答案的贡献。

    引理 5

    设当前进行到了第 ii 步,若进行到了第 i+ni + n 步时,该点还在场地内,对于第 jj 维的变化是:

    (1):若 vj>0v_j > 0,则 Lj←Lj+∣vj∣L_j \gets L_j + |v_j|。

    (2):若 vj<0v_j < 0,则 Rj←Rj−∣vj∣R_j \gets R_j - |v_j|。

    (3):对于 Rj−Lj+1R_j - L_j + 1,其值将会变化为:

    (Rj−Lj+1)−∣vj∣(R_j - L_j + 1) - |v_j|

    证明

    不难发现,若 “ 进行到第 i+ni + n 步时,该点还在场地内 “。

    则 “ 前 ii 步组成的路径 “ 与 “ 前 i+ni + n 步组成的路径 “ 之间只差了一个周期位移向量 v→\overrightarrow{v}。
    (在该情况下,位移的先后顺序不影响最终结果)

    那么,在只考虑第 jj 维的情况下。

    相当于进行到了第 ii 步,然后又经过了一个周期后,坐标值被加上了 vjv_j。

    故命题得证,Q.E.D

    引理 5 的推论

    对于第二周期中的第 ii 步(其中 n<i≤2nn < i \leq 2n),若第 ii 步是一个 “ 特殊步 “。

    考虑第 n∗x+(i−n)n \ast x + (i - n) 步,若该步也是一个 “ 特殊步 “,则该步对答案的贡献为:

    [n×(x−1)+i]∏j≠ci[−∣vj∣×(x−1)+(Rj−Lj+1)][n \times (x - 1) + i] \prod \limits_{j \neq c_i} [-|v_j| \times (x - 1) + (R_j - L_j + 1)]

    即:

    [n×x+(i−n)]∏j≠ci[−∣vj∣×x+(Rj−Lj+1+∣vj∣)][n \times x + (i - n)] \prod\limits_{j \neq c_i}[-|v_j| \times x + (R_j - L_j + 1 + |v_j|)]

    至此,已经有了一个初步的做法。

    枚举 i=1→ni = 1 \to n,先计算出第一周期中 “ 特殊步 “ 对答案的贡献。

    再枚举 i=(n+1)→2ni = (n + 1) \to 2n,计算每个模 nn 的同余类 i−n‾\overline{i - n} 对答案的贡献。具体地,根据引理 55 的推论,在循环内部再枚举一个 xx 即可。

    时间复杂度玄学,上界是 O(nk×max⁡1≤i≤k{wi})\mathcal{O}(nk \times \max\limits_{1\leq i\leq k} \left\{w_i\right\}),但实际上远不能达到上界,所以可以拿到可观的 8080 分。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f;
    }
    
    const int N = 500100, SIZE = 11;
    const int mod = 1e9 + 7;
    
    int n, k;
    
    int w[SIZE];
    int c[N], d[N];
    
    int L[SIZE], R[SIZE];
    
    int v[SIZE];
    int u[SIZE];
    
    int cur[SIZE];
    
    int ans;
    
    int main() {
        n = read(), k = read();
    
        for (int i = 1; i <= k; i ++)
            w[i] = read();
    
        for (int i = 1; i <= n; i ++)
            c[i] = read(), d[i] = read();
    
        // judgment has no answer.
    
        for (int i = 1; i <= k; i ++)
            L[i] = 1, R[i] = w[i];
    
        for (int i = 1; i <= n; i ++) {
            v[c[i]] += d[i];
    
            if (v[c[i]]) {
                if (v[c[i]] > 0) {
                    int val = v[c[i]];
                    if (w[c[i]] - val < R[c[i]]) R[c[i]] = w[c[i]] - val; 
                } else {
                    int val = -v[c[i]];
                    if (val + 1 > L[c[i]]) L[c[i]] = val + 1;
                }
            }
        }
    
        bool flag1 = 1;
        for (int i = 1; i <= k; i ++)
            if (L[i] > R[i]) flag1 = 0;
    
        bool flag2 = 1;
        for (int i = 1; i <= k; i ++)
            if (v[i]) flag2 = 0;
    
        if (flag1 && flag2) {
            puts("-1");
            return 0;
        }
    
        // work
    
        for (int i = 1; i <= k; i ++)
            L[i] = 1, R[i] = w[i];
    
        for (int i = 1; i <= n; i ++) {
            int C = c[i], D = d[i];
    
            u[C] += D;
    
            bool great = 0;
    
            if (u[C]) {
                if (u[C] > 0) {
                    int val = u[C];
                    if (w[C] - val < R[C])
                        R[C] = w[C] - val, great = 1;
                } else {
                    int val = -u[C];
                    if (val + 1 > L[C])
                        L[C] = val + 1, great = 1;
                }
            }
    
            if (great) {
                int val = 1;
                for (int j = 1; j <= k; j ++) {
                    if (j == C) continue;
                    val = 1ll * val * (R[j] - L[j] + 1) % mod;
                }
    
                ans = (ans + 1ll * val * i) % mod;
    
                if (L[C] > R[C]) {
                    printf("%d\n", ans);
                    return 0;
                }
            }
        }
    
        for (int i = n + 1; i <= 2 * n; i ++) {
            int C = c[i - n], D = d[i - n];
    
            u[C] += D;
    
            bool great = 0;
    
            if (u[C]) {
                if (u[C] > 0) {
                    int val = u[C];
                    if (w[C] - val < R[C])
                        great = 1;
                } else {
                    int val = -u[C];
                    if (val + 1 > L[C])
                        great = 1;
                }
            }
    
            if (great) {
                int mul = i;
                for (int j = 1; j <= k; j ++) cur[j] = R[j] - L[j] + 1;
    
                bool keep = 1;
                while (keep) {
                    int val = 1;
                    for (int j = 1; j <= k; j ++) {
                        if (j == C) continue;
                        val = 1ll * val * cur[j] % mod;
                    }
    
                    ans = (ans + 1ll * val * mul) % mod;
    
                    mul = (mul + n) % mod;
                    for (int j = 1; j <= k; j ++) {
                        cur[j] -= abs(v[j]);
    
                        if (cur[j] <= 0) {
                            keep = 0;
                            break;
                        }
                    }
                }
            }
    
            if (u[C]) {
                if (u[C] > 0) {
                    int val = u[C];
                    if (w[C] - val < R[C])
                        R[C] = w[C] - val;
                } else {
                    int val = -u[C];
                    if (val + 1 > L[C])
                        L[C] = val + 1;
                }
            }
    
            if (L[C] > R[C]) {
                printf("%d\n", ans);
                return 0;
            }
        }
    
        printf("%d\n", ans);
    
        return 0;
    }
    
    // I hope changle_cyx can pray for me. 

    算法二

    特殊性质:wi≤109w_i \leq 10^9。

    看起来「算法一」非常有前途,考虑优化。优化的重点其实在于计算模 nn 的所有同余类 1‾,2‾,⋯ ,n−1‾,0‾\overline{1}, \overline{2}, \cdots, \overline{n - 1}, \overline{0} 对答案的贡献。

    对于第二周期中的第 ii 步(其中 n<i≤2nn < i \leq 2n),若第 ii 步是一个 “ 特殊步 “。

    考虑第 n∗x+(i−n)n \ast x + (i - n) 步,若该步也是一个 “ 特殊步 “,则不难发现,该步对答案的贡献是一个与 xx 有关的多项式,可以考虑用 f(x)f(x) 表示:

    f(x)=[n×x+(i−n)]∏j≠ci[−∣vj∣×x+(Rj−Lj+1+∣vj∣)]f(x) = [n \times x + (i - n)] \prod\limits_{j \neq c_i}[-|v_j| \times x + (R_j - L_j + 1 + |v_j|)]

    注意到 f(x)f(x) 的每个乘积项,都是关于 xx 的一次二项式。

    可以考虑将这 kk 个乘积项卷在一起,即可得到一个 kk 次多项式 f(x)f(x)。至于计算出 f(x)f(x) 的系数,直接暴力卷即可,因为 kk 很小,所以复杂度肯定是可以接受的。

    多项式乘法(卷积):

    • 给定两个多项式 f(x)f(x) 与 g(x)g(x):
    f(x)=∑i=0nai×xif(x) = \sum\limits_{i = 0}^n a_i \times x^i
    g(x)=∑j=0mbj×xjg(x) = \sum\limits_{j = 0}^m b_j \times x^j
    • 要计算多项式 Q(x)=f(x)×g(x)Q(x) = f(x) \times g(x):
    Q(x)=∑i=0n∑j=0mai×bj×xi+jQ(x) = \sum\limits_{i = 0}^n \sum\limits_{j = 0}^m a_i \times b_j \times x^{i + j}

    考虑计算贡献。设模 mm 的同余类 i‾\overline{i} 从第二周期开始,最多要计算到第 EE 轮,不难得到:

    E=min⁡1≤i≤k,vi≠0{⌊Ri−Li∣vi∣⌋+1}E = \min\limits_{1 \leq i \leq k, v_i \neq 0} \left\{ \left\lfloor\frac{R_i - L_i}{|v_i|}\right\rfloor + 1 \right\}

    此时贡献为:

    ∑x=1Ef(x)\sum\limits_{x = 1}^E f(x)

    将 f(x)f(x) 用 ∑i=0kai×xi\sum\limits_{i = 0}^k a_i \times x^i 替换,得:

    ∑x=1E∑i=0kai×xi\sum\limits_{x = 1}^E \sum\limits_{i = 0}^k a_i \times x^i

    交换枚举顺序,得:

    ∑i=0k(ai×∑x=1Exi)\sum\limits_{i = 0}^k \left( a_i \times \sum\limits_{x = 1}^E x^i \right)

    至于要快速计算函数 Sk(n)=∑i=1nikS_k(n) = \sum\limits_{i = 1}^n i^k,是一个非常经典的问题。详见 CF622F The Sum of the k-th Powers。

    本篇题解中,代码给出的是 “ 拉格朗日插值 “。

    代码中并没有直接拉格朗日插值,而是使用拉格朗日插值先预处理出 Sk(n)S_k(n) 所对应的关于 nn 的 k+1k + 1 次多项式,然后再代入 xx 进行计算。

    时间复杂度 O(nk2)\mathcal{O}(nk^2)。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f;
    }
    
    int power(int a, int b, int p) {
        int ans = 1;
        for (; b; b >>= 1) {
            if (b & 1) ans = 1ll * ans * a % p;
            a = 1ll * a * a % p; 
        }
        return ans;
    }
    
    const int N = 500100, SIZE = 20;
    const int mod = 1e9 + 7;
    
    int n, k;
    
    int w[SIZE];
    int c[N], d[N];
    
    int L[SIZE], R[SIZE];
    
    int v[SIZE];
    int u[SIZE];
    
    struct polynomial {
        int m;
        int num[SIZE];
    
        polynomial() {
            m = 0;
            memset(num, 0, sizeof(num));
        }
    
        polynomial(int a, int b, int c) { m = a, num[0] = b, num[1] = c; }
    };
    
    polynomial operator + (polynomial a, polynomial b) {
        polynomial c;
    
        c.m = a.m;
        for (int i = 0; i <= a.m; i ++)
            c.num[i] = (a.num[i] + b.num[i]) % mod;
    
        return c;
    }
    
    polynomial operator * (polynomial a, polynomial b) {
        polynomial c;
    
        c.m = a.m + b.m;
        for (int i = 0; i <= a.m; i ++)
            for (int j = 0; j <= b.m; j ++)
                c.num[i + j] = ((c.num[i + j] + 1ll * a.num[i] * b.num[j]) % mod + mod) % mod;
    
        return c;
    }
    
    int calc(polynomial a, int x) {
        int ans = 0;
        for (int i = 0, val = 1; i <= a.m; i ++, val = 1ll * val * x % mod)
            ans = (ans + 1ll * a.num[i] * val) % mod;
        return ans;
    }
    
    polynomial g[SIZE];
    
    int val[SIZE];
    
    void Lagrange(int K) {
        val[0] = 0;
        for (int i = 1; i <= K + 2; i ++) val[i] = (val[i - 1] + power(i, K, mod)) % mod;
    
        g[K].m = K + 1;
    
        for (int i = 1; i <= K + 2; i ++) {
            polynomial p = polynomial(0, 1, 0);
            int q = 1;
    
            for (int j = 1; j <= K + 2; j ++) {
                if (i == j) continue;
                p = p * polynomial(1, mod - j, 1);
                q = 1ll * q * (((i - j) + mod) % mod) % mod;
            }
    
            p = p * polynomial(0, power(q, mod - 2, mod), 0);
            p = p * polynomial(0, val[i], 0);
    
            g[K] = g[K] + p;
        }
    }
    
    int ans;
    
    int main() {
        n = read(), k = read();
    
        for (int i = 1; i <= k; i ++)
            w[i] = read();
    
        for (int i = 1; i <= n; i ++)
            c[i] = read(), d[i] = read();
    
        // judgment has no answer.
    
        for (int i = 1; i <= k; i ++)
            L[i] = 1, R[i] = w[i];
    
        for (int i = 1; i <= n; i ++) {
            v[c[i]] += d[i];
    
            if (v[c[i]]) {
                if (v[c[i]] > 0) {
                    int val = v[c[i]];
                    if (w[c[i]] - val < R[c[i]]) R[c[i]] = w[c[i]] - val; 
                } else {
                    int val = -v[c[i]];
                    if (val + 1 > L[c[i]]) L[c[i]] = val + 1;
                }
            }
        }
    
        bool flag1 = 1;
        for (int i = 1; i <= k; i ++)
            if (L[i] > R[i]) flag1 = 0;
    
        bool flag2 = 1;
        for (int i = 1; i <= k; i ++)
            if (v[i]) flag2 = 0;
    
        if (flag1 && flag2) {
            puts("-1");
            return 0;
        }
    
        // work
    
        for (int i = 1; i <= k; i ++)
            L[i] = 1, R[i] = w[i];
    
        for (int i = 1; i <= n; i ++) {
            int C = c[i], D = d[i];
    
            u[C] += D;
    
            bool great = 0;
    
            if (u[C]) {
                if (u[C] > 0) {
                    int val = u[C];
                    if (w[C] - val < R[C])
                        R[C] = w[C] - val, great = 1;
                } else {
                    int val = -u[C];
                    if (val + 1 > L[C])
                        L[C] = val + 1, great = 1;
                }
            }
    
            if (great) {
                int val = 1;
                for (int j = 1; j <= k; j ++) {
                    if (j == C) continue;
                    val = 1ll * val * (R[j] - L[j] + 1) % mod;
                }
    
                ans = (ans + 1ll * val * i) % mod;
    
                if (L[C] > R[C]) {
                    printf("%d\n", ans);
                    return 0;
                }
            }
        }
    
        for (int i = 0; i <= k; i ++)
            Lagrange(i);
    
        for (int i = n + 1; i <= 2 * n; i ++) {
            int C = c[i - n], D = d[i - n];
    
            u[C] += D;
    
            bool great = 0;
    
            if (u[C]) {
                if (u[C] > 0) {
                    int val = u[C];
                    if (w[C] - val < R[C])
                        great = 1;
                } else {
                    int val = -u[C];
                    if (val + 1 > L[C])
                        great = 1;
                }
            }
    
            if (great) {
                int Round = 0x3f3f3f3f;
    
                for (int j = 1; j <= k; j ++) {
                    if (!v[j]) continue;
                    Round = min(Round, ((R[j] - L[j]) / abs(v[j])) + 1);
                }
    
                polynomial f = polynomial(0, 1, 0);
    
                f = f * polynomial(1, i - n, n);
    
                for (int j = 1; j <= k; j ++) {
                    if (j == C) continue;
                    f = f * polynomial(1, R[j] - L[j] + 1 + abs(v[j]), mod - abs(v[j]));
                }
    
                for (int j = 0; j <= k; j ++)
                    ans = (ans + 1ll * f.num[j] * calc(g[j], Round)) % mod;
            }
    
            if (u[C]) {
                if (u[C] > 0) {
                    int val = u[C];
                    if (w[C] - val < R[C])
                        R[C] = w[C] - val;
                } else {
                    int val = -u[C];
                    if (val + 1 > L[C])
                        L[C] = val + 1;
                }
            }
    
            if (L[C] > R[C]) {
                printf("%d\n", ans);
                return 0;
            }
        }
    
        printf("%d\n", ans);
    
        return 0;
    }
    
    // I hope changle_cyx can pray for me.