Problem - 1005

我们有一个圈，从内到外一共被分成了 $n$ 个环，中间是空的。我们把从外到内第 $i$ 层环平分成 $a[i]$ 份，其中 $a[i]$ 是偶数，我们把这 $a[i]$ 份黑白染色，第奇数个染成黑色，第偶数个染成白色。现在我们旋转每一层，每一层都会等概率随机到一个中止位置。问黑色的联通块数目的期望。两块黑色的区域有交点即算联通。层之间的旋转是相互独立的。

3
2
2 2
2
2 6
4
10 230 666 1000

1
2
500000256

样例解释
对于第一组样例，第一个环和第二个环各有一半是黑的，他们的黑色部分必然有交点，所以期望的联通块数目为 1。
对于第二组样例，旋转第一个环，只在几个特定角度上第一个环的黑色部分和第二个环的三个黑色部分都有交点，大部分情况下都只和两个黑色部分有交点，因为算期望，所以几个特定角度对答案没有影响，答案为 2。

Rotate