自动搬运

查看原文

来自洛谷，原作者为

	约瑟夫用脑玩 AFO

搬运于2025-08-24 21:51:38，当前版本为作者最后更新于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;
}