#P6908. falling

    ID: 6739 传统题 3000ms 512MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>动态规划CF2300概率DP数学前缀和计数DP模拟

falling

Falling

题目描述

小象喜欢计数题,喜欢休闲计数题,于是找来了一道题。

给定序列 a1,…,an−1a_1,\ldots,a_{n-1},构造一个有 2n+22n+2 个点的无向图 GG,点的编号为 1,2,…,2n+21,2,\ldots,2n+2。按下面的代码加边:

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) 都独立地从整数 1,2,…,k1,2,\ldots,k 中等概率选一个。

求点 11 到点 2n+22n+2 的最短路长度的期望。为避免输出小数,输出

$$\operatorname E[\operatorname{dist}(1,2n+2)]\cdot\prod_{i=1}^{n-1}a_i^4\pmod{2^{32}}.$$

这个乘积是全部随机赋权方案数,因此所求也是所有赋权方案的最短路长度之和对 2322^{32} 取模的结果。

输入格式

第一行一个整数 nn。

第二行 n−1n-1 个整数 a1,…,an−1a_1,\ldots,a_{n-1}。

输出格式

输出一个整数,表示上述乘积对 2322^{32} 取模后的非负结果。

样例输入

2
2

样例输出

17

数据范围

  • 对于 10%10\% 的数据,1≤ai≤301\le a_i\le30。
  • 对于 30%30\% 的数据,1≤ai≤3001\le a_i\le300。
  • 另有 10%10\% 的数据,n=2n=2。
  • 对于全部数据,2≤n≤82\le n\le8,1≤ai≤30001\le a_i\le3000。