BZOJ2962 序列操作

2015.03.04 15:26 Wed| 1 visits oi_2015| 2015_刷题日常| Text

吐槽

网上唯一的题解说:

开始WA的几百毫秒的都是由于我比较SB造成的,可是跑了10几秒的程序我查了N久也查不出错

最后灵机一动把50000改成60000就过了,也不知道为啥T_T

这究竟是为什么?

for (int i = 0; i <= n; ++i)
{
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j < i; ++j) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % M;
}

这个地方可怜的数组已经哭了有么 -_-||

Solution

用线段树维护一段区间内,$p[K]$ 表示选择 $K$ 个数相乘的所有方案的和($0\le K\le 20$)。

对于相邻的两段区间 $s1$, $s2$,在合并的时候可以直接按照卷积的形式乘到一起:

接下来考虑操作 2,只需要找到相应的区间然后将它的 $p[1], p[3], ...$ 更新为相反数即可。

最后考虑操作 1 的 $+c$ 操作,经过一番推导(找规律)后可以得到

这样只需要维护一个双标记的线段树就解决辣~

被卡了好久常数QAQ

BZOJ的测评竟然比楼下机房的渣机还要慢!一定要简化取模次数!!!

我用 i7 机器我自豪!!!

Code

#include <bits/stdc++.h>
using namespace std;

#define N 50005
#define mod 19940417
#define lson (pos << 1)
#define rson (pos << 1 | 1)
#define M(x) (((x) % mod + mod) % mod)

int n, q, a[N], add[N << 2], rev[N << 2], c[N][22];

struct $
{
    int p[22];
    $() : p() {}
    $(bool x) : p() { p[0] = 1; }
    inline int &operator[](int x) { return p[x]; }
} f[N << 2];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void update1(int pos, int l, int r, int z)
{
    add[pos] = M(add[pos] + z);
    $ v(true);
    for (int i = 1; i <= 20; ++i)
        for (int t = 1, j = i; j >= 0; t = 1ll * t * z % mod, --j)
            v[i] = M(v[i] + 1ll * f[pos][j] * c[r-l+1 - j][i - j] % mod * t);
    f[pos] = v;
}

inline void update2(int pos)
{
    for (int i = 1; i <= 20; i += 2)
        f[pos][i] = (mod - f[pos][i]) % mod;
    rev[pos] ^= 1;
    add[pos] = (mod - add[pos]) % mod;
}

void pushup(int pos)
{
    f[pos] = $();
    for (int i = 0; i <= 20; ++i)
        for (int j = 0; j <= 20 - i; ++j)
            f[pos][i + j] = M(f[pos][i + j] +
                            1ll * f[lson][i] * f[rson][j] % mod);
}

void pushdown(int pos, int l, int r)
{
    if (rev[pos])
    {
        update2(lson); update2(rson); rev[pos] ^= 1;
    }
    if (add[pos])
    {
        int mid = (l + r) >> 1;
        update1(lson, l, mid, add[pos]);
        update1(rson, mid + 1, r, add[pos]);
        add[pos] = 0;
    }
}

void build(int pos, int l, int r)
{
    f[pos] = $(true);
    if (l == r) { f[pos][1] = a[l]; return ; }
    int mid = (l + r) >> 1;
    build(lson, l, mid); build(rson, mid + 1, r);
    pushup(pos);
}

void modify(int pos, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y)
    {
        update1(pos, l, r, z);
        return ;
    }
    pushdown(pos, l, r);
    int mid = (l + r) >> 1;
    if (x <= mid) modify(lson, l, mid, x, y, z);
    if (y > mid) modify(rson, mid + 1, r, x, y, z);
    pushup(pos);
}

void inverse(int pos, int l, int r, int x, int y)
{
    if (x <= l && r <= y)
    {
        update2(pos);
        return ;
    }
    pushdown(pos, l, r);
    int mid = (l + r) >> 1;
    if (x <= mid) inverse(lson, l, mid, x, y);
    if (y > mid) inverse(rson, mid + 1, r, x, y);
    pushup(pos);
}

$ query(int pos, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y)
        return f[pos];
    pushdown(pos, l, r);
    int mid = (l + r) >> 1;
    if (x > mid) return query(rson, mid + 1, r, x, y, z);
    if (y <= mid) return query(lson, l, mid, x, y, z);
    $ re, t1 = query(lson, l, mid, x, y, z),
          t2 = query(rson, mid + 1, r, x, y, z);
    for (int i = 0; i <= 20; ++i)
        for (int j = 0; j <= 20 - i; ++j)
            re[i + j] = (re[i + j] +
                        1ll * t1[i] * t2[j] % mod) % mod;
    return re;
}

int main()
{
    cin >> n >> q;
    for (int i = 0; i <= n; ++i)
    {
        c[i][0] = 1;
        for (int j = 1; j < i && j <= 20; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        if (i <= 20) c[i][i] = 1;
    }
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    build(1, 1, n);
    char opt[3]; int x, y, z;
    for (int i = 1; i <= q; ++i)
    {
        scanf("%s", opt);
        switch (opt[0])
        {
            case 'I':
                x = read(), y = read(), z = read();
                modify(1, 1, n, x, y, z);
                break;
            case 'R':
                x = read(), y = read();
                inverse(1, 1, n, x, y);
                break;
            case 'Q':
                x = read(), y = read(), z = read();
                printf("%d\n", query(1, 1, n, x, y, z)[z] % mod);
                break;
        }
    }
}