問題描述 Description

小明喜歡玩一些智力游戲。假設有一個一維棋盤，在該棋盤上從左至右共有N+1$N+1$個格子，編號從0$0$到N$N$。小明有一個棋子，最初在編號為0$0$的格子中。他每次擲兩個骰子，每個骰子都有六個面，而且擲到每個面的概率都相同，骰子的點數分別是1,2,3,4,5,6$1,2,3,4,5,6$。 當棋子在編號為a$a$的格子中時，擲到的兩個骰子點數分別是x$x$和y$y$，那么棋子將會移動到編號為a+x+y$a+x+y$ 的格子中。當a+x+y$a+x+y$大于或等于N$N$的時候，小明就結束游戲。 小明是一個比較喜歡偷懶的人，他不喜歡擲那么多次骰子，所以在棋盤中有M$M$條飛行線路，對于第i$i$條飛行線路來說，可以不用擲骰子直接從編號為u$u$的格子跳到編號為v$v$的格子。如果還有另一條飛行線路起點是編號v(0<u<v≤n)$v(0/lt u/lt v/le n)$ 的格子，那么小明就可以按照這條線路繼續向前跳動。保證每個格子只可以作為一條飛行路線的起點。 現在想知道完成這個游戲需要擲骰子的次數期望值是多少。

輸入 Input

第一行給出N$N$，M$M$。 接下來M$M$行，每行包括兩個整數u,v(0<u<v≤n)$u,v (0/lt u/lt v/le n)$，表示格子u$u$到格子v$v$有一條飛行線路。

輸出 Output

輸出文件包含一個整數，即相應輸入文件的答案。輸出完成這個游戲需要擲骰子的次數期望值是多少，結果保留小數點后4$4$位。

樣例輸入#1 Sample Input #1

2 0

樣例輸出#1 Sample Output #1

1.0000

樣例輸入#2 Sample Input#2

8 3 2 4 4 5 7 8

樣例輸出#2 Sample Output#2

1.4213

限制 Limits

對于30%的數據，保證1≤=N≤100,0≤M≤10$1/le=N/le 100,0/le M/le 10$。 對于60%的數據，保證1≤N≤1000,0≤M≤100$1/le N/le 1000,0/le M/le 100$。 對于100%的數據，保證1≤N≤105,0≤M≤1000$1/le N/le 10^5,0/le M/le 1000$。 Time Limit : 1s$1s$ & Memory Limit : 128MB$128MB$

半黑歷史題……期望DP（話說學校還沒講期望23333333） 如果直接從前向后推的話，因為飛行路線的存在推不了。所以倒著推，就可以避免這個問題。 所以，DP方程式為 dp[i]+=∑j=212(dp[i+j]+1)?p[j] $$/begin{equation}dp[i]+=/sum_{j=2}^{12}(dp[i+j]+1)*p[j]/end{equation}$$ 還有，題目中貌似沒說，每個格子的出度為1…… 如果有飛行路線，直接繼承終點的dp值即可。 時間復雜度O(n)$O(n)$ Code