SDOI2013

为了不留下黑历史，我还是不要作任何主观评价比较好
怎么做得到嘛！

R1D1T1 随机数生成器

BZOJ3122
BSGS+大讨论（不想做）
待补

R1D1T2 森林

BZOJ3123
容易发现如果在一棵树上查询，那就是主席树
这道题只有合并操作，那就好办了，启发式合并
每次Dfs小的那棵树，把小的那棵树合并进大的那棵树的主席树里

R1D1T3 直径

BZOJ3124
第一问两次Dfs；也可以Dp：$f[u]$表示u的子树中直径，$g[u]$表示u子树中最深点深度，那么$f[u]=max(max(f[v]), max(g[v])+secondmax(g[v]))$，v表示u的儿子
第二问，如果每条直径都经过一条边，那么去掉这条边后形成了两个联通块，这两个联通块的直径一定会比原树的直径小（下面开始思维混乱，其实说说麻烦自己yy一下还是很简单的）
树形Dp一下，调用$Dfs(u, fa, F, G)$，传入参数F表示除了u的子树以外的联通块中的直径，G表示除了u的子树以外的联通块中的点距离u的最远距离
Dp数组$h[u][0..1]$表示u儿子们子树中的最深深度的最大值和次大值，$l[u][0..1]$表示u的儿子们的子树直径的最大值和次大值，这个可以在前面Dp算直径的时候算
那么显然去掉$(u,fa)$这条边后两个联通块的直径就是$F$和$f[u]$
考虑如何从u向儿子v转移，也就是说新的$F’$、$G’$是什么。
先设一个变量$tmp$，如果$g[v]==h[u][0]$
那么 $$tmp=G+h[u][1],G’=max(G+w(fa, u), h[u][1])$$
否则 $$tmp=G+h[u][0],G’=max(G+w(fa, u), h[u][0])$$
如果$f[v]==l[u][0]$，$F’=max(F, tmp, l[u][1])$，否则$F’=max(F, tmp, l[u][0])$

如果上面哪里写错了……那很正常

R1D2T1 方程

BZOJ3129
第二类条件直接在$m$中减掉$a-1$就好了，这样限制就变成了$x>=1$
第一类条件很少，可以容斥，强制使得一些限制不满足，转化为第二类限制
然后就是组合数取模了，直接把模数分解成$\prod p^c$，对于每个$p^c$取模，然后CRT合并就好了
怎么取模呢，用阳阳教我的“拓展卢卡斯”（这应该是个口胡的名字）
考虑一个组合数$C_m^n=\frac{n!}{m!(n-m)!}$，把分母分子中的$p$都提取出来然后消掉，就可以算逆元了
现在考虑如何把一个阶乘中的$p$提取出来。
先预处理$p^c$以内不是$p$倍数的数的前缀乘积$Mul[i]$
显然$x$以内$p$的倍数个数是$\lfloor \frac{x}{p} \rfloor$，它们是$p,2p,3p……$，那么可以提取出$\lfloor \frac{x}{p} \rfloor$个p，并且这些数变成了$1,2,3……$，于是可以递归
剩下的数不是p的倍数，利用$Mul[i]$算
又发现$x\equiv p^c+x(mod p^c)$，于是每$p^c$个数的乘积是相同的，于是快速幂
妈的zz讲不清楚

R1D2T2 费用流

BZOJ3130
显然把所有P的单位费用都放在流量最大的一条边上是最优的
那么二分最大边就好了，注意要实数二分

R1D2T3 淘金

BZOJ3131
显然可以行列分开考虑，如果变化后为$x$的数有$a$个，为$y$的数有$b$个，那么坐标为$(x,y)$的数有$ab$个，要求前$k$大用堆就好了
问题转化为算出变化后为$x$的数个数$f[x]$
这显然可以数位Dp，$f[i][j][0..1]$表示考虑了前$i$位当前乘积为$j$，是/否已经小于$N$的数个数。但是第二维太过巨大不能枚举
发现$j$肯定是由2、3、5、7乘起来的，总量应该不会太多，打表发现确实只有1W多个，于是离散第二维Dp就好了

R2D1T1 assassin

BZOJ3197
复杂度简直玄妙
一上来先考虑树同构，以重心为根，用波兰哈希法得到每棵子树的hash值
$f[u][v]$表示第一棵树中$u$与第二棵树中$v$配对的最小代价（当然首先$u$、$v$的hash值相等），现在考虑配对它们的儿子，可以配对的$su$、$sv$之间连费用为$f[su][sv]$的边，跑费用流
好了没了，估计复杂度$O(n^7)$，可能没这么高，但是不会算

R2D1T2 spring

BZOJ3198
设恰好有$k$个位置相同的组数为$G_k$
可以用哈希算出至少有$k$个位置相同的组数$F_k=\sum_{i=k}^6 C_k^i G_k$
那么答案 $$G_k=\sum_{i=k}^6(-1)^{i-k}C_k^i F_i$$
这个结论是抄题解的，并不会用正常的方法推出来，求大爷教我
网上都没有证明，我就yy了一下：
上式展开成 $$G_k=\sum_{i=k}^6(-1)^{i-k}C_k^i \sum_{j=i}^6 C_i^j G_k$$
发现$G_j$的系数$A_j=\sum_{i=k}^j(-1)^{i-k} C_k^i C_i^j$
由于$C_i^j C_k^i=C_k^j C_{i-k}^{j-k}$
所以$A_j=C_k^j \sum_{i=k}^j(-1)^{i-k}C_{i-k}^{j-k}=C_k^j \sum_{i=0}^{j-k}(-1)^i C_i^{j-k}$
根据二项式定理，$A_k=1$，其他$A$均为0

R2D1T3 escape

BZOJ3199
半平面交然后求一下最短路
待补

R2D2T1 项链

BZOJ3202
山东的同学数学都那么带劲吗

• Part I:
  首先算出有几种不同的珍珠$A$
  设有$i$个的珍珠个数为$A_i$，下面给出$A_3$的计算方法作为例子：
  $$\begin{align} A_3 &=\sum_{i=1}^a\sum_{j=1}^a\sum_{k=1}^a \epsilon(gcd(i,j,k)) \\ &=\sum_d \mu(d) \lfloor \frac{a}{d} \rfloor ^3 \end{align}$$
  那么发现$A_i=\sum_d \mu(d) \lfloor \frac{a}{d} \rfloor ^i$
  考虑一下一个三元组(i,j,k)的算重次数，显然$A=\frac{A_3+3A_2+2A_1}{6}$

• Part II:
  现在相当于有A种颜色的珍珠，做等价类计数
  然后就可以二话不说先套一发Polya定理，第$i$种置换是顺时针旋转$i$个珍珠，有$gcd(i,n)$个循环。我们先使得每个循环中的珍珠颜色一致。
  那么有几种合法的不动点呢？
  考虑珍珠$1$属于第一个循环，珍珠$2$属于第二个……珍珠$gcd(i,n)$属于第$gcd(i,n)$个，珍珠$gcd(i,n)+1$又属于第一个循环。
  所以问题显然可以转换为：把每个循环看成一个珠子，相邻两个不能相同。即现有一个有$gcd(i,n)$个珠子的环，相邻两个不相同的方案数。
  Dp一下试试：
  设$f[i][0..1]$表示长度为$i$的链，最后一个元是/否和第一个相同的方案数
  那么
  $f[i][0]=f[i-1][1]\times(A-1)+f[i-1][0]\times(A-2)$
  $f[i][1]=f[i-1][0]\times(A-2)$
  发现$f[i][0]$就是长度为i的环的答案
  这个可以用矩阵乘法加速，但是似乎会被卡常数我擦！
  那么我需要一个通项式，但是两个互相关联的函数的通项式我不会求
  那就化一下呗，看$f[i][0]$会怎么转移：
  $f[i][0]→f[i+1][1], f[i+1][1]\times(A-1)→f[i+2][0]$
  $f[i][0]\times(A-2)→f[i+1][0]$
  所以设$F_i$表示长度为i的环的答案的话，$F_i=(A-2)\times F_{i-1}+(A-1)\times F_{i-2}$
  注意如果环长为1的话，除非题目中给出的项链长度为1，否则显然是无论如何都不合法的，所以$F_1=0$
  所以就很好推通项式了

• Part III:
  灿爷教我学数学
  设$F$的生成函数$G(x)=\sum_{i\geq 1}F_i x^i$
  $(A-2)xG(x)=\sum_{i\geq 2}(A-2)F_{i-1}x^i$
  $(A-1)x^2 G(x)=\sum_{i\geq 3}(A-1)F_{i-2}x^i$
  所以
  $$[1-(A-2)x-(A-1)x^2]G(x)=F_1 x+F_2 x^2-F_1 x^2=(A^2-A)x^2$$
  下面第三步用了待定系数法：
  $$\begin{align} G(x)&=x\frac{(A^2-A)x}{1-(A-2)x-(A-1)x^2} \\ &=x\frac{(A^2-A)x}{[(1-A)x+1](x+1)} \\ &=x(\frac{A-1}{(1-A)x+1}+\frac{1-A}{x+1}) \\ &=x[(A-1)\sum_{i\geq 0}(A-1)^i x^i+(1-A)\sum_{i\geq 0}(-1)^i x^i] \\ &=\sum_{i\geq 1}[(A-1)^i+(1-A)(-1)^{i-1}]x^i \end{align}$$
  由此我们得到$F_i=(A-1)^i+(A-1)(-1)^i$

• Part IV
  知道了$F$的通项式以后
  $$\begin{align} Ans &=\sum_{i=1}^n F_{gcd(i,n)} \\ &=\sum_{d|n}F_d \sum_{i=1}^{\frac{n}{d}}\epsilon(gcd(i,n)) \\ &=\sum_{d|n}F_d \sum_{i=1}^{\frac{n}{d}}\sum_{d’|gcd(i,\frac{n}{d})}\mu(d’) \\ &=\sum_{d|n}F_d \sum_{d’|\frac{n}{d}}\mu(d’) \frac{n}{dd’} \\ &=\sum_{d|n}F_d \phi(\frac{n}{d}) \end{align}$$
  枚举约数算一下就好了

• Final Part
  整理一下刚才都干了什么
  首先PartI反演算出珍珠颜色个数
  再算出置换的不动点个数之和，利用$F_i$的通项式和PartIV的反演可以$O(\sqrt n\log n)$计算
  最后根据polya定理除以$n$
  你觉得这就没了吗？
  发现$n$是$10^14$级别，所以可能与$Mod$不互质
  那怎么办？发现$n$最多只有一个因子$Mod$，那么特判一下当$Mod|n$时，先在模$Mod^2$下算出分子，再把分子除掉$Mod$再乘上$\frac{n}{Mod}$即可，这样答案是不会变的

R2D2T2 保护出题人

BZOJ3203
我该说巧妙呢还是傻逼呢
只要发现$y$之间独立，且$y_i=max(\frac{\sum_{k=j}^i a_i}{x_i+(i-j)\times d}),j<i$，那就好做了
发现上式分子是$suma_i-suma_{j-1}$，分母是$(x_i+id)-jd$
所以把小于$i$的每个$j$看成一个点$(suma_{j-1},jd)$，询问点$(suma_i,x_i+id)$与这些点形成直线的最大斜率即可，这个可以维护一个下凸壳然后三分

R2D2T3 城市规划

BZOJ3204
太神了不会，待补