「NOIP2020」 微信步数

[NOIP2020] 微信步数

暴力

先定义走完一次 $1\sim n$ 的步骤为一轮。

考虑所有点一起按照步骤走下去，每步可能会使原本存在的点出界。我们维护每步后剩余的点，累加即可。具体地，每个维度互不干扰，且对与一个维度而言，删除的必然是从左一段连续的区间和从右一段连续的区间，若在该步下维度 $i$ 剩下 $[l_i,r_i]$ ，那么剩余的总点数为 $\displaystyle\prod_{i=1}^{k} (r_i-l_i+1)$ 。

我们只要一步一步模拟即可，直到没有点剩余。另外判断无穷步：在第一轮后回到起点且还有点剩余。

复杂度为 $O(Tnk)$ ，其中 $T$ 为最多跑了几轮。

CODE

typedef long long ll;
const int N = 500010;
const int M = 16;
const int mod = 1e9 + 7;
int c[N], d[N], n, k, w[M];

namespace sub1 {
    int l[M], r[M], e[M];
    // l[i], r[i] 表示 i 维度向左 / 向右历史最大偏移量  e[i] 为当前偏移
    void solve() {
        ll ans = 1;
        for (int i = 1; i <= k; ++i) ans = (ans * w[i]) % mod;
        for (int T = 1; ; ++T) {
            for (int i = 1; i <= n; ++i) {
                e[c[i]] += d[i];
                l[c[i]] = min(l[c[i]], e[c[i]]);
                r[c[i]] = max(r[c[i]], e[c[i]]);
                ll t = 1;
                for (int j = 1; j <= k; ++j) {
                    if (w[j] - r[j] + l[j] <= 0) goto end;
                    t = (t * (w[j] - r[j] + l[j])) % mod;
                }
                ans = (ans + t) % mod;
            }
            if (T == 1) {
                bool flag = 1;
                for (int j = 1; j <= k; ++j) if (e[j] != 0) flag = 0;
                if (flag) { ans = -1; break; }
            }
        }
        end:
        printf("%lld\n", ans);
    }
}
int main() {
    read(n, k);
    for (int i = 1; i <= k; ++i) read(w[i]);
    for (int i = 1; i <= n; ++i) read(c[i], d[i]);
    sub1::solve();
    return 0;
}

正解

记在第一轮中第 $j$ 个维度，第 $i$ 步时的历史 最左 / 最右 偏移为 $l_{j,i},r_{j,i}$ 。记第 $j$ 个维度在第一轮中的偏移为 $e_j$ 。（详见上面代码）

那么在第二轮中第 $j$ 个维度，第 $i$ 步时的历史 最左 / 最右 偏移为 $\min(l_{j,i},l_{j,i}+e_j),\max(r_{j,i},l_{j,i}+e_j)$ 。

增加的偏移量可以表示为：

$$C_{j,i} = \max\left(0, l_{j,n} - (l_{j,i} + e_j)\right)+ \max\left(0, (r_{j,i} + e_j) - r_{j,n}\right)$$

仔细思考可以发现，第二轮（包括第二轮）之后，对一第 $i$ 步新增的偏移量是不变的，第一轮单独算。

我们记 $A_j=w_j - r_{j,n} + l_{j,n}$ 表示第一轮后第 $j$ 维度的剩余量，记 $B_j=C_{j,n}$ 表示之后每轮第 $j$ 维的新增偏移量。我们可以得到在第 $x+2$ 轮，第 $i$ 步，第 $j$ 维的剩余量 $A_j-B_jx-C_{j,i}$

令 $T=\min_{j=1}^{k} A_j/B_j$ 表示从第二轮开始跑了多少个整轮，最后没跑满整轮单独算，考虑中间的。

易得 $2\sim T+1$ 轮的贡献：

$$\sum_{x=0}^{T-1} \sum_{i=1}^{n} \prod_{j=1}^k \left(A_j -B_jx-C_{j,i}\right)$$

令

$$\begin{aligned} F_i(x)&=\prod_{j=1}^k \left(A_j -B_jx-C_{j,i}\right)\\ &=a_{i,0}+a_{i,1}x^1+a_{i,2}x^2+\dots+a_{i,k}x^k \end{aligned}$$

计算 $F_i(x) (i\in[1,n])$ 复杂度 $O(nk^2)$

$$\begin{aligned} &\quad \sum_{x=0}^{T-1} \sum_{i=1}^{n} \prod_{j=1}^k \left(A_j -B_jx-C_{j,i}\right)\\ &=\sum_{i=1}^n \sum_{x=0}^{T-1}F_i(x)\\ &=\sum_{i=1}^n \sum_{j=0}^k a_{i,j}\sum_{x=0}^{T-1}x^j \end{aligned}$$

计算一个 $k$ 次方和是 $O(k)$ 的，故这里 $O(nk^2)$

注： $1,2,\dots,n^2$ 的 $k$ 次方和是一个关于 $n$ 的 $k+1$ 次多项式，由于 $k\le 10$ ，我们用拉格朗日插值全部预处理出来即可。

CODE

#include <bits/stdc++.h>
template <typename Tp>
inline void read(Tp& x) {
    x = 0; bool fg = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') fg ^= 1; ch = getchar();}
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (Tp)(ch ^ 48), ch = getchar();
    if (fg) x = -x;
}
template <typename Tp, typename... Args>
void read(Tp& t, Args& ...args) { read(t); read(args...); }
using namespace std;
typedef long long ll;
const int N = 500010;
const int M = 16;
const int mod = 1e9 + 7;
int c[N], d[N], n, k, w[M];

ll fpow(ll a, ll b = mod - 2) {
    ll r = 1;
    for ( ; b; b >>= 1, a = a * a % mod) if (b & 1) r = r * a % mod;
    return r;
}

namespace sub1 {
    int l[M], r[M], e[M];
    void solve() {
        ll ans = 1;
        for (int i = 1; i <= k; ++i) ans = (ans * w[i]) % mod;
        for (int T = 1; ; ++T) {
            for (int i = 1; i <= n; ++i) {
                e[c[i]] += d[i];
                l[c[i]] = min(l[c[i]], e[c[i]]);
                r[c[i]] = max(r[c[i]], e[c[i]]);
                ll t = 1;
                for (int j = 1; j <= k; ++j) {
                    if (w[j] - r[j] + l[j] <= 0) {
                        fprintf(stderr, "end at T = %d i = %d j = %d\n", T, i, j);
                        goto end;
                    }
                    t = (t * (w[j] - r[j] + l[j])) % mod;
                }
                ans = (ans + t) % mod;
            }
            if (T == 1) {
                fprintf(stderr, "in first round %lld\n", ans);
            }
            if (T == 1) {
                bool flag = 1;
                for (int j = 1; j <= k; ++j) if (e[j] != 0) flag = 0;
                if (flag) { ans = -1; break; }
            }
        }
        end:
        printf("%lld\n", ans);
    }
}

namespace sub2 {
    int e[M], l[M][N], r[M][N];
    int C[M][N], A[M], B[M];
    // k 次方和
    const int _a[M][M] = {
        {1, 1},
        {0, 500000004, 500000004},
        {0, 166666668, 500000004, 333333336},
        {0, 0, 250000002, 500000004, 250000002},
        {0, 766666672, 0, 333333336, 500000004, 400000003},
        {0, 0, 916666673, 0, 416666670, 500000004, 166666668},
        {0, 23809524, 0, 833333339, 0, 500000004, 500000004, 142857144},
        {0, 0, 83333334, 0, 708333338, 0, 583333338, 500000004, 125000001},
        {0, 766666672, 0, 222222224, 0, 733333338, 0, 666666672, 500000004, 111111112},
        {0, 0, 450000003, 0, 500000004, 0, 100000000, 0, 750000006, 500000004, 700000005},
        {0, 348484851, 0, 500000003, 0, 1, 0, 1000000006, 0, 833333340, 500000004, 818181824},
    };
    /*
    # Python 拉格朗日插值求出 k 次方和 的多项式
    mod = int(1e9 + 7)
    def inv(a):
        return pow(a, mod - 2, mod)
    def mul(f, g):
        n, m = len(f), len(g)
        h = [0] * (n + m - 1)
        for i in range(n + m):
            for j in range(i + 1):
                if j < n and i - j < m:
                    h[i] = (h[i] + f[j] * g[i - j]) % mod
        return h
    def mula(f, a):
        n = len(f)
        h = [0] * n
        for i in range(n):
            h[i] = f[i] * a % mod
        return h
    def add(f, g):
        n = max(len(f), len(g))
        h = [0] * n
        for i in range(n):
            if i < len(f): h[i] += f[i]
            if i < len(g): h[i] += g[i]
            h[i] %= mod
        return h
    def La(y):
        n = len(y)
        r = list()
        for j in range(n):
            f = [1]
            for i in range(n):
                if i != j:
                    iv = inv((j - i) % mod) % mod
                    f = mul(f, [-i * iv % mod, iv])
            f = mula(f, y[j])
            r = add(r, f)
        return r
    def calc(f, x):
        n = len(f)
        r = 0
        for i in range(n):
            r = (r + pow(x, i, mod) * f[i]) % mod
        return r
    def Get(k):
        return La([sum(i**k for i in range(j + 1)) for j in range(k + 2)])
    */
    ll calc(int n, int k) {
        if (n < 0) return 0;
        ll x = 1, r = 0;
        for (int i = 0; i <= k + 1; ++i) {
            r = (r + x * _a[k][i]) % mod;
            x = (x * n) % mod;
        }
        return r;
    }
    void solve() {
        // l[j][i],r[j][i] 表示第 j 个维度，在第一轮第 i 步时的历史 最左/最右 偏移
        for (int i = 1; i <= n; ++i) {
            e[c[i]] += d[i];
            for (int j = 1; j <= k; ++j) {
                l[j][i] = l[j][i - 1];
                r[j][i] = r[j][i - 1];
            }
            l[c[i]][i] = min(l[c[i]][i], e[c[i]]);
            r[c[i]][i] = max(r[c[i]][i], e[c[i]]);
        }
        // 计算第一轮贡献
        ll ans = 0;
        for (int i = 0; i <= n; ++i) {
            ll tp = 1;
            for (int j = 1; j <= k; ++j) {
                if (w[j] - r[j][i] + l[j][i] == 0) {
                    // 第一轮就挂了
                    printf("%lld\n", ans);
                    return ;
                }
                tp = (tp * (w[j] - r[j][i] + l[j][i])) % mod;
            }
            ans = (ans + tp) % mod;
        }
        // 判断 无限步
        bool flag = 1;
        for (int j = 1; j <= k; ++j) if (e[j]) flag = 0;
        if (flag) {
            printf("-1\n");
            return ;
        }
        // 计算之后每轮，每步增加（相对于本轮开始）的偏移量 C
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                C[j][i] = max(0, l[j][n] - (l[j][i] + e[j]))
                + max(0, (r[j][i] + e[j]) - r[j][n]);
            }
        }

        for (int j = 1; j <= k; ++j) {
            A[j] = w[j] - r[j][n] + l[j][n];
            B[j] = C[j][n];
        }

        // A[j] - T * B[j] - C[j][i] >= 0 : T 中间跑了几个整轮
        int T = 1e9;
        for (int j = 1; j <= k; ++j) if (B[j] != 0) {
            int t = A[j] / B[j] + 1;
            if (A[j] - t * B[j] <= 0) --t;
            T = min(T, t);
        }
        // 第 2 到第 T + 1 轮都跑满
        for (int i = 1; i <= n; ++i) {
            // calc \prod_{j=1}^{k} (A_j - x B_j - C_{j,i})
            ll f[M]; memset(f, 0, sizeof(f));
            f[0] = 1;
            for (int j = 1; j <= k; ++j) {
                ll _0 = (A[j] - C[j][i] + mod) % mod, _1 = mod - B[j];
                for (int _i = j; _i >= 0; --_i) {
                    if (_i > 0) f[_i] = (f[_i] * _0 + f[_i - 1] * _1) % mod;
                    else f[_i] = f[_i] * _0 % mod;
                }
            }
            for (int j = 0; j <= k; ++j) {
                ans = (ans + f[j] * calc(T - 1, j)) % mod;
            }
        }
        // 计算最后一轮贡献 第 T + 2 轮
        for (int i = 1; i <= n; ++i) {
            ll tp = 1;
            for (int j = 1; j <= k; ++j) {
                if (A[j] - B[j] * T - C[j][i] <= 0) {
                    // End
                    printf("%lld\n", ans);
                    return ;
                }
                tp = (tp * (A[j] - B[j] * T - C[j][i])) % mod;
            }
            ans = (ans + tp) % mod;
        }
        printf("%lld\n", ans);
    }
}

int main() {
    read(n, k);
    for (int i = 1; i <= k; ++i) read(w[i]);
    for (int i = 1; i <= n; ++i) read(c[i], d[i]);
    sub2::solve();
    return 0;
}