题外话
尼玛颓废着颓废着就开学了= =无聊终于把第三场的题全补完了
hdu 5316(1001) Magician
Solution
线段树裸题，维护四个东西，以奇/偶开头奇/偶结尾的最大值，正常线段树合并即可。
Code
hdu 5317(1002) RGCDQ
Solution
水题，发现$2\times 3\times 5\times 7\times 9\times 11\times 13 \times17>1000000$，所以素因子种数最多为7个，前缀和统计一下即可
Code
hdu 5318(1003) The Goddess Of The Moon
Solution
水题，题目太长比赛没看= =，唯一的坑是要把数字去重，然后容易看出可以用矩阵乘法来递推
Code
hdu 5319(1004) Painter
Solution
简单模拟题，按题目要求一刷刷到底就可以了
Code
hdu 5320(1005) Fan Li
Solution
感觉这道题是个不错题，考虑以$i$为开头的序列，$gcd$如果发生变化一定至少除以$2$，所以不同的gcd区间最多也是log级的。可以预处理出所有的四元组$(g,i,l,r)$，表示以$i$为开头，结尾在$[l,r]$区间内$gcd$为$g$。
考虑$dp$，不妨考虑当前$gcd=x$的方案数以及区间数，假设该四元组开头为$i$,显然区间数是以结尾在$[1,i-1]$区间内的最大值$+1$，方案数也很好计算。容易发现用一个线段树就可以轻松维护了。
Code
hdu 5321(1006) Beautiful Set
Description
A的计算方法是：对于$n$个数的某个排列，此排列的美丽值为这个排列所有的区间最大公约数之和。然后这个集合的美丽值为$n$个数的所有排列的美丽值之和。
B的计算方法是：在$n$个数中选出$k(1 \le k \le n)$个数，对于某种选取方案，这种方案的美丽值为$k$个数的最大公约数乘上$k$。然后这个集合的美丽值为所有选数方案的美丽值之和。
Solution
很容易想到用$cnt[i]$表示集合中$i$的倍数个数
- 考虑第一个人
$F1[x]$表示$gcd$为$x$的倍数的区间的个数
$f1[x]$表示$gcd$为$x$的区间的个数
$F1[x]=\sum_{x|d}f1[d]$
且$F1[x]=\sum_{j=1}^{cnt[x]} \binom{cnt[x]}{j}\times j! \times (n-j+1)!$
从$cnt[x]$里选$j$个数，再把$n-j$个数和这$j$个数算做$n-j+1$的排列
- 考虑第二个人
$F2[x]$表示$gcd$为$x$的倍数的区间的个数
$f2[x]$表示$gcd$为$x$的区间的个数
易知$F2[x] = \sum_{x|d}f2[d]$
且$F2[x]= \sum_{j=1}^{cnt[x]} \binom{cnt[x]}{j}\times j = cnt[x]\times 2^{cnt[x]-1}$
这个稍微推推就能推出来
同样的$F2[x] = \sum_{x|d}f2[d]$
然后就是我们熟悉的莫比乌斯反演辣！
$F(n)=\sum_{n|d}f(d)$
可以得到
$f[n]=\sum_{n|d}\mu(d/n)\times F(d)$
于是可以计算出$f$，$\sum f[i]\times i$即是答案
Code
hdu 5322(1007) Hope
Solution
这题其实并不难，考虑$dp[i]$为长度为$i$的排列的答案，枚举这个排列最大值所在的位置，最大值左边和它都是联通的，于是我们可以得到转移方程
$dp[i]=\sum_{j=1}^i \binom{i-1}{j-1}\times (j-1)!\times dp[i-j]\times j^2$
稍加变换我们可以得到
$dp[i]=(i-1)!\times \sum_{j=1}^i \frac{j^2}{(i-j)!}\times dp[i-j]$
令$k=i-j$我们可以得到$dp[i]=(i-1)!\times \sum_{k=0}^{i-1}\frac{(i-k)^2}{k!}\times dp[k]$
展开得$dp[i]=(i-1)!\times (i^2-2ik+k^2)\times \frac{dp[k]}{k!}$
维护三个前缀和即可O(N)解决，当然你可以没思维难度得想到cdq分治+NTT得做法QAQ
Code
hdu 5323(1008) Solve this interesting problem
Solution
考虑$[l,r]$是做左儿子还是右儿子，具体有$4$种情况，暴力枚举即可，实际上的复杂度是$4^{11}$，完全可以接受
Code
hdu 5324(1009) Boring Class
Solution
三维最长不下降序列之类的题，很容易想到按$id$算答案，$r$这一维排序，$l$这一维用树状数组维护然后cdq分治的经典做法。
考虑$dp$由于要字典序最小，先cdq分治算右区间的答案，考虑对左区间的影响即可。
写了不到$80$行，轻松愉快，cdq分治真是个高大的姿势。。。爽
Code
hdu 5325(1010) Crazy Bobo
Solution
水题，按权值排序后，权值小的向大的连即可，dp一下就行了
Code
hdu 5326(1011) Work
Solution
水题，随便dfs就行了= =
Code
完结撒花！
继续补题！>_<