期望技巧

内容来自Errichto期望讲座part1和part2.
有两个重要的内容：
1.期望线性性
2.contribution technique
这里主要总结第二点。
https://codeforces.com/blog/entry/62690
https://codeforces.com/blog/entry/62792
part I

流坑

part II
其实还有两个技巧：
power technique和ordered pair technique
1.Inflation 2 The price of a tv is 1000$. Each of the next N days, the prices goes up by 1% or 2% (each with p-bility 50%). Find EV of the final price.

2.Square of wins You bought N (N ≤ 105) lottery tickets. The i-th of them is winning with p-bility pi. The event are independent (important!). Find EV of the square of the number of winning tickets.

裸的做法：
double ans  =0;
p(i,j):
{
   i!=j: p[i]*p[j];
   i==j: p[i]    
}

for(int i =0;i<n;i++)
    for(int j =0;j<n;j++)
        ans+= p(i,j) * 1;
不裸的做法：
S = p[0] + p[1] + .. + p[n-1]
for(int i =0;i<n;i++){
    ans+=p[i]*(S-p[i]) + p[i];
}

3.Cube of wins Same but find EV of the 3-rd or 4-th power.

3rd power:
p(i,j,k) = {
    比方i,j,k都不同：p(i)*p(j)*p(k)
    i和j相同,和k不同:p(i)*p(k)
    i和j和k都相同:p(i)
}

for(int i =0;i<n;i++){
    for(int j =0;j<n;j++){
        for(int k =0;k<n;k++){
            ans += p(i,j,k)
        }
    }
}
类似做法，都能降到O(n)

4.Bulbs There are N (N ≤ 50) light bulbs and M (M ≤ 50) switches. For every switch, we know a set of bulbs such that its state is flipped (on to off, off to on) when the switch is clicked. All bulbs are off, and then we click each switch with p-bility 50%. Find EV of the cube of the number of bulbs that are on.

遍历triple
选定其中三个下标的状态a,b,c
然后dp[a][b][c]，初始状态dp[0][0][0]=1
然后状态转移求出dp[1][1][1]
ans += dp[1][1][1] （contribution technique O(n^3*8*m)）

5. Sum-length Given a sequence of length N (N ≤ 105), find the sum over sum·len3 over all intervals. Print the answer modulo 109 + 7.
   There are a few possible solutions.

   solution 1
   contribution technique
   for(int b  =0;b<n;b++){
    for(int a= 0;a<b;a++){
        for(int c = b;c<n;c++){
            ans += x*(c-a+1)^3;
        }
    }
   }
   另外，设置左边长度为L,右边长度为R,原来(c-a+1)^3变成了(L+R)^3,预处理可以O(n)解法
   solution2
   对于每个长度len,求sum，再累加。
   solution3

   

意思就是要先选个起始点和结束点，然后在这个区间内选出三个点，便转化成为如下
ans+= 左边选一个，并且右边选4个的方案数
      +左边选2个，并且右边选3个的方案数
      +左边选3个,并且右边选2个的方案数
      。。。。

（记住这里的选是可重复选： ）
6. Small power of subtree You're given a tree of size N (N ≤ 105) and an integer k (k ≤ 10). Find the sum of sizek over all "subtrees", i.e. connected subgraphs. Print the answer modulo 109 + 7.

solution
先统计每个sub部分，然后再把我parent分配到那些个sub部分，所以会有C(i+j-1,j)这些东西来merge
dp[root][k]就是最后的答案

题外题：给定一颗树,求path长度的平方和

要学会用低的power来更新高的power，比如如下图就是自底向上更新。

7.DoubleLive (Topcoder SRM 727) Your army consists of B + H soldiers: B bears and H humans (B, H ≤ 2000). A bear has two hit points, a human has one hit point.
The enemy archer has T arrows (T ≤ 2·B + H). Every next arrow will hit a random alive soldier in your army, taking one hit point. When someone has zero hit points, he dies.
The strength of your army is defined as bears·humans·all, e.g. 3·7·10 = 210 for an army of 3 bears and 7 humans. It doesn't matter if some bears have only one hit point.
Find the EV of the strength of your army after the enemy archer uses all his arrows.

dp[B1][B2][H]
=>dp[one][two][0/1][0/1/2]*B*H*(one+two)
意思就是选定个特定的B和H去更新答案,所以要*B*H