BZOJ2532 | CERC2010 Casting Spells

首先跑马拉车。

然后对于每个位置 i 我们求出他的回文对称半径 r_i 。比如说图上假设 i 是回文子串的中心(如果是偶数长度那就是中心的右侧),然后红色位置是子串的右末端,那么 r_i 就是:

然后有了 r_i 之后我们考虑合法的串长什么样子:

于是我们的任务就是找到满足以下条件的 j

  •  j+r_j \geqslant i
  •  j \geqslant i-\frac{r_i}{2}

然后就可以了。那么这里有一个 O(n \log n) 的搞法:从左到右枚举 i ,并同时维护两个集合:一个是当前所有满足条件 [1] 的 j 的位置集合,这个集合以 r_j+j 排序,并记录每个 r_j+j 对应的 j

另一个集合维护所有当前的合法位置 j ,并按照 j 排序。

每次扫到一个 i 只需先清空位置集合所有 r_j+j < ir_j+j 和合法集合对应的 j

然后求合法集合里 i - \frac{r_i}{2} 的后继即可。

 

关于原根判定的若干证明

其实这个证法是从 zhx 的讲稿中看+结合我自己 yy 出来的……其实这个做法的来源是拉格朗日定理,改天学了之后说不定我会有什么新的认识……

引理1 \,\,\,\, 如果 G = <a> ,称 G 为循环群,若 G 为有限循环群,可知当 |G| = \infty 时, G 与整数加群 \mathbb{Z} 同构,当 |G| \ne \infty 时, ord(a)=|G|

设在质数 \text{mod } p 意义下进行加法和乘法, 那么乘法群 G=\{1,2, \cdots ,p-1 \} 是一个循环群。设 aG 的生成元 (<a>=G),易知 ord(a) = |G| = \varphi(p)

引理2 \,\,\,\, 由欧拉定理可知 \forall a \in G \,,\,ord(a)|\varphi(p)

引理3 \,\,\,\,k=ord(a) \,\,\,(a \in G) ,则 a^k=e , a^{k+i}=a^i

引理4 \,\,\,\, 设原根为 a ,对于\forall 1\leqslant i \leqslant p-1 , \exists x >0 \text{ s.t. } a^x=i \,\, (\text{ mod } p)

引理5 \,\,\,\, 设原根为 a , 仅有 a^{t\varphi(p)}=e ,其中 t \in \mathbb{N}_+

原根判断:a 为原根的充要条件是:对于所有 p 的质因子 d ,都有 a^{\frac{\varphi(p)}{d}} \ne 1

证明:

ord(a)=k

k=\varphi(p) ,则 a 是循环群的生成元,可知 a 为原根,并且 a^{\frac{\varphi(p)}{d}} \ne 1

k < \varphi(p) 时,据引理 2 可知 ord(a)| \varphi(p)

t = \frac{\varphi(p)}{k} , 显然 t>1

dt 任一质因子,显然有 \frac{\varphi(p)}{t}|\frac{\varphi(p)}{d} ,据引理 3 可知 a^{\frac{\varphi(p)}{d}}=1 ,由引理 4 可知 a 显然不是一个原根。

于是胡言乱语地证明完了。

BZOJ2194 快速傅立叶之二

题目让你求这个东西

C_k=\sum_{i=k}^{n-1}{A_iB_{i-k}}

然后假设把 B 全给翻转,那么就是求

C_k=\sum_{i=k}^{n-1}{A_iB_{n-1-i+k}}

然后发现这样把次数凑起来就是与 i 无关的了,成了这样:

D_{n-1+k}=\sum_{i=k}^{n-1}{A_iB_{n-1+k-i}}

那么

\text{let }\lambda =n-1+k

就有

D_{\lambda}=\sum_{i=k}^{n-1}{A_iB_{\lambda -i}}

注意这里长的很像卷积,但是范围是不一样的,尝试把正常卷积形式的其余对应的项写出来,发现都是 0  。。

所以就可以看做卷积了,直接上 FFT 。

然后对应一下

C_0=D_{n-1} C_{n-1}=D_{2n-2}

就做完了。

今天一天尽享多项式!Í dag er「多项式」æfa! 今日は一日「多项式」三昧!

题目是在玩梗。甩你个冰岛语词典自己查吧。这个句子大概这么发音: ɪː tɑɣ ɪrʱ 多项式  ævɑ(肯定不太准)

拉格朗日插值法

插值是什么?

差不多就是以一个函数 f(x) 已知的若干点值代入反解,做出一个特定的函数求对于一个给定的 xf(x) 的近似值的过程。

如果这个特定函数是一个多项式,就称为插值多项式

其中一种方法是 O(n^3) 类的高消。

拉格郎日插值法在干什么?

构造一个对于所有情况都通用的插值基函数,也叫做拉格朗日基本多项式 , 然后可以一步步由它求出插值多项式。

为什么叫做基函数?因为最后的插值多项式是由这个函数线性组合得到的。

这个基函数要干什么?

我们通过 n+1 个点,构造若干个多项式(插值基函数)做线性组合,其中对于第 i 个多项式在 x_i 处的取值为 y_i ,在其他点处取值为 0

把这个多项式叫做 l_i(x) ,那么利用这个性质,最后的插值多项式就可以表示成

l(x) = \sum_{i=0}^n{y_il_i\left( x \right)}

尝试把给定的 n+1个点值代入,发现插值多项式对于所有的点值都成立。于是就偷税地插值完了。

构造

这里利用了一个性质: 0 乘任何数都为 01 乘任何数都不变。

所以按照上文, l_i(x) 就要满足 l_i(x_i)=1 \,,\, \forall j \in [0,n],j \ne i \,,\, l_i(x_j)=0

那么这个构造非常的暴力:

l_i\left( x \right) =\prod_{j=\text{0 }j\ne i}^n{\frac{x-x_j}{x_i-x_j}}

代入各个 x_i 算一下就可以发现满足该性质。

于是我们用 O(n^2) 的时间复杂度求出了拉格日插值多项式。就是这个东西:

l\left( x \right) =\sum_{i=0}^n{\left( y_i\prod_{j=\text{0,}j\ne i}^n{\frac{x-x_j}{x_i-x_j}} \right)}

如果给定的点值是 [0,n] 内的话,那么有方法可以优化到 O(n) 的复杂度。

拉格日插值的线代理解

显然插值基函数是线性无关的,所有的点都可以被线性表出。

所以我们只是构造了一组较好计算的基,使得可以代入 x 来确定坐标 (x,y) 而已。

为什么这样是对的?

我们回到朴素的插值法。这玩意其实就是解线性方程组:

\left( \begin{array}{c} y_1 \\ y_2 \\ \vdots \\ y_n \end{array} \right) =\left( \begin{matrix} 1& x_1& \cdots& x_{1}^{n-1} \\ 1& x_2& \cdots& x_{2}^{n-1} \\ \vdots& \vdots& \ddots& \vdots \\ 1& x_n& \cdots& x_{n}^{n-1} \end{matrix} \right) \left( \begin{array}{c} a_0 \\ a_1 \\ \vdots \\ a_n \end{array} \right)

简写一下就是

\vec{y}=A\vec{a}

如果 |A| \ne 0 那方程组就有唯一解。 观察到 |A| 其实是范德蒙德行列式。

|A|=\prod_{1\leqslant i<j\leqslant n}{\left( x_j-x_i \right)}

如果 x_i 互不相等,那么 |A| \ne 0

所以拉格朗日插值得到的多项式曲线是唯一的。

代码怎么写?

慢速傅里叶变换 (Foolish Fourier Transformation)

FFT 其实就是用分治法加速 DFT 和 IDFT 的过程。

我对大部分博文都不太满意的一点是,思路偏重点不满意。在大多数情况下 (除非实在找不到办法) ,我更偏向的是探究型的讲解而非灌输型的讲解。我觉得有机会去搞懂这里的方法、思路是如何发现的,为什么要使用这样的思路,这一点是最重要的。

不过话说回来, FFT 这类优化思路过于偏门,在 OI 中搞懂了 FFT 是怎么来的并没有助于你解题。

————第 1 节————

先来考虑我们的任务:O(n \log n) 的多项式乘法。

首先第一点是我们发现系数表示法的复杂度下界是 O(n^2) ,因为对于第一个多项式的每一个系数,都要和第二个多项式的 n 个系数做一次乘法。

所谓系数表示法就是我们惯常的形式:

A\left( x \right) =a_0+a_1x+\cdots +a_nx^n=\left( \begin{matrix} a_0& a_1& \cdots& a_n \end{matrix} \right) \left( \begin{array}{c} 1 \\ x \\ \cdots \\ x^n \end{array} \right)

那么我们有一种优化是将多项式由系数表示法转为点值表示法。对于一个 n 次多项式,依据上文,可以用 n+1 个互不相等的点唯一确定:

f\left( x \right) =a_0+a_1x+a_2x^2\,\,\Leftrightarrow \,\,f\left( x \right) =\left\{ \left( x_1,y_1 \right) ,\left( x_2,y_2 \right) ,\left( x_3,y_3 \right) \right\}

然后就可以 O(n) 搞出乘积,如下:

f\left( x \right) =\left\{ \left( x_i,A_i \right) \right\}

g\left( x \right) =\left\{ \left( x_i,B_i \right) \right\}

\left( f\cdot g \right) \left( x \right) =\left\{ \left( x_i,A_iB_i \right) \right\}

————第 2 节————

但是问题是对于这个多项式,求 n 个点值的复杂度还是 O(n^2) 的,非常棘手。

这里我们就开始玩 tricky 的变换了。首先我们假设这个多项式是 2^m-1 次的(这样我们就需要求 2^m 个点值)

n 次多项式为(这里我比较喜欢用矩阵的写法,系数和变量分开,看着清楚)

A\left( x \right) =a_0+a_1x+\cdots +a_nx^n=\left( \begin{matrix} a_0& a_1& \cdots& a_n \end{matrix} \right) \left( \begin{array}{c} 1 \\ x \\ \cdots \\ x^n \end{array} \right)

我们可以按奇偶性分组:

A\left( x \right) =\left( a_0+a_2x^2+a_4x^4 \right) +\left( a_1x+a_3x^3+a_5x^5 \right)

=\left( a_0+a_2x^2+a_4x^4 \right) +x\left( a_1+a_3x^2+a_5x^4 \right)

然后如果我们设

A_0\left( x \right) =\left( \begin{matrix} a_0& a_2& a_4& \cdots \end{matrix} \right) \left( \begin{array}{c} 1 \\ x \\ x^2 \\ \cdots \end{array} \right)

A_1\left( x \right) =\left( \begin{matrix} a_1& a_3& a_5& \cdots \end{matrix} \right) \left( \begin{array}{c} 1 \\ x \\ x^2 \\ \cdots \end{array} \right)

那么我们就有

A\left( x \right) =A_0\left( x^2 \right) +xA_1 \left( x^2 \right)

这挺好的。我们可以递归式地计算每个点值。不过并不会优化什么运算。为什么?

注意到

x_1^2 , x_2^2 , \cdots , x_n^2

仍极有可能组成 n 个不同的数字。对于每个 A(x_i) ,我们都要分别递归计算 A_0(x_i)A_1(x_i) ,这样的复杂度是高于 O(n \log n)  的 O(n^2) ,唉。

那么我们的任务只剩下找一组特定的 \{x\} 使得它不组成 n 个不同的数字,而是 \frac{n}{2} 个,那么递归计算 A(x) 时规模即可减半。

————第 3 节————

比如说我让这组 \{x\}

\left\{ x_0,\cdots ,x_{\frac{n}{2}-1},-x_0,\cdots ,-x_{\frac{n}{2}-1} \right\}

那么平方之后不就减半了么?

但是这种关系不会传递下去。平方后得到的数字全是不小于 0 的数字。再次递归又回到了原来的形式。很尴尬。

不过这启迪我们。取相反数然后平方,可以把问题规模减半。但再一次递归就失效了。是否存在不失效的取值呢?

如果对于一个有偶数个元素的数集平方后得到的新集合,大小能够减半,且新集合也满足性质,这个性质就是折半性质。如果我们可以快速的找到一个满足折半性质的自变量 x 的取值集合,分治就是可行的。

是可以找到的。这个东西就是 n 次单位复根。

n 次单位复根是满足 \omega^n = 1 的复数 \omega , 其中由复数的运算法则(辐角相乘,模相加)可以很简单地得出 n次单位根有 n 个这个结论。

而又因为复数 \omega^n 在复数平面上的模都是 1 ,所以相乘之后还会是 1 ,那么所有的 w_i (1 \leqslant i <n) 就会均匀分布在单位圆上,类似当 n = 16 时它是这样的:

这里首先我列出几条性质:

\left( \cos \theta +i\sin \theta \right) ^k=\cos \left( k\theta \right) +i\sin \left( k\theta \right)

这个性质可以归纳法证出来。

还有很重要的两个性质

考虑欧拉公式

e^{2\pi i}=1=\omega ^n

易得

\omega =e^{\frac{2\pi i}{n}}

这时的单位根称之为主次单位根,记作

\omega_n =e^{\frac{2\pi i}{n}}

那么对于其他的单位根,记作

\omega _{n}^{k}=e^{\frac{2\pi ik}{n}},0\leqslant k<n

显然都是主次单位根整数幂

消去引理

\omega_{dn}^{dk}=\omega_{n}^{k}\,\,\left( d>0n\geqslant \text{0,}k\geqslant 0 \right)

证明:代入欧拉公式即可。

折半引理

\left( \omega _{n}^{k} \right) ^2=\omega_{\tfrac{n}{2}}^{k}

证明:代入消去引理即可。

于是我们证明 n 次单位根集合的折半性质

\left( \omega _{n}^{k+\frac{n}{2}} \right) ^2=\omega _{n}^{2k+n}=\omega _{n}^{2k}\times \omega _{n}^{n}=\omega _{n}^{2k}=\left( \omega _{n}^{k} \right) ^2

那么大功告成 !  \left\{ \left( \omega _{n}^{i} \right) ^2 \right\} 就等效于 \left\{ \omega _{\frac{n}{2}}^{0},\omega _{\frac{n}{2}}^{1},\cdots ,\omega _{\frac{n}{2}}^{\frac{n}{2}-1},\omega _{\frac{n}{2}}^{0},\cdots ,\omega _{\frac{n}{2}}^{\frac{n}{2}-1} \right\}

 x 的取值集合取单位复数根 , 不但满足折半的性质,而且还有一定的规律性,与原集合保持一致。这意味着我们只需要计算取 \left\{ \omega _{\frac{n}{2}}^{0},\omega _{\frac{n}{2}}^{1},\cdots ,\omega _{\frac{n}{2}}^{\frac{n}{2}-1} \right\} A_0A_1 即可。问题规模成功减半,复杂度降为 O(n \log n)

具体计算怎么计算呢?

A_{k}^{0}=A_0\left( \omega _{\frac{n}{2}}^{k} \right) =A_0\left( \left( \omega _{n}^{k} \right) ^2 \right)

A_{k}^{1}=A_1\left( \omega _{\frac{n}{2}}^{k} \right) =A_1\left( \left( \omega _{n}^{k} \right) ^2 \right)

那么我们要求的就是所有

A\left( \omega _{n}^{k} \right) =A_0\left( \omega _{n}^{2k} \right) +\omega _{n}^{k}A_1\left( \omega _{n}^{2k} \right) =A_0\left( \omega _{\frac{n}{2}}^{k} \right) +\omega _{n}^{k}A_1\left( \omega _{\frac{n}{2}}^{k} \right) =A_{k\,\text{mod }\frac{n}{2}}^{0}+\omega _{n}^{k}A_{k\,\,\text{mod }\frac{n}{2}}^{1}

另外我们要折半,这样才能 O(n \log n) 。假设上面式子的 k < \frac{n}{2} ,注意到

A\left( \omega _{n}^{k} \right) =A_{k}^{0}+\omega _{n}^{k}A_{k}^{1}

A\left( \omega _{n}^{k+\frac{n}{2}} \right) =A_0\left( \omega _{n}^{2k+n} \right) +\omega _{n}^{k+\frac{n}{2}}A_1\left( \omega _{n}^{2k+n} \right) =A_{k}^{0}-\omega _{n}^{k}A_{k}^{1}

后一个式子用到的几步变换无非就是把单位根的指数上拆了罢了。首先是指数是加了 \frac{n}{2} 相当于转了半圈,变为相反数。其次是 \omega_n^{2k+n} = \omega_n^n \times \omega_n^{2k}

然后就做完了 DFT 。再来理一下大致思路

想要转换点值表达式乘起来

→ 变换一下发现可以分治

→ 要算的 x 值太多,复杂度不对

→ 引入单位复根,折半算值

→ 求出点值表达式

————第 4 节————

我们来从线代角度考虑 DFT 究竟在做什么。

无非就是取了单位复根矩阵去算点值

\left( \begin{array}{c} A_0 \\ A_1 \\ \vdots \\ A_{n-1} \end{array} \right) =\left( \begin{matrix} \left( \omega _{n}^{0} \right) ^0& \left( \omega _{n}^{0} \right) ^1& \cdots& \left( \omega_{n}^{0} \right) ^{n-1} \\ \left( \omega _{n}^{1} \right) ^0& \left( \omega _{n}^{1} \right) ^1& \cdots& \left( \omega _{n}^{1} \right) ^{n-1} \\ \vdots& \vdots& \ddots& \vdots \\ \left( \omega _{n}^{n-1} \right) ^0& \left( \omega _{n}^{n-1} \right) ^1& \cdots& \left( \omega _{n}^{n-1} \right) ^{n-1} \end{matrix} \right) \left( \begin{array}{c} a_0 \\ a_1 \\ \vdots \\ a_{n-1} \end{array} \right)

因为方程显然可解,那么这个矩阵存在逆矩阵。 所谓 IDFT 也即从点值表达还原为系数表达就是在点值表达矩阵上乘这个大矩阵的逆矩阵。

由于某些包括证明过长和知道也没啥用的缘由,这里不再给出证明,只给出性质:这个矩阵的逆矩阵为

E=\frac{1}{n}\left( \begin{matrix} \left( \omega _{n}^{-0} \right) ^0& \left( \omega _{n}^{-0} \right) ^1& \cdots& \left( \omega _{n}^{-0} \right) ^{n-1} \\ \left( \omega _{n}^{-1} \right) ^0& \left( \omega _{n}^{-1} \right) ^1& \cdots& \left( \omega _{n}^{-1} \right) ^{n-1} \\ \vdots& \vdots& \ddots& \vdots \\ \left( \omega _{n}^{-\left( n-1 \right)} \right) ^0& \left( \omega _{n}^{-\left( n-1 \right)} \right) ^1& \cdots& \left( \omega _{n}^{-\left( n-1 \right)} \right) ^{n-1} \end{matrix} \right)

然后这样 IDFT 实现上就是让 DFT 时的每个 \omega_n^k 变为 \omega_n^{-k} ,然后再乘 \frac{1}{n} 即可。

————第 5 节————

这里并不打算讲那个没啥思维含量还和 FFT 本身不太搭边的优化。不过 FFT 代码还是要搬上来的。完整版的话去翻别的文吧。

呆子数论变换 ( Nerd Theory Transformation )

 

 

 

 

 

 

 

 

 

 

 

 

 

dkw on tree 板子

显得没事干水一发板子

dkw dsu on tree 这个东西主要就是对于树上的统计类问题采用树剖的方法去做,可以有效降低复杂度到 O(n \log n)

这个板子是 CF 600E

 

连载文章索引

置顶太多文太难受了。于是就有了这个。


算法文:

[18/12/21] 关于原根判定的若干证明

[连载中] [18/12/19] 今天一天尽享多项式!Í dag er「多项式」æfa! 今日は一日「多项式」三昧!

[18/12/19] dkw on tree 板子

[18/12/02] 关于 Purfer 序列

[18/12/01] 从小学开始的数数

[连载中] [18/11/06] 随便搞搞 ICG ( 公平组合游戏 ) 和其余的博弈

[18/11/05] exGCD 合并同余方程组

[18/09/28] 如何使用「构造函数法」去做Möbius反演

[连载中] [18/09/13] 从特殊的图论模型谈开去

[18/09/06] [莫名其妙的] 二项式反演

[18/08/17] [咕咕] OI 实用群论

[18/07/03] 弦图,区间图,完美消除,MCS,TreeDecp,PQTree及其他

[18/06/20] 头插 DP 指北

[18/06/11] 通过移位形成的置换群的轮换数

[18/03/21] 乱写点线代

[18/03/15] 树链刨分 ( 启发式剖分 )

[18/02/23] 带修莫队板子

[18/01/10] 网络流学习笔记

[连载中] [17/11/09] 数学笔记


想法:

[18/12/07] Code Style

[18/12/04] GNAQ 的训练康复计划

[18/09/17] 一个小题目

[18/07/12] [题单] 搜索及相关

[18/06/12] GNAQ 的文化课颓废 [指南]

[18/05/03] Vim 一键编译、保存、运行、退出

[18/05/03] reStructuredText – 一个轻量级的标记语言

[18/04/15] 一点黑科技

[18/03/16] 提高调试效率 – GNAQ 的变量命名风格

[连载中] [17/11/07] 向神犇学习!优秀文章汇总

[17/11/03] NOIP 2017 DP 专项练习

[17/08/15] Excited 卡常数技巧

[17/08/14] Tarjan – 求解有向图的强连通分量 (SCC)

[已弃坑] [17/08/14] A Set of Good Problems

[连载中] [17/08/13] 初中 OI 打味极鲜记

[17/08/13] 《星际穿越》影评 ( 转载 )


成套题解:

JLOI 成套题解 [已完结]

SCOI 成套题解

APIO2018 练习赛 题解

SCOI2010 六题题解

首先爆搜出所有的幸运数字,然后把倍数去重。这样还剩 943 个。

对于一个数字 x[A,B] 中的倍数的个数是 \lfloor \frac{B}{x} \rfloor - \lceil \frac{A}{x} \rceil +1

然后直接 DFS 跑容斥,将所有数字按照从大到小的顺序排序,选 1 个号码的答案 -2 个号码的 \text{lcm} 的答案 +3 个号码的 \text{lcm} 的答案……

将数字按照从大到小的顺序排序,使得 \text{lcm} 能够更快地超越上界。

考虑二分图匹配。左面一排点代表属性,右面一排点代表装备。意义是如果发挥当前的属性的装备被用过了,那用那个装备的属性就换一种。匈牙利即可。

设计状态 dp[i][j] 表示第 i 天持有 j 支股票的答案。

转移分为三种:

  • 从 dp[i-1][j] 转移
  • 从 dp[i-w-1][k] 转移(买入)
  • 从 dp[i-w-1][k] 转移(卖出)

考虑后两个的转移式子:

\text{dp}\left[ i \right] \left[ j \right] =\max \left\{ \text{dp}\left[ i-w-1 \right] \left[ k \right] -\text{ap}\left[ i \right] \times \left( j-k \right) \right\}

 

\text{dp}\left[ i \right] \left[ j \right] =\max \left\{ \text{dp}\left[ i-w-1 \right] \left[ k \right] +\text{bp}\left[ i \right] \times \left( k-j \right) \right\}

把后面的 y \times (j-k) 那部分展开,发现后两种转移是个滑动窗口,上单调队列。

经典套路,二维正交坐标系把 1 看做向右走,把 0 看做向上走,答案为不跨越直线 y=x (在下半部分走)到达点 (n,m) 的方案数。

也即不触碰直线 y=x+1 到达的方案数。以 y=x+1 为对称轴做 (n,m) 的对称点为 (m-1,n+1)

答案为 C_{n+m}^n - C_{n+m}^{m-1}

三分套三分。设在 AB 上从 A \rightarrow E ,在 CD 上从 F \rightarrow D ,那么中间就是 E \rightarrow F

然后对 E 三分,固定 E 的位置三分 F 的位置。

 [Scoi2010]序列操作

直接上线段树硬搞。维护最左端 0/1 最右端 0/1 和整段的 0/1 即可。

合并的时候讨论一下。

下推的时候覆盖标记消翻转标记,翻转标记优先翻转覆盖标记,再更新自己。

 

BZOJ3895 取石子

这题思路不错。

首先考虑对于一个 >1 的堆,如果合并他对先手有利,那么这堆石子在取完之前一定会被先手合并。同理如果对后手有利也是。

既然合并这个动作要不就是对先手有利要么就是对后手有利,那肯定这堆石子最后会被合并。

并且在取完之前,合并这个动作无论在何时发生,都等同于在对这堆石子操作时的前两步内发生。

那么我们就可以把充裕堆 ( 大小 >1 的堆 ) 先提前合并了,然后在 DAG 游戏图上记搜 \mathrm{SG} 值。

操作分为几种:

  • 拿走一个孤单堆
  • 拿走充裕堆的一个石子
  • 把一个孤单堆合并到充裕堆内
  • 把两个孤单堆合并,成为充裕堆的一部分

然后就写个代码就好了。复杂度大概是 O(T \cdot \sum{a_i}) 的。

 

毒瘤题解#2 CEOI2008 | BZOJ1393 Knights

一道无比毒瘤的 Every-SG 的题。

注意此题BZOJ没有SPJ,方案输出要严格按照以下顺序 (找到了就输出) :

int dx[4]={-2,-2,-1,1},dy[4]={1,-1,-2,-2};

题面

上来先打表!这样:

把表打了你会发现一些奇怪的规律

然后写一下,我们就有:

好,那么这题基本就做完了。剩下的就是用用那个 Every-SG 的定理然后找一下方案罢了。。

 

毒瘤题解 BZOJ2410

某次搜 “Nim” 手贱搜出这破题来,结果自闭了一上午,自闭了。

首先考虑 k>2 的情况,因为任意一个格子都可以填颜色而两边的格子不会影响它,答案是 0 的格子数的奇偶性决定的。

那么再来考虑 k=1 的情况。此时我们把每段白格子单独拿出来看:

首先(除掉整个序列的开头和结尾)每段的第 1 和最后一个这两个格子是不能染色的。

那么假设我们在中间染了一个,那就分成了两个子局面,比较显然这两个子局面是相互独立的,那么我们就可以用 SG 定理了。

再考虑如何算一段白格的 \mathrm{SG} 。首先长度为 0 的白格子的 \mathrm{SG}0 ,长度为 1 的因为只能转移到 0 所以  \mathrm{SG}=1

那么接下来考虑长度为 n 的,我们先假设这 n 个格都能被染色

那么染位置 i 会让剩下两段为 i-2n-i-1

(注意特判 i=1i=n 的情况,这两种本质上是一样的)

那么我们爆算一波 \mathrm{SG}  值。

打个表找规律

0,1,1,2,0,3,1,1,0,3,3,2,2,4,0,5,2,2,3,3,0,1,1,3,0,2,1,1,0,4,5,2,7,4,
0,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,2,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7,4,
8,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7,4,
8,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4

然后发现除前两段之后循环节为 34

(其实这个非常神奇,不过这种模型居然也出现在 《Winning Ways》 里面了,Orz……可以看一下这个A002187 )

然后就直接乱搞就可以了。。

这就完了,再来考虑 k=2 的情况

如果你不去管全部空白的特殊情况,那么空白块总共有三种:

  1. 有一端与一个染色块相邻,另一端为整个序列的首或尾。
  2. 两端都与染色块相邻,两端颜色不同。
  3. 两端都与染色块相邻,两端颜色相同。

可以把 [2] 和 [3] 一起考虑,很轻松的使用归纳法证明 [2] 的 \mathrm{SG} 值都是 0 ,[3] 的 \mathrm{SG} 值都是 1

那么考虑第一种情况,随便画个图或者写个暴力可以得到长度为 n 的段的 \mathrm{SG}=n

这样就基本做完了。再回来考虑全部空白的情况。如果长度为 N ,后继局面显然有 N 种。

然后你发现每种都是两个子局面异或起来,假设先手从位置 i 劈开,那么就是 i-1 \oplus n-i

然后 O(n) 求一下 \mathrm{SG} 就好了。

不过事实上是数据过水,导致没有这类情况,不用写就能过。。。。

另外搜 A002187 的资料的时候我搜到一份很有趣的文档讲的是这个序列和井字格游戏的关系,好像可以出一道题的样子。。

 

– END –