最终得对抗自己

[2017 HDU多校赛] 解题报告

写一下这几天多校赛做的题目

[BZOJ 3625] 小朋友和二叉树 多项式

给你长度为N的不重复数列C, 整数m, 求对于每一个正整数s<=m, 点权在数列C内并且点权和为s的二叉树数量。

非常好的题目!
组合数学结合多项式与生成函数, 同时运用多项式开根和求逆。

[考试题目] 偶 分块

有一个N个数的数组A, 如果区间 [l, r] 满足所有数字只出现偶数次, 那么这个区间很好。
问有多少个很好的区间?

分块哈希随便乱搞!

[BZOJ 3125] CITY 插头DP

一个网格状地图被分割成N*M个块。
. 表示这个块可以通过
– 表示这个块只可以左右通过
| 表示这个块只可以上下通过
# 表示这个块不能通过
(从每个块只能走到其上下左右相邻的四个块)
那么把所以可以通过的块都经过且只经过一次并回到原地的方案数是多少?

分类讨论, 插头DP!

[BZOJ 2216][Poi2011] Lightning Conductor DP

已知一个长度为n的序列a1,a2,…,an。
对于每个1<=i<=n,求最小的非负整数p满足 对于任意的j,aj < = ai + p – sqrt(abs(i-j))

动态规划优化好题!

[HDU 3507]Print Article 斜率优化

给出数列C,常数W,
求:
$$ f(i)=min { f(j)+sum(j,i)^2+W } $$
$$ 其中:sum(i,j)=\sum_{k=i}^j C_i $$
的第N项。
N<=1e7

斜率优化入门。

[51Nod 1238]最小公倍数之和 V3 杜教筛

世界之大,无奇不有。
如何突破线性筛法的极限速度?
用低于线性的复杂度求得积性函数前缀和。

给定N,求
$$ \sum_{i=1}^n \sum_{j=1}^n \frac{ij}{gcd(i,j)} $$
N<=10^10,答案对10^9+7取模。

这题并不简单。

[POJ 2888]Magic Bracelet Burnside与矩阵加速

给你长度为N的项链(可以旋转),问用M种颜色染色有多少种本质不同的方案。
其中还有k对限制关系,表示颜色i和颜色j不能放在一起,答案要取模。

很有意思哦!

[UVa 10294]Arif in Dhaka 置换群与组合数学

群论和组合数学, Polya定理计数!

[HDU 4609] 3 Idiots FFT

给N条长度不一的木棍,求随机选取三根木棍能组成三角形的概率。
答案精度要求1e-7。

世界之大,无奇不有。 快速傅里叶变换!