题目概述

给出 $f(x),g(x),h(x)$ ，求 $f(g(x))\ mod\ h(x)$ ，系数在 $mod\ 2$ 意义下。

解题报告

直接就有一个 $O(n^2log_2n)$ 的多项式取模做法……没写过，不知道会不会被卡常。

不过由于是 $mod\ 2$ 意义下的所以我们可以bitset乱搞QAQ。

用朴素 $O(n^2)$ 取模是 $O(n^3)$ 的，用bitset优化一下变成 $O({n^3\over\omega})$ 。

但这样还是不行，我们再压位……对 $f(x)$ 每 $12$ 位分别做，你就得到了 $O({n^3\over12\omega})$ 的优秀解法（雾）。

示例程序

#include<cstdio>
#include<bitset>
using namespace std;
const int maxn=4000;
typedef bitset<(maxn<<1)+5> data;

int n,m,K,pos[1<<12];data f,g,MOD,BA[15],sum[1<<12],pw,tem,ans;

inline void Mod(data &a) {for (int i=K<<1;i>=K;i--) if (a[i]) a^=MOD<<(i-K),a[i]=0;}
inline void Mul(data a,data b,data &c) {c=0;for (int i=0;i<K;i++) if (a[i]) c^=b<<i;Mod(c);}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=0,x;i<=n;i++) scanf("%d",&x),f[i]=x;
    scanf("%d",&m);for (int i=0,x;i<=m;i++) scanf("%d",&x),g[i]=x;
    scanf("%d",&K);for (int i=0,x;i<=K;i++) scanf("%d",&x),MOD[i]=x;
    MOD[K]=0;for (int i=m;i>=K;i--) if (g[i]) g^=MOD<<(i-K),g[i]=0;
    BA[0]=1;for (int i=1;i<=12;i++) Mul(BA[i-1],g,BA[i]);sum[1]=pw=1;
    for (int s=2;s<(1<<12);s++) pos[s]=pos[s>>1]+1,sum[s]=sum[s^(1<<pos[s])]^BA[pos[s]];
    for (int i=0,S=0;i<=n;i+=12,S=0){
        for (int j=i;j<i+12&&j<=n;j++) if (f[j]) S|=1<<j-i;
        Mul(sum[S],pw,tem);ans^=tem;Mul(pw,BA[12],pw);
    }int len=K;while (!ans[len]) len--;printf("%d",len);
    for (int i=0;i<=len;i++) putchar(' '),putchar(ans[i]+48);puts("");return 0;
}