矩阵快速幂刷过。。。

回复 @cstdio :
O(1)hash容易被卡，还是O(log)级别的稳定，只要把底数搞的大一点也不会常数太大
Orz cstdio的插头dp写法，以后联通块插头dp就这么写了

矩阵快速幂两个变量打反WA了N次。。。

BZOJ 2003839 ccc000111 2002 Accepted 4424 kb 1928 ms C++/Edit 1528 B 2017-04-15 10:33:47
这里呢。。。
同样代码 垃圾评测机
虽说时间不一样，但是这个E是什么情况。。。
UPD：这不科学……
重打一遍就对了……代码一模一样……
这不科学……
UPDD：好吧……
我脑残，没有想到修改后跳出去的情况……
不过这数据真的淼的不行，根本没想到这个都过了八个点……BZOJ直接过了，害得我裱了一顿评测姬……

神奇建图

记忆化搜索水过

维护子树信息等于模板+4行。。。。

本地跑和评测机跑的不一样。醉3A.

回复 @周 :
[ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ] [ [] ]

回复 @周 :
esfsefwe

回复 @cstdio :
翻车了……
WA1：手残打反变量名
WA2：倒序加边忘记把端点改成bcc标号

提示里面"wys"的意思是希望你使用上一个数据的算法+wys优化通过这一测试点。
放心，我开的标程3倍时限，绝对不卡常，这样做只是鼓励下暴力+卡常玩家而已。。
话说标程用的cin,cout会不会被嫌弃呢？(实际上是因为造数据的电脑视64位机，我却用32dev...)

回复 @cstdio :
被逆元搞的晕头转向，求了五个正变换和两个逆变换……

回复 @konicy : 我先站内私信给你说一下这个的模型
http://i1.buimg.com/538184/200ef278b1a0ea95.png
迭代求得上面数字0的那个节点的期望次数x0到收敛，然后递推出来后面的节点的期望执行次数，然后算出来概率，然后算出来期望。
题面翻车了，抱歉。
这个脑洞留下了好了= =

回复 @萌萌的叶子姐��的脑残粉 :
我好像依然没有理解= =
选择不回答这个是随机的吗？
我用您的代码测试了一下1 1 2 2，结果是0.66667=2/3
所以是1/3的概率不回答，1/3的概率答对，1/3的概率答错？ 这样期望确实是0.66667,然后我测试2 1 2 2 1 2 2结果是1.14286=8/7这个我想不通是怎么算的了。。。。
而且如果随机选择回答不回答。应该是0.5选择不回答，0.5选择回答，然后在分对错的情况吧。。。这样我就算不出来0.66667了。。。。。
还是说每次选择回答不回答要根据当前局面决定。。。。。。。。
2
1 2 2
1 2 2
假如对，错，不答，概率按1/3算
答错 0
不答 0
答对->不答 1/3*1/3*2=2/9
答对->答错 0
答对->答对 1/3*1/3*(2+2)=4/9
期望2/9+4/9=2/3=0.66667。。。。我可能学了假的期望。。。

@konicy 啊，是的，忘了写上不回答直接结束这个过程的情况了..,sorry，已改。

人脑跑不出样例。。。
答错了一道长者不就离开了，然后把续的秒都还给你了么。。。
那不是全部答对才可以真正续上嘛。。。。
样例不应该是0.5*0.5*0.5*（2+4+8）=1.75吗。。。。。

样例:

1 1 2 2 2 2 3 3 3

 l r l r

没加读入优化就上榜了？？