题意
你在抛硬币。其中抛到正面的概率是 (p)，请求出第一次出现连续 (k) 次正面的期望步数
解法
第一次接触期望 DP
根据题目来设状态，设 (f_i) 为第一次出现连续 (i) 次正面的期望步数
考虑掷一次硬币带来的影响：掷一个正面，可以使连续 (i-1) 次延长为连续 (i) 次；掷一次反面，可以使连续 (i-1) 次清空为 (0) 次，还需要再掷 (f_i) 次
[f_i = p imes(f_{i-1}+1)+(1-p) imes (f_{i-1}+1+f_i)
]
把这个式子化简会得到一个可以用等比数列求和优化的式子，于是就可以 (O(log N)) 求解了
代码
没什么好放的