YOU'VE MADE A BRAVE DECISION, WELCOME.

流离之人追逐幻影。

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
太神了不会,待补