自动搬运

查看原文

来自洛谷，原作者为

	Scarlet_Hypoc ...

搬运于2025-08-24 22:15:16，当前版本为作者最后更新于2021-03-31 10:57:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解（废话）

这部分作者神志不清的自说自话大家跳过也无妨的qwq……

这题做的人少的吓人，我也是听了f321dd巨佬讲课才来尝试做一做，个人觉得还是很有趣的题qwq。

话说这题网上题解似乎只有不超过 $3$ 篇啊……像我这种菜鸡水平的人没什么题解看就很难受，所以千辛万苦过了这题来记录一下。

话说做这题的时候还有一个有趣的事儿，就是中途用瞪眼法已经再也瞪不出bug的时候，我去偷了一手Picks爷的代码对拍，结果拍出来四五个，手算之后发现错的全是Picks爷的代码qaq，定睛一看发现他在多项式快速幂的时候没有取模，如果 $k$ 比 $n$ 大一些他就裂开了……

顺便给大家送一组第二问的样例吧（应该是满足题目要求的……）：

input :
5
1 0 1 0 0
1 0 0 0 0
1
2
1 0 1 0 1
output :
00011

真·题解

第一问

这个递推式是让 $M_0$ 反复乘 $2$，大于等于 $2^m$ 的时候就减去 $2^m$ 并异或一个 $x$。众所周知异或可以看成二进制下不进位的加 / 减法，那么大于等于 $2^m$ 时的操作完全可以看成二进制下不进位的取模啊！

记题目中给出的数 $x$ 为多项式 $p(x)$，令 $G(x)=p(x)+x^m$，那么在模 $G(x)$ 意义下求一个 $M_0\times x^k$ 就是答案，注意为每一位的运算是模 $2$ 意义下的不进位加减法，多项式运算本身是不进位的，所以注意模 $2$ 就好。

时间复杂度 $O(m\log m\log k)$。

第二问

第二问就比较奇怪，给出 $M_{k\cdot 2^l}$，求 $M_k$。

注意到题目给了个也很奇怪的性质：$x$ 是好的——在序列长度趋于无穷的时候，近似等概率地在 $\mathbb Z^+\cap (0,2^m)$ 中取值。

简单概括

$M_0$ ~ $M_{\infty}$ 形成了一个大小为 $2^m-1$ 的多项式乘法群 $F$（并且这个多项式乘法是在模 $G(x)$ 意义下的）。

$\forall f(x)\in F$，显然 $f(x)^0$ 是 $F$ 的单位元，剩下 $2^m-2$ 个元素一定可以表示为 $f(x)^i$，那么 $f(x)^{2^m-1}=f(x)^0$，于是有 $f(x)^{2^m}=f(x)$。

---

人话翻译 （可能略烦，略长……具有一定前置知识并且看懂了简单概括的就可以跳过了……）

定义初值为 $A_0\in (0,2^m)$，递推式为 $A_i=A_{i-1}\times B \pmod {G(x)} (B\in (0,2^m))$ 的序列为 $(A_0,B)$ 的生成序列。

显然 $M$ 序列存在循环节，上述性质相当于告诉我们循环节大小为 $2^m-1$，令 $F$ 为一个循环节内所有元素的集合。显然存在一个元素在原来的数值上为 $2$，在多项式表示下就是 $x^1$，那么 $M$ 相当于是 $(M_0,x^1)$ 的生成序列。

实际上不难发现任意生成序列的循环节都是 $2^m-1$，考虑 $F$ 内任意一个元素 $f(x)$，对于生成序列 $(1,f(x))$，其第 $2^m$ 项为 $f(x)$，即 $1\times f(x)^{2^m}=f(x)$，我们得到了和上面一样的结论。

---

有了这个结论，剩下的事情就很简单了。我们现在拥有 $M_{k\cdot2^l}=M_0\times x^{k\cdot 2^l}$，我们需要求 $M_k$，显然有：

$$M_k=M_0\times x^k\times x^{2^m}=M_0\times (x^{k\cdot2^l})^{2^{m-l}}=M_0\times \left(\frac {M_{k\cdot 2^l}} {M_0}\right)^{2^{m-l}} $$

好啦，这就做完啦！诶，慢着……我要怎么求模 $G(x)$ 意义下 $M_0$ 的逆啊？！

啊事实上这个东西也是可以做的，你需要往扩展欧几里得算法上套多项式板子，具体参见Picks巨佬的代码……但是不要怕！上面的性质不仅可以放到 $x$ 上用，我们也可以放到 $M_0$ 上再用一次！

$$M_0\times \left(\frac {M_{k\cdot 2^l}} {M_0}\right)^{2^{m-l}}=M_0^{2^m}\times(M_{k\cdot 2^l}M_0^{-1})^{2^{m-l}}=M_{k\cdot 2^l}^{2^{m-l}}\times (M_0^{2^{m-l}})^{2^l-1} $$

这样有了另一种又好看又好写的做法！时间复杂度是 $O(m^2\log m)$，因为每次快速幂是 $\log {2^m}=m$ 的复杂度。

---

啊哈！你以为这就完了？让我们看回第一问。

事实上，你信心满满的冲完第一问的代码后，交上去一看，恭喜你只有 $30$ 分，除去第二问的 $40$ 分，剩下你还会因为TLE丢掉 $30$ 分。

好，T就T，卡常就是了，然后你千辛万苦卡一通常后也许会少几个TLE，但是大概率那几个TLE会变成WA（笑

下面有两个奇技淫巧，大概能帮你解决这些乱七八糟的问题。

为什么第一问会WA？

这个的原因大概率是因为你没有处理好系数要对2取模这件事，每次将两个多项式卷积完后系数模 $2$ 了吗？多项式除法的时候商和余数的系数模 $2$ 了吗？这是需要检查的。

检查后会发现一个有趣的事情：如果你在多项式乘法的时候，系数都是正数，那么乘完之后直接系数模 $2$ 即可。但是如果出现了负数呢？负数在ntt模数下会变成正数，与此同时其奇偶性会发生改变，直接模 $2$ 会得到相反的结果。然而，我也没有很好的判断一个系数是整数还是负数的办法。

注意到，会出现负数的地方之后多项式求逆的部分，众所周知多项式求逆依赖于这个公式：$G=G_0(2-FG_0)$，然而，由于需要对系数模 $2$，我们却恰好可以利用这一点来规避遇到负数的问题：式子可以写成 $G=2G_0-FG_0^2$，模 $2$ 后 $2G_0$ 直接消掉，然后取负不影响奇偶性，即取负后模 $2$ 和直接模 $2$ 的结果相同，于是式子可以变成 $G=FG_0^2$，负数不见了！

为什么第一问会TLE？

这不是出题人的问题？复杂度mlog2m出1e6的范围，这还是多项式运算的log，这出题人脑子是不是有问题啊（

第一问其实有一个大优化，做快速幂的时候，如果多项式次数小于 $n$，那么就不需要取模，因为取了也不发生变化。那么复杂度变成 $O(m\log m(\log k-\log m))$，由于这里 $m,k$ 同阶，所以这是个大优化。加上之后应该是能无压力通过的（我最慢的点 $3.5$s）。

---

那么这样才算是真的做完啦，代码如下：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 3000010
#define mod 998244353
#define bin(x) (1<<(x))
#define MS(f,x) memset(f,0,4<<(x))
#define CP(f,g,x) memcpy(f,g,(x)<<2)

#define cn getchar
template<class TY>void read(TY &x){
	x=0;int f1=1;char ch=cn();
	while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();}
	while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1;
}
int n,F[maxn],G[maxn];
int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
int w[maxn],inv[maxn];void prep(int lg){int N=bin(lg);
	inv[1]=1;for(int i=2;i<=N;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1,wn;i<N;i<<=1){
		w[i]=1;wn=ksm(3,(mod-1)/(i<<1));
		for(int j=1;j<i;j++)w[i+j]=1ll*w[i+j-1]*wn%mod;
	}
}
void reduce(int &x){x+=x>>31&mod;}
void ntt(int *f,int lg,int type=0){
	int limit=bin(lg);if(type)reverse(f+1,f+limit);
	for(int i=0,j=0,k;i<limit;i++){if(i<j)swap(f[i],f[j]);k=limit>>1;while((j^=k)<k)k>>=1;}
	for(int mid=1,t;mid<limit;mid<<=1)for(int j=0;j<limit;j+=(mid<<1))for(int i=0;i<mid;i++)
	{t=1ll*f[j|i|mid]*w[mid|i]%mod;reduce(f[j|i|mid]=f[j|i]-t);reduce(f[j|i]+=t-mod);}
	if(type)for(int i=0;i<limit;i++)f[i]=1ll*f[i]*inv[limit]%mod;
}
int A[maxn],B[maxn],C[maxn],D[maxn],E[maxn],Q[maxn],R[maxn];
void NTT(int *f,int *g,int ln,int Mul=2){
	int lg=ceil(log2(ln*Mul));ntt(f,lg);ntt(g,lg);
	for(int i=0;i<bin(lg);i++)f[i]=1ll*f[i]*g[i]%mod;ntt(f,lg,1);
	for(int i=0;i<bin(lg);i++)f[i]&=1;
}
void getsqr(int *f,int ln){
	int lg=ceil(log2(2*ln-1));
	ntt(f,lg);for(int i=0;i<bin(lg);i++)f[i]=1ll*f[i]*f[i]%mod;
	ntt(f,lg,1);for(int i=0;i<bin(lg);i++)f[i]&=1;
}
void getinv(int *f,int *g,int ln){
	if(ln==1){g[0]=ksm(f[0],mod-2);return;}getinv(f,g,ln+1>>1);
	int lg=ceil(log2(ln<<1));MS(A,lg);MS(B,lg);CP(A,f,ln);CP(B,g,ln);
	getsqr(B,ln+1>>1);NTT(B,A,ln);CP(g,B,ln);
}
void getrev(int *f,int *g,int ln){for(int i=0;i<=ln;i++)g[i]=f[ln-i];}
void getdiv(int *f,int *g,int *q,int ln1,int ln2){
	int lg=ceil(log2(ln1+1));MS(C,lg);MS(D,lg);MS(E,lg);
	getrev(f,C,ln1);getrev(g,D,ln2);for(int i=ln1-ln2+1;i<=ln1;i++)C[i]=D[i]=0;
	getinv(D,E,ln1-ln2+1);for(int i=0;i<=ln1-ln2;i++)E[i]&=1;
	NTT(C,E,ln1-ln2+1);getrev(C,q,ln1-ln2);
}
void getmod(int *f,int *g,int *q,int *r,int ln1,int ln2){
	int lg=ceil(log2(ln1+1));MS(C,lg);MS(D,lg);CP(C,g,ln2+1);CP(D,q,ln1-ln2+1);
	NTT(C,D,ln1+1,1);for(int i=0;i<ln2;i++)r[i]=f[i]^C[i];
}
void Modto(int *f,int *g,int ln1,int ln2){
	for(int i=0;i<=ln1;i++)f[i]&=1;
	getdiv(f,g,Q,ln1,ln2);getmod(f,g,Q,R,ln1,ln2);
	for(int i=0;i<=ln1;i++)f[i]=(i<ln2?R[i]:0);
}
int Base[maxn],A1[maxn];
void solve1(){
	int ts;read(ts);
	int lg=ceil(log2(n<<1));Base[1]=A1[0]=1;
	int c1=0,c2=1;
	for(;ts;ts>>=1){
		if(ts&1){
			if((c1+=c2)<n)A1[c1-c2]=0,A1[c1]=1;
			else NTT(A1,Base,n),ntt(Base,lg,1),Modto(A1,G,2*n-1,n);
		}
		if((c2<<=1)<n)Base[c2>>1]=0,Base[c2]=1;
		else getsqr(Base,n),Modto(Base,G,2*n-1,n);
	}
	NTT(F,A1,n);Modto(F,G,2*n-1,n);
	for(int i=0;i<n;i++)putchar(F[i]?'1':'0');
}
int Mk[maxn];
void ksm1(int *f,int ts){
	for(int i=1;i<=ts;i++)
		getsqr(f,n),Modto(f,G,2*n-1,n);
}
void ksm2(int *f,int ts){
	int lg=ceil(log2(n<<1));
	CP(A1,f,n);ntt(f,lg);
	for(int i=1;i<ts;i++){
		for(int i=0;i<bin(lg);i++)f[i]=1ll*f[i]*f[i]%mod;
		ntt(f,lg,1);Modto(f,G,2*n-1,n);
		ntt(f,lg);ntt(A1,lg);for(int i=0;i<bin(lg);i++)A1[i]=1ll*A1[i]*f[i]%mod;
		ntt(A1,lg,1);Modto(A1,G,2*n-1,n);
	}
	for(int i=0;i<bin(lg);i++)f[i]=(i<n?A1[i]:0);
}
void solve2(){
	int l;read(l);
	for(int i=0;i<n;i++)read(Mk[i]);
	ksm1(Mk,n-l);ksm1(F,n-l);ksm2(F,l);
	NTT(F,Mk,n);Modto(F,G,2*n-1,n);
	for(int i=0;i<n;i++)putchar(F[i]?'1':'0');
}

int main()
{
	read(n);prep(ceil(log2(n+1<<1)));
	for(int i=0;i<n;i++)read(G[i]);G[n]=1;
	for(int i=0;i<n;i++)read(F[i]);
	int type;read(type);
	if(type==0)solve1();
	else solve2();
	return 0;
}