※ 引述《utomaya (乌托马雅)》之铭言： : ※ 引述《babufong (哔哔)》之铭言： : : 371. Licence plates : : http://projecteuler.net/problem=371 : : 俄勒冈州的车牌号码是由三个英文字母後面接着三位数字(0到9)所组成的。 : : Seth 开车去上班时，他会玩一个小游戏： : : 每当他在路途上，看到两个车牌号码的数字部分相加为 1000 时，就算胜了这场游戏。 : : (如 MIC-012 和 HAN-988，或是 RYU-500 和 SET-500，这都算胜利，只要是在同一趟 : : 车程中看到。） : : 计算出 Seth 赢得游戏所需要看到的车牌数的期望值，并将答案给到小数点後八位数。 : 一开始往马可夫链的方面去想，结果被困了好久 以下是马可夫链的解法: (顺便当防雷页) 设全部有 0 ~ n-1 的车牌要凑成 n 其中 n 为偶数 (原题为 n = 1000 的情形) 这个马可夫链中一共有 n+1 个状态 前 n 个对应於 utomaya 的 n 个 DP 格 (即前 n/2 个状态是还没看到 n/2, 後 n/2 个状态是看到了一个 n/2) 而第 n+1 个状态则是 "win" 是个吸收状态 因此题目便是要求这个马可夫链的"平均吸收次数" 先写出它的转移矩阵: 对 1≦i≦n/2, 状态 i 代表看到了 i-1 组的数字之一但没有 n/2 於是有 i 个情形停在状态 i, 有 n-2i 个情形进入状态 i+1, 有 1 个情形进入状态 i+n/2, 有 i-1 个情形进入状态 "win" 而状态 i+n/2 代表看到了 i-1 组的数字之一且有一次 n/2 於是有 i 个情形停在状态 i+n/2, 有 n-2i 个情形进入状态 i+1+n/2, 有 i 个情形进入状态 "win" (当 i = n/2 时没有进入状态 i+1+n/2 的部份, 不过这个马上可以处理) 所以它的转移矩阵长这样: [ 1 n-2 1 0 ] [ 2 n-4 1 1 ] [ 3 n-6 1 2 ] [ ... ... ... ] [ n/2-1 2 1 n/2-2 ] １ [ n/2 1 n/2-1 ] ---- [ 1 n-2 1 ] ｎ [ 2 n-4 2 ] [ 3 n-6 3 ] [ ... ... ] [ n/2-1 2 n/2-1 ] [ n/2 n/2 ] [ n ] 可以看到扣除吸收的那个状态 剩下的部份左上和右下是一样的双对角线矩阵 左下是 0 右上是 I/n 也就是这部份可以写成 Q = [ Q' I/n ] [ 0 Q' ] 参照 http://en.wikipedia.org/wiki/Absorbing_Markov_chain 我们可以计算其基本矩阵 N = (I-Q)^-1 计算结果是 N = [ (I-Q')^-1 (1/n)((I-Q')^-1)^2 ] [ 0 (I-Q')^-1 ] 而平均吸收时间即为 N 乘上 1 向量 因此题目所求即为 N 矩阵的第一列的和 於是剩下的就是计算出 (I-Q')^-1 及其平方 这也很容易 因为 I-Q' 只有两个对角线有值 因此直接以扩张矩阵 [I-Q' | I] 做倒回代换即可求得 其元素为 n j-1 n-2k A_{i,j} = --- * Π ---- , i≦j (是个上三角矩阵) n-j k=i n-k 由此 ((I-Q')^-1)^2 的元素为 n/2 B_{i,j} = Σ A_{1,k} A_{k,j} k=1 n/2 n/2 因此所求即为 Σ A_{1,j} + (1/n) Σ B_{1,j} j=1 j=1 n/2 / n/2 \ 它可以化为 Σ A_{1,k} | 1 + (1/n) Σ A_{k,j} | k=1 \ j=k / 所以程式上就先把 A 矩阵给算出来存着 (需时 O(n^3)) 再套用上面这个式子 (需时O(n^2)) 就得到答案了 我猜 utomaya 被困住应该是不知道有计算"平均吸收时间"的公式... 还是要挡一下的页末防雷页 -- ◢ ˊ_▂▃▄▂_ˋ. ◣　　　　　 　　　　▅▅　▅▅　ι●╮　　 █▄▄▄▄▄ ▍./◤_▂▃▄▂_◥ \'▊ 　　ＨＡＲＵＨＩ █████　＜■┘ 　 ▄▄▄▄▄▄▄ ▎⊿ ◤◤◥█◥◥█Δ 　　ＩＳＭ　 　　By-gamejye　￠|\ 　　▌▌▌▌▌▄▌▌ ▏ζ(▏●‵◥′●▊)Ψ ▏　　 　　　 　　　　█　　　 ⊿Δ 　　▄▄▄ ▄▄▄▄ █/|▊ 〃 、 〃▋ |\ ▎　　　　　 　 　ハルヒ主义　　　 　　█▄▄▄█▄▄ ◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための凉宫ハルヒの団　　　 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.230.62 ※ 编辑: LPH66 来自: 140.112.28.91 (02/16 16:23)