[問題] codeforces #447 problem B

[GYLin (Lynx)]

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