2018 Multi-University, HDU Day 6

ultmaster: 除了我签了个到，全是 kblack 做的。可能 kblack 1v3 结局也差不多吧。。。

Problem A

Solved by ultmaster. 00:39 (+4)

题意：小学积分题。

题解：不会积分，上了个 Wolfram Alpha。没想到漏除一个 $b$（纸上是有的，抄上去就没有了）。对着一个明显不对的答案调了好久，还仔细考虑有没有精度问题。答案是 $\pi a + 2b$。注意输出要去尾。根本不需要什么 long double...

Problem B

Solved by kblack. 02:12 (+2)

题意：$K$ 个书架放 $N$ 本书，总价值为 $score = gcd(beauty_1, beauty_2, ..., beauty_k)$，$beauty_i = 2^{fib(cnt_i)} - 1$，求期望。

题解：首先研究 gcd 的性质了解到 $scrore = 2^{fib(gcd(cnt_i))}-1$，枚举 gcd，用插板求出方案数，然后容斥一下（减去gcd是倍数的方案数）就好了，乘一下价值就好了。

Problem C

Solved by kblack. 04:12 (+5)

题意：环上 $N$ 对狗男女，权是环上距离，求最小权匹配的大小。

题解：环上必定有至少一处没有任何狗男女经过，记狗男为 $+1$ 狗女为 $-1$ 并求前缀和 $f_i$，从 $-n$ 到 $n$ 枚举 $x$ 即是，$\sum{|f_i-x|}$ 即是最小权和，突变点一共 $n$ 个，基数维护一下就好了。

kblack: 千万不要去离散化这个突变点，两个数组合并一定要归并，但凡有半个 $log$ 你就离 T 不远了。

Problem G

Unsolved. (-6)

Problem I

Solved by kblack. 01:01 (+1)

题意：村民狼人互相指认，村民一定说实话，狼人可以胡说八道，求铁狼数量。

题解：显然，可能所有人都在胡说八道。如果指认组成一个圈，其中一项指控是狼人其他是村民，那么狼人指控的目标一定是铁狼，认为铁狼是村民的也是铁狼，也要计算在内。

Problem K

Upsolved by ultmaster. (-5)

题意：$M_n(i,j) = 1 \text{ if} \binom{i}{j} \bmod p > 0 \text{ else } 0$. $F(n,k) = \sum_{i = 0}^{p^n-1}\sum_{j=0}^{p^n-1}M_n^k(i,j)$. 求 $(\sum_{n=1}^N\sum_{k=1}^K F(n,k)) \bmod (10^9 + 7)$.

题解：打表找规律，最后发现如果枚举 $k$ 的话，是一个首项为 $q=p(p+1)\cdots(p+k)/(k+1)!$，公比也为 $q$ 的等比数列。求前 $N$ 项和即可。

ultmaster: 小学生常犯错误：等比数列求和直接套公式，从来不考虑公比为 $1$ 的情况，到最后都没看出来。（差点就有贡献了啊。。。心痛。。。

Problem L

Solved by kblack. 00:23 (+)

温暖的签到。