PTT數位生活區 / C_and_CPP (C/C++)

[問題] codeforces #447 problem B

看板C_and_CPP (C/C++)作者 (Lynx)時間8年前 (2017/11/20 09:45), 8年前編輯推噓8(9推 1噓 12→)
留言22則, 5人參與, 8年前最新討論串1/1
問題連結: http://codeforces.com/contest/894/problem/B 總之就是給定矩陣大小 n * m (n列, m行) 和 k (1 或 -1) 每一列和每一行的乘積都必須要是 k 請問矩陣可以有幾種填法 ==================================== 我一開始的想法是 先從第一列填到倒數第二列, 每一列都確保乘積是k, 所以如果 k = 1, 就確保有偶數個 -1, 那就是 C(m, 0) + C(m, 2)... 每一列的組合基本上都是這樣, 所以一直給他乘, 算出前 n - 1 列的組合: (C(m, 0) + C(m, 2) + ... ) ^ (n - 1) 然後因為剩下最後一列, 已經只有一個選擇了, 就乘1 (決定前 n - 1 列等於決定第n列, 因為每一行乘積都要是k) 但這樣的算法在這題完全沒用, 因為 n 跟 m 的範圍極大 ( <= 10^18 ) 然後答案要 mod 10^9 + 7 但是組合數量要用到除法, 不可以用餘數運算, 所以應該是用動態規劃之類的, 但是想不太到QQ (C版首發, 其實不知道能不能問這類問題, 有違反版規請鞭QQ) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.176.218.28 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1511142306.A.2A2.html
推
11/20 10:35, 8年前 , 1F
先填左上(n-1)*(m-1),這樣會對應到一組解 所以答案
11/20 10:35, 1F
→
11/20 10:35, 8年前 , 2F
是 2^(n-1)*(m-1)
11/20 10:35, 2F
歐歐對欸~同樣的想法其實再把他套在"列"上就可以了 等等來試試看 ※ 編輯: GYLin (180.176.218.28), 11/20/2017 10:40:28
推
11/20 12:50, 8年前 , 3F
有prob_solve專版，雖然有點冷清，不過有駐站人員
11/20 12:50, 3F
推
11/20 12:53, 8年前 , 4F
而且這種一看就知道一定是dp
11/20 12:53, 4F
要弄成dp也不是不可, 不過這題其實是要用數學解搭配Mod Exponentiaition XD 那一長串的C加總其實可以帶二項式定理orz
推
11/20 13:15, 8年前 , 5F
不過要注意奇偶性問題
11/20 13:15, 5F
就先check過特殊情況這樣吧~(列或行只有一行得狀況) ※ 編輯: GYLin (180.176.218.28), 11/20/2017 15:03:45
推
11/21 01:01, 8年前 , 6F
快速冪弄一下就好了(那場好血腥
11/21 01:01, 6F
推
11/21 01:03, 8年前 , 7F
話說你都列出C(m, 0)+C(m, 2)+...了，那其實那串直接就是2
11/21 01:03, 7F
→
11/21 01:03, 8年前 , 8F
^(m-1)，因為C(m, 0)+C(m, 1)+...+C(m, m)=2^m
11/21 01:03, 8F
嗚嗚犯傻了QQ 那陀就二項式定理的小變形沒錯
推
11/21 01:22, 8年前 , 9F
這個看起來應該沒辦法用動態規劃解
11/21 01:22, 9F
→
11/21 01:22, 8年前 , 10F
┌ + + - + - ┐
11/21 01:22, 10F
→
11/21 01:22, 8年前 , 11F
存在 A = │ + + + + + │ 使 A(1:2, 1:4) 不滿足
11/21 01:22, 11F
→
11/21 01:22, 8年前 , 12F
└ + + - + - ┘
11/21 01:22, 12F
→
11/21 01:23, 8年前 , 13F
應該就只是單純的二項式總和為冪次
11/21 01:23, 13F
→
11/21 01:26, 8年前 , 14F
還是真的能用DP解但是我還沒想出來 O.O?
11/21 01:26, 14F
似乎可以開一個陣列dp[i][j] 表示 i列j行矩陣的解, 應該找得出遞迴式, dp[i][j] = dp[i][j - 1] * 2^i 之類的? 不過好像很沒必要 世說 nm 給那麼大也很明顯也不能用DP QQ
噓
11/21 08:30, 8年前 , 15F
看不懂版規?
11/21 08:30, 15F
→
11/21 08:30, 8年前 , 16F
還是色盲看不到黃色的字?
11/21 08:30, 16F
抱歉QQ 下次會盡量PO跟C++有關der問題
推
11/21 09:30, 8年前 , 17F
對了，算冪次方也有也有O(lg次方數)的快速解喔，可
11/21 09:30, 17F
→
11/21 09:30, 8年前 , 18F
自行google閱讀學習，概念可是非常容易
11/21 09:30, 18F
推
11/21 09:39, 8年前 , 19F
以前刷題的時候看到mod一個很大數字就代表有特殊解
11/21 09:39, 19F
→
11/21 09:39, 8年前 , 20F
法，但現在一時忘了
11/21 09:39, 20F
→
11/21 09:49, 8年前 , 21F
現在才看到一樓正解，這題的確是用快速冪，O(lg10^
11/21 09:49, 21F
→
11/21 09:49, 8年前 , 22F
36)=O(lg2^108)=O(108)，可是非常快速
11/21 09:49, 22F
應該就是先換成二進位再去算吧 ※ 編輯: GYLin (180.176.218.28), 11/22/2017 23:18:37
‣ 更多 GYLin 的文章
文章代碼(AID): #1Q4ZEYAY (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 GYLin 的文章
文章代碼(AID): #1Q4ZEYAY (C_and_CPP)