codechef FEB18

提示：由于排版需要，我的Editorial使用了[hide]、[/hide]标签，不科学上网这个标签就用不了，所以请大家科学浏览Editorial。(不过说起来不科学浏览的话，公式什么的也显示不了吧。

BROCLK

$\cos(x)=d/l$，我们要求的是$\cos(tx)$。有公式$\cos(nx)=2\cos(x)\cos((n-1)x)-\cos((n-2)x)$，写个矩阵快速幂就好了。证明见这里。

不知道上面那个公式的可以把所有数写成$a+b\sin(x)$的形式，然后用$\sin(a+b)$与$\cos(a+b)$的公式爆搞。

LUCASTH

挺不错的一个题。

首先注意到答案是$f(x)=\prod_{i=1}^n(x+i)$的系数中，不是$p$的倍数的个数。由于$p$很小，我们可以想到把$f(x)$写成$g(x)^q\cdot h(x)$的形式，其中$q=\lfloor n/p\rfloor$，$g(x)=\prod_{i=1}^p(x+i)$，$r=n\bmod p$，$h(x)=\prod_{i=1}^r(x+i)$。再注意到$g(x)$实际上与$x^p-x$同余。我们只需要求$(x^{p-1}-1)^q\cdot h(x)$的非零系数个数即可。可以发现这个东西等于 ($(x^{p-1}-1)^q$的非零系数个数) 乘以 ($h(x)$的非零系数个数)。($r=p-1$的情况除外，这个特判就好)。前者用Lucas定理求，发现就是将$n$转成$p$进制；后者用分治FFT就可以求出。总复杂度$O(\log^2 n+p\log^2 p)$。

CHEFCHR

我也想要这样骗钱啦!

CHEFPTNT

我也想要这样骗钱啦!

公式是

$$\min(cnt[O],x\lfloor\frac{M+1}{2}\rfloor)+\min(cnt[E],x\lfloor\frac{M}{2}\rfloor)\ge N$$

CARPTUN

我也想要这样骗钱啦!

答案是$\max(A)\cdot(C-1)$。证明略。你站=数据结构+FFT+小学奥数。

CHANOQ

一开始人们以为这个题是个hard。后来大家发现玩脱了。(我觉得这题还没POINPOLY难

可以用主席树在$O(\log n)$的时间求出左端点在$[l_1,r_1]$内，右端点在$[l_2,r_2]$内的区间个数。

如果$CNT\le\sqrt{\frac{n}{\log n}}$，我们可以用$O(CNT^2\log n)=O(CNT\sqrt{n\log n})$的时间暴力求出答案。

如果$CNT>\sqrt{\frac{n}{\log n}}$，我们可以前缀和瞎搞，在$O(n)=O(CNT\sqrt{n\log n})$的时间内求出答案。

另外这题据说bitset可以水过。

POINPOLY

admin问我：这个题难度怎么样? 我随口回了个medium-hard。。

然后admin告诉我，他的计划是出一道easy。。

我瞬间就懵了。。。

这题解法很多，admin的标解非常漂亮：考虑$n=10$的情况，容易用鸽笼原理证明一定有两个点的中点是整点，这个点也一定严格在多边形内部。如果$n>10$呢?把凸包分成长度为$10$的若干段就是了。

当然也可以在$O(n+k)$的时间内列出严格在多边形内部的$k$个点。怎么做留给读者自行思考。

蛤?泥的博客居然还有读者?

CLANDLBL

其实这个题挺妙的。可惜被我用Graph isomorphism heuristics给搞过去了。这里就不讲std了。。讲讲我的瞎搞做法。。

首先我们有个大暴力。依次枚举每个点的label，复杂度$O(n!)$。我猜其实是$O(n^3)$

然后我们可以优化一下。令$sum(i)$为$i$的邻边上数的和，$sum'(i)=\sum_{k=1}^ncommon\_divisor\_count(i,k)$。枚举一个点$v$的label时候只枚举$sum'(l(v))=sum(v)$的那些$l(v)$。用map啥的优化一下。

BIAS

cha题嘛，当然是不会做才出出来的咯

PERMPAL

这个题是在比赛开始后admin临危受命出出来的题目。。(因为有个叛徒出了一个原题，比赛进行了1h后被揪出来了。)我觉得这题作为一个cakewalk/simple还是很优秀的。。我夸夸他啊

题解很简单。。先check一遍，如果有解那么就每次找两个相同的字符然后决定它们的位置即可。

SEMESTER

来晚了的同学可以看看题意。

事情是这样的。。有一个1☆小哥，兴致勃勃跑来出题。然后他把上面链接里的原题搬到了cc上，把题面瞎几把改了一下。他第一次骗钱没有经验。。犯下了各种各样的花式低级错误。。包括但不限于int sum=a[0]+a[1]+..+a[6];和纯手打测试数据(于是一个数字有两个前导零)等低级错误。我跟他解释了大概5h的“$\sum a$可以达到$7\times 10^9$，你这里不能用int”“你数据这里造错了，那里造错了”，他哪里都不懂，瞎几把改也改不好，倒是浪费了我的时间。终于我强行帮他把数据改好，这题过了testing。

但是!他来这的目的可不是为了出题。比赛开始后我惊讶地看到，居然有人在30min内做出了CLANDLBL!然后我仔细看了看他的代码。。貌似代码风格跟我有点像。。再看了看过程。。woc居然是出题人的标解。。。这题能想到标解的都是天才啊。。。再定睛一看，这tm就是我的代码嘛!我翻出后台我写的出题人做法，发现和这货的代码一模一样。。。更加神奇的是，他交的POINPOLY的部分分代码居然也是我写的。。。

我感到了恐惧，立马向admin报了警。admin大大很快就找到了这个账号的IP地址，发现和1☆小哥的IP重合

然后我们又抓到了实锤(注：实锤页面已挂，大概就是说在比赛中交我程序的那人就是1☆小哥)

于是这位小哥就被封号了(然而他的至少三个小号中只有两个被封)。

说起来去年的FEB17也有两个题被删掉了。不知道是怎么回事。做tester做admin不容易呀。