作者GYLin (Lynx)
看板C_and_CPP
標題[問題] codeforces #447 problem B
時間Mon Nov 20 09:45:02 2017
問題連結:
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://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1511142306.A.2A2.html
1F：推 spentplaying: 先填左上(n-1)*(m-1),這樣會對應到一組解 所以答案 11/20 10:35
2F：→ spentplaying: 是 2^(n-1)*(m-1) 11/20 10:35
歐歐對欸~同樣的想法其實再把他套在"列"上就可以了
等等來試試看
※ 編輯: GYLin (180.176.218.28), 11/20/2017 10:40:28
3F：推 alan23273850: 有prob_solve專版，雖然有點冷清，不過有駐站人員 11/20 12:50
4F：推 alan23273850: 而且這種一看就知道一定是dp 11/20 12:53
要弄成dp也不是不可, 不過這題其實是要用數學解搭配Mod Exponentiaition XD
那一長串的C加總其實可以帶二項式定理orz
5F：推 spentplaying: 不過要注意奇偶性問題 11/20 13:15
就先check過特殊情況這樣吧~(列或行只有一行得狀況)
※ 編輯: GYLin (180.176.218.28), 11/20/2017 15:03:45
6F：推 oToToT: 快速冪弄一下就好了(那場好血腥 11/21 01:01
7F：推 oToToT: 話說你都列出C(m, 0)+C(m, 2)+...了，那其實那串直接就是2 11/21 01:03
8F：→ oToToT: ^(m-1)，因為C(m, 0)+C(m, 1)+...+C(m, m)=2^m 11/21 01:03
嗚嗚犯傻了QQ 那陀就二項式定理的小變形沒錯
9F：推 Hazukashiine: 這個看起來應該沒辦法用動態規劃解 11/21 01:22
10F：→ Hazukashiine: ┌ + + - + - ┐ 11/21 01:22
11F：→ Hazukashiine: 存在 A = │ + + + + + │ 使 A(1:2, 1:4) 不滿足 11/21 01:22
12F：→ Hazukashiine: └ + + - + - ┘ 11/21 01:22
13F：→ Hazukashiine: 應該就只是單純的二項式總和為冪次 11/21 01:23
14F：→ Hazukashiine: 還是真的能用DP解但是我還沒想出來 O.O? 11/21 01:26
似乎可以開一個陣列dp[i][j] 表示 i列j行矩陣的解, 應該找得出遞迴式,
dp[i][j] = dp[i][j - 1] * 2^i 之類的?
不過好像很沒必要
世說 nm 給那麼大也很明顯也不能用DP QQ
15F：噓 Ommm5566: 看不懂版規? 11/21 08:30
16F：→ Ommm5566: 還是色盲看不到黃色的字? 11/21 08:30
抱歉QQ 下次會盡量PO跟C++有關der問題
17F：推 alan23273850: 對了，算冪次方也有也有O(lg次方數)的快速解喔，可 11/21 09:30
18F：→ alan23273850: 自行google閱讀學習，概念可是非常容易 11/21 09:30
19F：推 alan23273850: 以前刷題的時候看到mod一個很大數字就代表有特殊解 11/21 09:39
20F：→ alan23273850: 法，但現在一時忘了 11/21 09:39
21F：→ alan23273850: 現在才看到一樓正解，這題的確是用快速冪，O(lg10^ 11/21 09:49
22F：→ alan23273850: 36)=O(lg2^108)=O(108)，可是非常快速 11/21 09:49
應該就是先換成二進位再去算吧
※ 編輯: GYLin (180.176.218.28), 11/22/2017 23:18:37