P3689 [ZJOI2017]多项式

约瑟夫用脑玩 · 2021-06-19 16:13:09 · 题解

既然都决定写了，为了以后的自己读得懂，还是写一篇详细的题解吧。

有点长，分个层。

快速幂

通读全题，第一个注意到的是大的不正常的 m，而题目要求的是多项式的 m 次方，那么快速幂的思想跑不了。

系数扩倍

接着可以注意到是在模 2 意义下进行，考虑快速幂的过程发现 f(x)^k \Rightarrow f(x)^{2k} 就是系数的次数扩倍。

为什么？把 f(x)^k 写开，即 f(x)^k=\sum_i c_i x^i，则 f(x)^{2k}=(\sum_i c_i x^i)\cdot(\sum_i c_i x^i)=\sum_ic_i^2x^{2i}+\sum_i\sum_{j\not=i}c_ic_jx^{i+j}

由于有模 2，首先有 c_i^2=c_i，接着有 \sum_i\sum_{j\not=i}c_ic_jx^{i+j}=2\sum_i\sum_{j>i}c_ic_jx^{i+j}=0。

故 f(x)^{2k}=\sum_ic_ix^{2i}

转移状态

然后我就不会了，但是可以发现 n,K 小的不对劲。

为了后文方便，令 K\rightarrow K-1,t=\max(n,K)，即后文的 K 表示询问串看作多项式的最高次数为 K。

显然，我们可以发现 f(x)^k 的相邻 t 项系数只有 2^t 种情况，记 F(st) 表示当前相邻系数状态为 st 的个数，发现是可以轻松转移快速幂的。

更重要的是，我们发现这个东西对最后求答案很有帮助，但我们还不会转移。

快速幂转移

还是为了后文方便，对于开头不到 t 项的相邻 r<t 项，我们在其前面补 t-r 个 0 作为状态，你可以看作负数项为 0，并考虑了部分负数项。

考虑某一段状态为 st，扩倍后一定唯一确定了一段长为 2t 的状态 st'，(不严谨的表示一下)即 st_{k,k+t}=\sum_{i=k}^{k+t}c_ix^i，则 st'_ {2k,2(k+t)}=\sum_{i=k}^{k+t}c_{i}x^{2i}

但如果我们将 st' 里面的 t 个(相邻 t 项系数)状态全部计数到扩倍后的 F' 里面的话是会重复计数的。

如果你不想自己 yy 一个办法去重然后调边界致死的话，可以想办法将其一一对应进行计数。

我们对应取最后两个状态，即对于 st_{k,k+t} 我们只对应计数 st'_ {2k+t-1,2k+2t-1},st'_ {2k+t,2k+2t}，可以发现这样就巧妙地转移了扩倍。

总的来看也是正确的，设 f(x)^k 有 y 项，有 y 个状态，那么 f(x)^{2k} 有 2y 项，那么就应该有 2y 个状态。

然而还有个严重的问题就是快速幂不止乘 2，还可能加 1。

如果我们先转移了 F' 再乘 1 转移 F'' 的话是有问题的，因为一个状态不被 F' 一种状态一一对应了，还与这种状态相邻的 t 个状态有关。

嗯，t 个？我们发现由 F 转移时刚好就对应了相邻 2t 个位置，即相邻 t 个状态。

于是我们直接在这里确定乘上 f(x) 后得到对应的长为 2t+n 的状态，但这里确定的 t+n 个状态也有巧妙的重叠。

这里我们采用的方法是取中间两个状态，即 st_{k,k+t} 对应 st''_ {2k+n,2(k+t)+n}，取 st''_ {2k+t-1,2k+2t-1},st''_ {2k+t,2k+2t} ，和前面一样欸！(((

总的来看应该有 2y+n 项，即 2y+n 个状态，那么最前面会多出 n 种状态没有计数进去，于是我们可以记录最前面的 T 位，然后暴力将前面 n 种状态加进去即可。

同时最前面的这 T 位也有其他的用处，马上就要用到。而且我并不知道 T 取多少没问题，毕竟有的题解里说取个几十几百位都不是瓶颈(我：@^#%@!%#)，于是我随便地采取了 T=2t+1。

后缀和

转移就这样愉快的结束了，但你可能发现题目给的 L,R 用都还没用过。

由于快速幂转移过程中我们将前面 T 位带着走了的，所以我们可以轻易地掐掉前面的一部分。

用题目中的形式表达一下，f(x)^m 就是 s，那么其后缀就是 s\left[ k,N \right] ,N 是总长，k 就是后缀开始的位置。

于是我们可以得到 s\left[ k,N \right] 的 F 数组，具体就是每次扩倍或扩倍加一时用前 T 位暴力掐掉一段掐到 k 那个位置就行。

统计答案

显然地，我们用 s\left[ L,N \right] 的 F 减去 s\left[ R-K+1,N \right] 的就是答案。

统计的话由于 K 可能比 t 小，那么我们在前面补上任意一种前缀统计。

注意补东西都是在前面补，类比前面补 0，但这里不是补 0，而是补任意一种前缀。

以上。

哦不对还有我难看的代码，但好歹还有点注释，为了看得懂我多截了一点：

const int Mx=100;
const int M=1<<19;
int n,m,mx,mxx,trs[2][2][M];
LL T,L,R,stf,stg,alf,alg;
int tt,flg[Mx+5];
LL len[Mx+5],F[2][M];
inline LL Ask(LL v)
{
    int i,t,f,fl;
    LL k=T,l,dl,sm;
    LLL prf,prg;
//前 T 位偷懒用 __int128 存的
    for(;k^1;k>>=1)
    {
        flg[++tt]=k&1;
        len[tt]=tt-1?(len[tt-1]+1)>>1:v;
//要求到 [v,N] 的 F 每次要的长度
    }
    for(i=0;i<=n;F[0][(stf<<(mx-(i++)))&alf]++);
    for(t=1,f=0,l=n,prf=stf<<(mx+1);tt;tt--,t^=1,f^=1)
    {
        fl=flg[tt];
        for(i=0;i<=alf;i++)
        {
            if((k=F[f][i]))
            {
                F[t][trs[fl][0][i]]+=k;F[t][trs[fl][1][i]]+=k;
                F[f][i]=0;
//用预处理好的直接转移
            }
        }
        for(i=prg=0;i<=mxx;i++)
        {
            prg|=((prf>>i)&1)<<(i<<1);
        }
//暴力转移前 T 位
        dl=Max(0ll,(l=(l<<1)+(fl?mx:0))-len[tt]);
//该掐多长
        if(fl)
        {
            for(i=prf=0;i<=mx;i++)
            {
                if((stf>>i)&1)
                {
                    prf^=prg<<i;
                }
            }
            if(dl<mx)for(i=dl;i<mx;F[t][(prf>>(mxx+mx+mx-(i++)+1))&alf]++);
            if(mx<dl)for(i=mx;i<dl;F[t][(prf>>(mxx+mx+mx-(i++)+1))&alf]--);
//掐和加上 n 种状态二合二(我毒瘤)
            prf=(prf>>(mxx+mx-dl))&alg;
        }
        else
        {
            for(i=0;i<dl;F[t][(prg>>(mxx+mx-(i++)+1))&alf]--);
//掐
            prf=(prg>>(mxx-dl))&alg;
        }
        l-=dl;
    }
    for(i=sm=0;i<(1<<(mx-m));sm+=F[f][(i++)|stg]);
//补前缀统计
    for(i=0;i<=alf;F[f][i++]=0);
    return sm;
}
inline int gt()
{
    char ch;
    for(ch=gc();ch^48&&ch^49;ch=gc());
    return ch^48;
}
int TT;
signed main()
{
    #ifndef ONLINE_JUDGE
//  freopen("poly1.in","r",stdin);
    freopen("_.in","r",stdin);
//  freopen("_.out","w",stdout);
    #endif
    int i,j;
    LL k,kk;
    for(TT=read();TT;TT--)
    {
        n=read();read(T);m=read()-1;read(L);read(R);mx=Max(n,m);mxx=(mx<<1)+1;
//题解对应代码 n->n m->T K->m t->mx T->mxx
        for(i=stf=0;i<=n;i++)
        {
            stf|=gt()<<(mx-i);
        }
        for(i=stg=0;i<=m;i++)
        {
            stg|=gt()<<(mx-i);
        }
        alf=(1<<(mx+1))-1;alg=(1ll<<(mxx+1))-1;
        for(i=0;i<=alf;i++)
        {
            for(j=k=0;j<=mx;j++)
            {
                k|=((i>>j)&1ll)<<(j<<1);
            }
            trs[0][0][i]=k>>mx;trs[0][1][i]=(k>>(mx-1))&alf;
//扩倍转移的预处理
            for(j=kk=0;j<=mx;j++)
            {
                if((stf>>j)&1)
                {
                    kk^=k<<j;
                }
            }
            trs[1][0][i]=(kk>>mx)&alf;trs[1][1][i]=(kk>>(mx-1))&alf;
//扩倍加一转移的预处理
        writenum(R-L+1<m?0:Ask(n*T+1-L)-Ask(n*T+1-(R-m+1)),10);
//毒瘤
    }
    return output;
}