CTSC 2014 随机数 题解
Scarlet_Hypoc
·
·
题解
题解（废话）
这部分作者神志不清的自说自话大家跳过也无妨的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) 中取值。
简单概括
$\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）。
---
那么这样才算是真的做完啦，代码如下：
```cpp
#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;
}
```