M_sea 的博客 - 咕咕
type: channel
link: https://m-sea-blog.com/category/咕咕
items: IOI2021 集训队作业乱做
items: 多项式全家桶重新学习笔记

IOI2021 集训队作业乱做
type: item
date: 2020-10-28T03:20:00+00:00
description: WF 2014 Baggage 设 $(BA)$ 表示 $BABA\cdots BA$，$(AB)$ 表示 $AAA\cdots ABBB\cdots B$。 首先爆搜一下 $n=3,4,5,6,7$，可以发现最短的构造长度为 $n$，同时从 $\_\_(BA)$ 变成了 $(AB)\_\_$。 考虑 $n\geq 8$ 的情况。我们可以做如下操作： $$ \begin{matrix} \_\_BABA(BA)BABA\\ ABBABA(BA)B\_\_A\\ ABBA\_\_(BA)BBAA \end{matrix} $$ 中间那个 $\_\_(BA)$ 可以直接递归处理，处理完后再做如下操作： $$ \begin{matrix} ABBA(AB)\_\_BBAA\\ A\_\_A(AB)BBBBAA\\ AAAA(AB)BBBB\_\_ \end{matrix} $$ 这样子整个序列就变成了 $(AB)$，长度为 $n$。可以证明这是最短的。 Maze Reduction 这种题看着就是要对每个点求一个哈希值，所以关键在于如何设计哈希函数。 设 $h_{i,j,k}$ 表示从 $j$ 的第 $k$ 扇门进去走 $i$ 步的哈希值。假设从 $j$ 的第 $k$ 扇门走进去是 $v$，那么可以从 $j$ 开始绕着 $v$ 走一圈，把所有的 $h_{i-1,v,x}$ 哈希起来表示 $h_{i,j,k}$。特别的，当 $i=0$ 时可以用 $j$ 的度数表示。 然后对每个房间 $i$ 求 $h_{n,i,j}$ 的最小表示，即可当做其哈希值。因为数据范围很小所以可以暴力求，时间复杂度 $\mathcal{O}(n^4)$。 Metal Processing Plant 不妨设 $D(A) \leq D(B)$。 从小到大枚举 $D(A)$，双指针从大到小枚举 $D(B)$，那么只需要考虑如何判断是否合法。 因为每个点要么在 $A$ 中要么 $B$ 中，因此考虑 2-SAT。对于边权在 $(D(A), D(B)]$ 中的边，其两端点需要满足不同时在 $A$ 中；对于边权 $>D(B)$ 的边，其两端点需要满足不同时在一个集合中。 使用压位 Kosaraju 算法找出强连通分量判断即可，时间复杂度 $\mathcal{O}(\frac{n^4}{\omega})$。 Pachinko 设 $f_{i, j}$ 为能够到达 $(i, j)$ 的概率，可以列出一个 $n\times m$ 元方程组。然而直接解时空都无法承受。 不妨把所有格子按照从上到下、从左往右的顺序编号，这样子矩阵是一个长度为 $m$ 的带状矩阵。 因从我们只需要对每行保存 $2m$ 个值，消元时也只需要往下消 $m$ 行再回代就可以了。 Sensor Network 直接随机贪心求最大团是可以过的。具体就是用 bitset 维护已经加入的点，然后随机一个加点排列，能加就加即可。 正解是枚举两个点 $A,B$，则其它点必定在分别以 $A,B$ 为圆心、半径为 $D$ 的两个圆的交内，我们要求最大团。转化成补图的最大独立集，可以发现补图中所有边的端点都在 $AB$ 的两侧，因此补图为二分图，从而很好求最大独立集。 Surveillance 把所有区间按左端点排序，则选了每个区间后下一个必选的区间可以直接双指针预处理出来。 然后预处理倍增数组，枚举起点，然后直接倍增跳一圈即可。 WF 2015 Evolution in Parallel 设 $A\subseteq B$ 表示 $A$ 是 $B$ 的子序列。 首先至少要有 $s_i\subseteq U$，判掉后 $U$ 就没用了。 考虑一条链上的串长度显然是不降的，于是我们把所有串按长度从小到大排序后依次加入，并维护两条链。我们称一个串 $S$ 能接在一条链的末端当且仅当链尾串 $T$ 满足 $T\subseteq S$。 如果当前串不能接在任意一条链的末端，则无解； 如果当前串只能接在一条链的末端，就接上去； 如果当前串可以接在两条链的末端，发现不好处理。我们再维护一条待选链，那么 如果当前串可以接在待选链末端，那么就接上去； 否则一定是这个串和待选链分别接在两条链的末端，随便选择一种接法即可。 这样子总共只需要询问 $\mathcal{O}(n)$ 次 $A\subseteq B$ 是否成立，复杂度 $\mathcal{O}(n^2)$。 Qanat 可以证明，竖井一定会垂直往上运，底部一定会走左右两个竖井中近的那个往上运。 考虑确定最右边的竖井的位置，这样子加上最右边竖井右边部分的代价后即可转化为一个子问题，而这个子问题对应的三角形与原三角形是相似的，所以我们可以只求出原三角形中放 $n-1$ 个竖井的代价，乘上比…

多项式全家桶重新学习笔记
type: item
date: 2020-10-20T12:15:00+00:00
description: 为了方便，下文中的多项式长度和 $n$ 均为 $2$ 的幂（多项式除法、三角函数和反三角函数除外），模数均为 $998244353$。 下面所有函数中（除了 NTT_init）传进去的 $n,m$ 都是多项式项数而不是次数。 多项式乘法 这是前置知识，如果不会建议「点开洛谷题面单击右边蓝色按钮题解」。 int r[N]; void NTT(int* A,int n,int op) { for (int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]); for (int i=1;i<n;i<<=1) { int rot=qpow(op==1?3:332748118,(mod-1)/(i<<1)); for (int j=0;j<n;j+=i<<1) for (int k=0,w=1;k<i;++k,w=1ll*w*rot%mod) { int x=A[j+k],y=1ll*w*A[j+k+i]%mod; A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod; } } if (op==-1) { int inv=qpow(n,mod-2); for (int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod; } } int NTT_init(int n) { int lim=1,l=-1; for (;lim<n;lim<<=1,++l); for (int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<l); return lim; } 多项式求导 $$ (x^a)'=ax^{a-1} $$ void getderi(int* F,int* G,int n) { for (int i=1;i<n;++i) G[i-1]=1ll*F[i]*i%mod; G[n-1]=0; } 多项式不定积分 $$ \int x^a\mathrm{d}x=\frac{x^{a+1}}{a+1} $$ void getinte(int* F,int* G,int n) { for (int i=1;i<n;++i) G[i]=1ll*F[i-1]*qpow(i,mod-2)%mod; G[0]=0; } 多项式牛顿迭代 已知 $G(x)$，求 $F(x)$ 满足 $G(F(x))\equiv 0\pmod{x^n}$。 假设我们已经求出了 $F_o(x)$ 满足 $G(F_0(x))\equiv 0\pmod{x^{\frac{n}{2}}}$，将 $G(x)$ 在 $F_0(x)$ 处泰勒展开得到 $$ G(F(x))=\sum_{i=0}^{+\infty}\frac{G^{(i)}(F_0(x))}{i!}(F(x)-F_0(x))^i $$ 可以发现 $i\geq 2$ 时在模 $x^n$ 意义下都为 $0$，所以 $$ G(F(x))\equiv G(F_0(x))+G'(F_0(x))(F(x)-F_0(x))\pmod{x^n} $$ 又 $G(F(x))=0$，化简得到 $$ F(x)=F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}\pmod{x^n} $$ 多项式求逆 已知 $F(x)$，求 $G(x)$ 满足 $F(x)G(x)\equiv 1\pmod{x^n}$。 Luogu 假设我们已经求出了 $G_0(x)$ 满足 $F(x)G_0(x)\equiv 1\pmod{x^{\frac{n}{2}}}$，那么 $$ F(x)(G(x)-G_0(x))\equiv 0\pmod{x^\frac{n}{2}} $$ 所以 $$ G(x)-G_0(x)\equiv 0\pmod{x^{\frac{n}{2}}} $$ 平方得到 $$ G(x)^2-2G(x)G_0(x)+G_0(x)^2\equiv 0\pmod{x^n} $$ 乘上 $F(x)$ 即可得到 $$ G(x)\equiv 2G_0(x)-F(x)G_0(x)^2\pmod{x^n} $$ 这样就可以由 $G_0(x)$求出 $G(x)$ 了。 void getinv(int* F,int* G,int n) { static int A[N],B[N]; if (n==1) { G[0]=qpow(F[0],mod-2); return; } getinv(F,G,n>>1); for (int i=0;i<n;++i) A[i]=F[i],B[i]=G[i]; int lim=NTT_init(n<<1); NTT(A,lim,1),NTT(B,lim,1); for (int i=0;i<lim;++i) A[i]=1…