Skip to content

S2OJ - 1486. 数据结构

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

题面

题目描述

维护一个正整数多重集合 SS,初始为空,支持两个操作:

  1. 插入:插入一个新数 xx
  2. 修改:令集合中所有数加 11

每次操作结束后,输出 SS 中所有数的 kk 次方和,kk 预先给定,对 109+710^9 + 7 取模。

输入格式

第一行两个数 m,km, k,其中 mm 表示操作次数。

接下来 mm 行,每行可能为以下两种之一:

  1. 0 x ,表示插入一个大小为 xx 的新元素。
  2. 1,表示令集合 SS 里所有数加一。

输出格式

输出 mm 行,第 ii 行表示第 ii 次操作结束之后,SS 中所有数的 kk 次方和。

样例输入输出

样例输入 #1

3 2
0 1
0 1
1

样例输出 #1

1
2
8

数据范围与约定

对于 100%100\% 的数据,m2×105m \leq 2 \times 10^51k501 \leq k \leq 500x1050 \leq x \leq 10^5

思路

这道题考场上大家都是直接把二项式定理拿出来用 A 掉的,复杂度是 O(nk2)O(nk^2),可惜就我一个菜鸡把二项式定理忘掉了,所以通过杨辉三角手推完二项式定理之后顺带着出来了一种 O(mk)O(mk) 的做法。可惜的是考场上忘记处理负数取模的问题导致猛挂到 20 分。下面带来我的考场思路,可能会有些许罗嗦:

首先题目要求在每次操作完成后输出多重集合 SS 中所有数的 kk 次方和,因此可以从这里下手。

插入操作的数的 kk 次方可以直接加进全局和中,因此只需要考虑如何处理全局加 11 的问题即可。

先写出一些加 11kk 次方和的式子进行观察:

  1. k=1k = 1 时,

    (x1+1)1+(x2+1)++(xn+1)=1×(x1+x2++xn)+1×(1+1++1)n1\begin{aligned} & (x_1 + 1)^1 + (x_2 + 1) + \cdots + (x_n + 1) \\ =& 1 \times (x_1 + x_2 + \cdots + x_n) + 1 \times \underbrace{(1 + 1 + \cdots + 1)}_{n \text{ 个 } 1} \\ \end{aligned}

  2. k=2k = 2 时,

    (x1+1)2+(x2+1)2++(xn+1)2=(x12+2x1+1)+(x22+2x2+1)++(xn2+2xn+1)=1×(x12+x22++xn2)+2×(x1+x2++xn)+1×(1+1++1)n1\begin{aligned} & (x_1 + 1)^2 + (x_2 + 1)^2 + \cdots + (x_n + 1)^2 \\ =& (x_1^2 + 2 x_1 + 1) + (x_2^2 + 2 x_2 + 1) + \cdots + (x_n^2 + 2 x_n + 1) \\ =& 1 \times (x_1^2 + x_2^2 + \cdots + x_n^2) + 2 \times (x_1 + x_2 + \cdots + x_n) + 1 \times \underbrace{(1 + 1 + \cdots + 1)}_{n \text{ 个 } 1} \\ \end{aligned}

  3. k=3k = 3 时,

    (x1+1)3+(x2+1)3++(xn+1)3=(x13+3x12+3x1+1)+(x23+3x22+3x2+1)++(xn3+3xn2+3xn+1)=1×(x13+x23++xn3)+3×(x12+x22++xn2)+3×(x1+x2++xn)+1×(1+1++1)n1\begin{aligned} & (x_1 + 1)^3 + (x_2 + 1)^3 + \cdots + (x_n + 1)^3 \\ =& (x_1^3 + 3 x_1^2 + 3 x_1 + 1) + (x_2^3 + 3 x_2^2 + 3 x_2 + 1) + \cdots + (x_n^3 + 3 x_n^2 + 3 x_n + 1) \\ =& 1 \times (x_1^3 + x_2^3 + \cdots + x_n^3) + 3 \times (x_1^2 + x_2^2 + \cdots + x_n^2) + 3 \times (x_1 + x_2 + \cdots + x_n) + 1 \times \underbrace{(1 + 1 + \cdots + 1)}_{n \text{ 个 } 1} \\ \end{aligned}

  4. k=4k = 4 时,

    (x1+1)4+(x2+1)4++(xn+1)4=(x14+4x13+6x12+4x1+1)+(x24+4x23+6x22+4x2+1)++(xn4+4xn3+6xn2+4xn+1)=1×(x14+x24++xn4)+4×(x13+x23++xn3)+6×(x12+x22++xn2)+4×(x1+x2++xn)+1×(1+1++1)n1\begin{aligned} & (x_1 + 1)^4 + (x_2 + 1)^4 + \cdots + (x_n + 1)^4 \\ =& (x_1^4 + 4 x_1^3 + 6 x_1^2 + 4 x_1 + 1) + (x_2^4 + 4 x_2^3 + 6 x_2^2 + 4 x_2 + 1) + \cdots + (x_n^4 + 4 x_n^3 + 6 x_n^2 + 4 x_n + 1) \\ =& 1 \times (x_1^4 + x_2^4 + \cdots + x_n^4) + 4 \times (x_1^3 + x_2^3 + \cdots + x_n^3) + 6 \times (x_1^2 + x_2^2 + \cdots + x_n^2) + 4 \times (x_1 + x_2 + \cdots + x_n) + 1 \times \underbrace{(1 + 1 + \cdots + 1)}_{n \text{ 个 } 1} \\ \end{aligned}

可以观察到系数呈现出了杨辉三角的形式:

111121133114641\begin{array}{c} 1 \\ 1 \quad 1 \\ 1 \quad 2 \quad 1 \\ 1 \quad 3 \quad 3 \quad 1 \\ 1 \quad 4 \quad 6 \quad 4 \quad 1 \\ \end{array}

那么可以考虑记录全局累计增加的数 Δ\Delta,然后每次全局加之后都将 Δ+1\Delta + 1,再重新计算全局和。此时需要将新插入的数 xx 作为 xΔx - \Delta 存入以便计算。

现在再来看一看 (xi+Δ)k(x_i + \Delta)^k 的问题,有一种想法是可以将其按照 ((xi+(Δ1))+1)k((x_i + (\Delta - 1)) + 1)^k 的形式递归展开,比如 (x+2)2(x + 2)^2 就可以这样展开:

(x+2)2=(x+1)2+2(x+1)+1=(x2+2x+1)+2(x+1)+1=x2+4x+4\begin{aligned} & (x + 2)^2 \\ =& (x + 1)^2 + 2 (x + 1) + 1 \\ =& (x^2 + 2x + 1) + 2 (x + 1) + 1 \\ =& x^2 + 4x + 4 \\ \end{aligned}

k=2k = 2 时,系数分布如下图所示:

1×201×201×211×202×211×221×203×213×221×231×204×216×224×231×24\begin{array}{c} 1 \times 2^0 \\ 1 \times 2^0 \quad 1 \times 2^1 \\ 1 \times 2^0 \quad 2 \times 2^1 \quad 1 \times 2^2 \\ 1 \times 2^0 \quad 3 \times 2^1 \quad 3 \times 2^2 \quad 1 \times 2^3 \\ 1 \times 2^0 \quad 4 \times 2^1 \quad 6 \times 2^2 \quad 4 \times 2^3 \quad 1 \times 2^4 \\ \end{array}

推广得:

1×k01×k01×k11×k02×k11×k21×k03×k13×k21×k31×k04×k16×k24×k31×k4\begin{array}{c} 1 \times k^0 \\ 1 \times k^0 \quad 1 \times k^1 \\ 1 \times k^0 \quad 2 \times k^1 \quad 1 \times k^2 \\ 1 \times k^0 \quad 3 \times k^1 \quad 3 \times k^2 \quad 1 \times k^3 \\ 1 \times k^0 \quad 4 \times k^1 \quad 6 \times k^2 \quad 4 \times k^3 \quad 1 \times k^4 \\ \end{array}

举个稍大一些的例子:

(x1+2)4+(x2+2)4=(x14+8x13+24x12+32x1+24)+(x24+8x23+24x22+32x2+24)=(x14+x24)+8×(x13+x23)+24×(x12+x22)+32×(x1+x2)+(24+24)\begin{aligned} & (x_1 + 2)^4 + (x_2 + 2)^4 \\ =& (x_1^4 + 8 x_1^3 + 24 x_1^2 + 32 x_1 + 2^4) + (x_2^4 + 8 x_2^3 + 24 x_2^2 + 32 x_2 + 2^4) \\ =& (x_1^4 + x_2^4) + 8 \times (x_1^3 + x_2^3) + 24 \times (x_1^2 + x_2^2) + 32 \times (x_1 + x_2) + (2^4 + 2^4) \\ \end{aligned}

设左对齐的杨辉三角的第 ii 行第 jj 列上的数为 fi,jf_{i, j},那么可以将总和记为:

i=0k(fk,i×Δi×j=1nxjki)\sum_{i = 0}^{k} (f_{k, i} \times \Delta^i \times \sum_{j = 1}^{n} x_j^{k - i})

显然 j=1nxjki\sum_{j = 1}^{n} x_j^{k - i} 可以使用前缀和优化到 O(1)O(1),记为 sum\mathit{sum},最终形式为:

i=0k(fk,i×Δi×sumki)\sum_{i = 0}^{k} (f_{k, i} \times \Delta^i \times \mathit{sum}^{k - i})

复杂度为 O(mk)O(mk)

代码

#include <iostream>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2e5 + 5,
          K = 55;
const int mod = 1e9 + 7;

int m, k, d, cnt;
long long f[K][K], s[K], sum;

long long binpow(long long a, long long b) {
    a %= mod;

    long long res = 1;

    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }

    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> k;

    f[0][0] = 1;
    for (int i = 1; i <= k; i++) {
        f[i][0] = 1;

        for (int j = 1; j <= i; j++) {
            f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % mod;
        }
    }

    while (m--) {
        int op;

        cin >> op;

        if (op == 0) {
            int x;
            long long p = 1;

            cin >> x;

            s[0] = (s[0] + 1) % mod;

            for (int i = 1; i <= k; i++) {
                p = (p * (x - d) % mod + mod) % mod;
                s[i] = (s[i] + p) % mod;
            }

            sum = (sum + binpow(x, k)) % mod;
        } else {  // op == 1
            d++;

            sum = 0;
            for (int i = 0; i <= k; i++) {
                sum = (sum + f[k][i] * binpow(d, i) % mod * s[k - i] % mod) % mod;
            }
        }

        cout << sum << endl;
    }

    return 0;
}