→ bleed1979:數字很大，記得用unsigned long long 03/03 22:25
推 adks3489:成功了 而且速度比我的果然快很多XD 非常感謝 03/04 08:28
→ adks3489:然後我發現我前面那個printf改成cout也AC了 可是不知道 03/04 08:28
→ adks3489:原因是什麼@@ 03/04 08:29
推 loveme00835:因為只要標準輸出就可以啊@@ 03/04 18:09
先來個4 x 4 array好了。
1. 首先，K = 0一定是1
0 0 1 2 3 4
1 1
2 1
3 1
4 1
2. K >= N一定是0
0 0 1 2 3 4
1 1 0 0 0 0
2 1 0 0 0
3 1 0 0
4 1 0
3. N = 2, K = 1 是 1
0 0 1 2 3 4
1 1 0 0 0 0
2 1 1 0 0 0
3 1 0 0
4 1 0
4. N = 3, K = 1 是 3
0 0 1 2 3 4
1 1 0 0 0 0
2 1 1 0 0 0
3 1 3 0 0
4 1 0
5. N = 3, K = 2 是 2
0 0 1 2 3 4
1 1 0 0 0 0
2 1 1 0 0 0
3 1 3 2 0 0
4 1 0
6. 我們來分析N = 4, K = 2
1 2 3 4
swap 1
4可以和1換，可以和2換，可以和3換，所以有3個可能
swap2
假設4和3換, swap剩1次
1 2 4 3
看前三個1 2 4，是不是變成N = 3, K = 1了
所以是3 * (N = 3, k = 1)
現在討論1 2 3 4的3
swap1
3可以和2換，可以和1換，所以有2個可能
swap2
假設3和2換，swap剩1次
1 3 2 4
看前面的1 3，是不是變成N = 2, K = 1了
所以是2 * (N = 2, K = 1)
同理2和1類推
以上所有都要加起來才是N = 4, K = 2的解
所以一個N x N array 最內圈的寫法
for (k = i - 1; k != 0; --k)
A[i][j] += k * A[k][j - 1];
外面兩圈當然是i和j的遞增
也就是說，這題速解為Dynamic Programming
所以先作precalculation，while讀入測資後直接輸出Array值
C++速度大約是0.012s, C應該可以更快
Bleed
※ 引述《adks3489 (Double C)》之銘言：
: 題號：11077
: 題目網址：http://acm.uva.es/p/v110/11077.html
: 遇到的問題：就..WA
: 有問題的code： http://codepad.org/fWDqxTjH
: 補充說明：
: 大概講一下這題目的內容，
: Input為N及K
: N是有數列長度,K是作排序的次數
: Output的要求為找出長度為N，需要K個swap來做排序的數列共有多少個
: 範例：
: N=3 數列| swap次數
: 1 2 3 | 0
: 1 3 2 | 1
: 2 1 3 | 1
: 2 3 1 | 2
: 3 1 2 | 2
: 3 2 1 | 1
: N K Output
: 3 0 | 1
: 3 1 | 3
: 3 2 | 2
: 送出去給了我WA，我也不知道該怎麼辦了
: 救救我吧
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.177.97