2019,10,24 长郡 csp

考试

---

T1 ioday1

题意

有一张试卷, $n$ 道题 $(n\le 10^9)$, 每道题都有 $k$ 个选项 $(k\le 5*10^5)$,
正确答案为 $i$ 的题目有 $a_i$ 道,
小Z 的答案中, 选择了 $i$ 的题目有 $c_i$ 道,
求小Z 的分数的数学期望

方法

首先要想明白一个东西,
对于正确答案的任何一种排列方式, 获得的分数的期望值都是一定的.

这样的话, 我们就相当于得到了一份正确答案, 对这份答案求期望就行了.

对于一道答案为 i 的题, 选 i 的概率是 $\frac{c_i}{n}$, 然后答案为 i 的题有 $a_i$ 道, 所以期望为

$$\sum_{i=1}^{k}\frac{a_i*c_i}{n}$$

(考场上一分都没写出来的我...)

---

T2 paper

题意

有一张长为 $n$ 的纸条 $(n\le10^{18})$, 给定 $m$ 个位置 $(m\le10^4)$,
除了这 $m$ 个位置之外, 可以在纸条的任意位置切割,
切割后纸条会变成若干段, 要求在每一段上标记一个数 $x$,
给定 $c$ $(1\le c\le 7)$, 设某一段纸条的长度为 $l$,
要求 $l\mid x$, 且 $x\le c$,
求总方案数.
(若两种方案不同, 可以是切割方案不同, 也可以是标数方案不同)

16pts ($n^2$)

设 f[i] 为距离纸条左侧距离为 i 时的方案数,
记 num[i] 为 i 的 小于等于 c 的因子个数
每次枚举最后一段的长度, n^2 转移

$$f[i]=\sum_{k=1}^{i}f[i-k]*num[k]$$
当 i 这个位置不能选的时候直接设为 0 就好了

36pts ($nc$)

上面的转移方程可以化为

$$f[i]=\sum_{j=1}^{c}\sum_{k=1}^{k<= \lfloor \frac{i}{j} \rfloor } f[i-k*j]$$
相当于上面的是确定了长度之后算有能标多少数字
现在的是确定了标哪个数字后算有哪几种长度符合要求

然后这一坨 $\sum_{k=1}^{k<= \lfloor \frac{i}{j} \rfloor } f[i-k*j]$
可以用一个前缀和来代替,
设 $g[i][j]$ 为从 i 往前, 每 j 个位置记一个的前缀和 (有点绕)
那方程变为

$$f[i]=\sum_{j=1}^{c}g[i-j][j]$$
$$g[i][j]=g[i-j][j]+f[i]$$

矩阵优化

就是矩阵优化....
然后每次不能切的时候还要停一下

$O(m*(c^2)^3*log n )$
$c^2$ 是转移矩阵的大小
$(c^2)^3$ 是快速幂时的矩阵乘法

再优化

预处理出矩阵快速幂时矩阵 A 的每个 $2^k$ 次方
然后快速幂的时候直接把转移矩阵的每个次方乘到原矩阵上

$O(m*c^2*log n+c^2*log n)$

---

T3 oiday2

题意

给定一个大小为 $n$ 的树 $(n\le 1000)$,
现要选出 $m$ 个点, 构成一个新图, 图上两点之间的边长为 原树中两点之间的距离.
给出每个点被选为这 $m$ 个点之一的概率, 求新图的 最小生成树的边长之和 的数学 期望.

方法

若已经确定了这 $m$ 个点, 除了直接kruskal之外, 还有一种方法可以求出最小生成树:

随便选一个点作为根节点 (不一定要是这 $m$ 个点中的点), 把这 $m$ 个点按照到根节点的距离从小到大排序,
对于每个点, 从它前面的点中选取一个离它最近的点作为它的父亲.

这个方法等价于将 $m$ 个点排好序后, 每次取出最后的一个点, 把它删掉, 然后在剩下的点中找一个距离离它最近的点作为它的父亲.

可以通过反证法证明,
设当前删掉的点为 $u$, 只要证明: 对于 $u$ 前面的任意一个点 $v_i$, $v_i$ 选取 $u$ 作父亲不会比选取 $v_j$ 作父亲更优即可.
稍微画几个点就能明白, 这里就不讲了.

再考虑一般情况.
根据期望的线性性 (题解说的, 我不知道...), 我们可以求出每一个点的父边的期望值, 它们的和就是最小生成树的边权之和的期望值.

那按照刚才的策略, 同样的, 先随便选一个根节点, 然后把所有点按照到根节点的距离从小到大排序,
再对于每一个点, 把它前面的点按照到它的距离从小到大排序,
设当前点为 $u$, 它前面的点排序后为 $v_1,v_2,v_3...$,
如果 $u$ 的父亲是 $v_i$ 那么 $v_1,v_2,...,v_{i-1}$ 一定都不是 $m$ 个被选中的点之一, 否则 $u$ 的父亲就应该在它们之中,
所以 $v_i$ 的贡献就是

$$p[u]*p[v_i]*(1-p[v_1])*(1-p[v_2])*...*(1-p[v_{i-1}])*dis[u][v_i]$$

最后求个和就行了.