BZOJ5087 Polycomp < bitset+分块 >

Problem

Polycomp

Description

你有三个系数为的多项式
求
为方便起见，将答案多项式所有系数对取模输出即可
如果，则

Input

一共三行，每行一个多项式，分别为
对于一个多项式，描述为个整数，其中为或，

Output

用同样的格式输出答案多项式
如果答案为，输出0 0

Sample Input

1
2
3

5 0 1 0 1 0 1
2 1 1 1
4 0 1 1 0 1

Sample Output

1 1 1

HINT

记表示多项式最高项的次数，

Source

By clj

标签：bitset 分块

Solution

陈老师神题。

直接用数组模拟乘除过程，可以做到，若用bitset维护，即可做到。然而这样还是会。

考虑类似分块的想法，将的每十位分成一段，预处理种情况对应的和，然后每次十位十位地加，即可做到，时间复杂度可以接受。
根据vanilla的调参，貌似这种先预处理的方法在块大小为时最快。

OwenOwl有更快的方法，即先不预处理出所有和，最后加的时候再根据每块情况计算，这样块大小可以更大，情况数更少，会更快。

Code

#include <bits/stdc++.h>
using namespace std;
typedef bitset<8001> poly;
template <class T> inline int read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
    return x;
}
int lf, lg, lh, len, LOG[1<<16|1];
poly f, g, h, t, ans, pw[17], s[1<<16|1];
void init() {for (int i = 2; i <= (1<<16); i++) LOG[i] = LOG[i>>1]+1;}
void mod(poly &p, int l) {
    for (int i = l; i >= lh; i--)
        if (p[i]) p ^= (h<<(i-lh));
}
poly mul(poly a, poly b) {
    poly ret = 0;
    for (int i = 0; i <= lh; i++)
        if (a[i]) ret ^= b<<i;
    mod(ret, 2*lh); return ret;
}
int getsta(int l, int r) {
    int ret = 0;
    for (int i = l; i <= r; i++)
        ret |= f[i]<<(i-l);
    return ret;
}
int main() {
    read(lf); for (int i = 0, x; i <= lf; i++) if (read(x)) f.set(i);
    read(lg); for (int i = 0, x; i <= lg; i++) if (read(x)) g.set(i);
    read(lh); for (int i = 0, x; i <= lh; i++) if (read(x)) h.set(i);
    mod(g, lg), pw[0].set(0), s[1].set(0), t.set(0), init();
    for (int i = 1; i <= 16; i++) pw[i] = mul(pw[i-1], g);
    for (int i = 2; i < (1<<16); i++) s[i] = s[i-(1<<LOG[i])]^pw[LOG[i]];
    for (int i = 0; i <= lf; i += 16, t = mul(t, pw[16]))
        ans ^= mul(s[getsta(i, i+15)], t);
    for (len = lh; !ans[len] && len; len--) ;
    printf("%d ", len);
    for (int i = 0; i <= len; i++)
        printf("%d ", ans[i] ? 1 : 0);
    return puts(""), 0;
}