codechef MAY16

cc改版了，就在MAY16开始前几个小时。

挺漂亮的。

不过有个缺点是，墙内上不了?

更正： (5.8早上)

再更：墙内突然上得了了 (5.8晚上)

按AC时间顺序写咯

LADDU

模拟题，论strcmp的使用。

FORESTGA

二分答案，注意别爆long long了。$O(N\log W)$。

CHEFSOC2

普及组级别的dp题。。(真的是普及组某题改，至少很像

$f_{i,j}$表示第$i$轮的时候球在第$j$条狗手上的方案数，转移随手写

SEAGCD2

开始以为是数论，容斥，反演，瞎jb搞搞

后来发现是瞎jb搞搞

枚举$A$中有多少个$1$，剩下的数肯定互不相同，考虑$\gcd(a,b)>1$就给$a,b$连一条边，相当于枚举图的独立集，因为出题人是sereja，所以可以猜测这样的独立集个数不会很多，就可以做出来辣

不过写了一发好像过不了。。这是因为图中有一些孤立的点($>50$的质数)，把它们单独拎出来就好，剩下90个点的独立集个数就真的不多了，搜索一遍大概2s的样子

用$h_{i,j}$表示$M=j$的时候选$i$个不同的数(组成集合，不是排成数组)的方案数，且每一个数都不能是$>50$的质数。这个直接搜吧

然后用$f_{i,j}$表示$M=j$的时候选$i$个不同的数的方案数，可以选$>50$的质数。枚举选几个这种质数，设为$K$个，那么就有

$$f_{i,j}=\sum_{K=0}^{\min(f(j),i)}\binom{f(j)}{K}h_{i-K,j}$$

其中$f(j)$是$51\sim j$内的质数个数。那么一次搜索就可以干掉所有$f$值。

然后要计算答案的话就是

$$\sum_{t=0}^N\binom{N}{t}f_{N-t,M}(N-t)!$$

这题通过人数居然只有CHEFMATH的一半。。窝不服

CHBLLS

455 vs 112

天平返回-2,-1,0,1,2分别表示1,2,3,4,5，一次出答案→_→

就酱

CHEFNUM

这个题代码长度限制50000B简直就是福利啊 本题解结束

呃还是写一些正常的东西吧，考虑求$f(l)+f(l+1)+\dots+f(r)$。分段打表，求出$f(1)+\dots+f(s),f(s+1)+\dots+f(2s),f(2s+1)+\dots+f(3s)$，直到$f(10^9)$为止(这个可以花很长时间打表)，然后得到$10^9/s$个数打进源程序里面。这样对于一次询问我们只需要求不超过$s$个数的$f$值就好。我取$s=250000$效果不错，只打了40K，官方数据0.3s一个点(10 querys)。

DISTNUM2

AFO多年已经不会写主席树辣

考虑$L_i$为最大的$j$使得$A_j=A_i,j<i$。如果不存在那么就是$-1$。(在处理DISTNUM的时候我们就是这么玩的

问题变成$l\le i\le r,L_i<l$的数中第$k$大。平面上$N$个点，每个点有一个权值，每次在线询问求矩形中第$k$大的点。k-d tree套主席树。时间复杂度$O(Q\sqrt{n}\log n)$，空间复杂度$O(n\log^2 n)$。

常数优化：

• 离散化，主席树深度能小就小
• 在询问的时候一些节点已经是$0$了就不要管了。

STARROAD

出题人语死早辣

问题应该是这样的：$f_{i,j}$为原图中点$i$与点$j$之间长度$\le K$的不一定简单的路径条数，构造一个新图，$i,j$之间有$f_{i,j}\bmod X$条边，求新图的生成树个数，需要高精度。

矩乘求$f$，基尔霍夫矩阵求生成树个数。答案上界约为$10^{878}$。取$Q=100$个$10^9$级别质数然后crt。

crt这么玩：设模数是$p_1,p_2,\dots,p_{100}$，其乘积为$P$，答案为$a_1,a_2,\dots,a_{100}$，找出$q_i$使得$q_i\equiv 1 \pmod p_i$，$q_i\equiv 0\pmod p_j(j\ne i)$，求$\sum q_ia_i\bmod P$即可。如何求$q_i$呢?令$P_i=\frac{P}{p_i}$，其实$q_i$就是$P_i$在模$p_i$意义下的逆元，再乘以$P_i$。记$r_i$为$P_i$在模$p_i$意义下的逆元。要求$\sum q_ia_i$即求$\sum P_ia_ir_i\bmod P=(\sum P_i\times (a_ir_i\bmod p_i))\bmod P$。如果要求高除高的余数。。因为商不超过$100$，所以暴力就好了。。

需要用到高*低，高/低，高+高，高-高。

复杂度：矩乘$O(N^3\log K)$，基尔霍夫矩阵$O(100N^3)$，高精度合答案$O(1000\times 100)$。好像可以过的样子，最终3s+过辣。

SHOP2

真的没兴趣做cha题

CHEFMATH

一觉醒来(5月16日早上)快400人过了这个题。。好方

吓得我赶紧去补了一发

总共$43$个斐波那契数。考虑meet-in-the-middle，搜出所有$6$个斐波那契数加起来的方案，一共有$\binom{48}{6}$种，存起来。然后对于一次询问搜索最小的$4$个数是哪些，一共$\binom{46}{4}$种。需要用到“所有数都大于$f(x)$的选择方案中，恰好凑出$y$的方案数”。

复杂度$\binom{48}{6}+\binom{46}{4}Q$，可能多一些log。卡卡常就不小心过了。

nonsense

5月22日晚上。。Space Colony又要翻新了。。一首歌唱三遍也是厉害

不过话说组织最近很勤快啊