【bitset 技巧 分塊】bzoj5087: polycomp

神仙zq發現了${n^2\sqrt n}\over 32$做法

Description

你有三個系數為0,1的多項式f(x),g(x),h(x)

求f(g(x)) mod h(x)

為方便起見，將答案多項式所有系數對2取模輸出即可

如果f(x)=Sigma(Ak * X^k)

則f(g(x))=Sigma(Ak(g(x))^K

Input

一共三行，每行一個多項式,分別為f,g,h

對于一個多項式描述為n P0,P1...Pn其中Pi為0或1

多項式P(x)=P₀+P₁*x+....+P_n*xⁿ

記n表示多項式最高項的次數,n<=4000

Output

用同樣的格式輸出答案多項式

如果答案為0，輸出0 0

---

題目分析

陳老師神題x1

觀察到這里多項式的所有操作都是在系數$\mod 2$的意義下的，因此可以用bitset來加速多項式的一些操作。例如$O(n^2)$實現多項式取模。

void mod(poly &a, int pos)
{
    for (int i=pos; i>=p; i--)
        if (a[i]) a ^= c<<(i-p), a[i] = 0;　　//我第一次居然把標紅地方給忘了
}

但是如同很多bitset的技巧題一樣，非常重要的一點是bitset每次整體操作的復雜度是??$O(size)$? 的。

這意味著$Poly\, +:O(n), \, Poly\, *:O(n^2)$

接下去我們從暴力開始談起。

暴力做法　$O({{n^3}\over 32})$

第一個需要解決的問題是：$f(g(x))$。那么我們只需要對$g(x)$求$k$次冪（也即最暴力地k次自乘），再將這些結果相加得到多項式$f(g(x))$。至于取模的過程，則可以在每次multiply的時候順帶模干凈，這樣最終相加得到的結果就是在模多項式意義下的答案。

void mod(poly &a, int pos)　　　　//pos是a的度數
{
    for (int i=pos; i>=p; i--)
        if (a[i]) a ^= c<<(i-p), a[i] = 0;
}
void mult(poly a, poly b, poly &ret)　　　　//ret=a*b
{
    ret.reset();
    for (int i=0; i<=p; i++)
        if (a[i]) ret ^= b<<i;　　//這里就是模擬n^2多項式乘法的過程
    mod(ret, p<<1);
}

總的代碼：

#include<bits/stdc++.h>
const int maxn = 8035;
typedef std::bitset<maxn> poly;

int n,m,p;
poly a,b,c,tmp,cnt;

void input(poly &a, int &n)
{
    scanf("%d",&n);
    for (int i=0, x; i<=n; i++)
    {
        scanf("%d",&x);
        if (x) a.set(i);
    }
}
void mod(poly &a, int pos)
{
    for (int i=pos; i>=p; i--)
        if (a[i]) a ^= c<<(i-p), a[i] = 0;
}
void mult(poly a, poly b, poly &ret)
{
    ret.reset();
    for (int i=0; i<=p; i++)
        if (a[i]) ret ^= b<<i;
    mod(ret, p<<1);
}
int main()
{
    input(a, n), input(b, m), input(c, p);
    tmp[0] = 1, mod(b, m);
    for (int i=0; i<=n; i++)
    {
        if (a[i]) cnt ^= tmp;
        mult(tmp, b, tmp);　　　　//復雜度n^3在這里
    }
    while (p>=0&&!cnt[p]) --p;
    if (p==-1) puts("0 0");
    else{
        printf("%d",p);
        for (int i=0; i<=p; i++)
            printf(" %d",cnt[i]?1:0);
    }
    return 0;
} 

對系數按10位分塊　$O({{n^3}\over 320})$

參見法老博客：[BITSET 分塊] BZOJ5087. polycomp

注：md[t]并不一定要等于0.這里的取模多項式最高位對計算無影響。

容易發現這種做法的復雜度的階仍然是$n^3$.

對$i=a\sqrt k+b$分塊　$O({{n^2\sqrt n}\over 32})$

233