#P6908. falling
falling
Falling
题目描述
小象喜欢计数题,喜欢休闲计数题,于是找来了一道题。
给定序列 ,构造一个有 个点的无向图 ,点的编号为 。按下面的代码加边:
add_edge(1, 1 * 2 + 0, 0);
add_edge(1, 1 * 2 + 1, 0);
for (int i = 1; i < n; ++i) {
add_edge(i * 2 + 0, (i + 1) * 2 + 0, rand_int(a[i]));
add_edge(i * 2 + 0, (i + 1) * 2 + 1, rand_int(a[i]));
add_edge(i * 2 + 1, (i + 1) * 2 + 0, rand_int(a[i]));
add_edge(i * 2 + 1, (i + 1) * 2 + 1, rand_int(a[i]));
}
add_edge(n * 2 + 0, n * 2 + 2, 0);
add_edge(n * 2 + 1, n * 2 + 2, 0);
其中 add_edge(from, to, cost) 表示加入一条连接 from 和 to、边权为 cost 的无向边。每次 rand_int(k) 都独立地从整数 中等概率选一个。
求点 到点 的最短路长度的期望。为避免输出小数,输出
$$\operatorname E[\operatorname{dist}(1,2n+2)]\cdot\prod_{i=1}^{n-1}a_i^4\pmod{2^{32}}.$$这个乘积是全部随机赋权方案数,因此所求也是所有赋权方案的最短路长度之和对 取模的结果。
输入格式
第一行一个整数 。
第二行 个整数 。
输出格式
输出一个整数,表示上述乘积对 取模后的非负结果。
样例输入
2
2
样例输出
17
数据范围
- 对于 的数据,。
- 对于 的数据,。
- 另有 的数据,。
- 对于全部数据,,。