問題連結: 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)

這個看起來應該沒辦法用動態規劃解┌ + + - + - ┐存在 A = │ + + + + + │ 使 A(1:2, 1:4) 不滿足└ + + - + - ┘應該就只是單純的二項式總和為冪次還是真的能用DP解但是我還沒想出來 O.O?

不過要注意奇偶性問題

快速冪弄一下就好了(那場好血腥話說你都列出C(m, 0)+C(m, 2)+...了，那其實那串直接就是2^(m-1)，因為C(m, 0)+C(m, 1)+...+C(m, m)=2^m

先填左上(n-1)*(m-1),這樣會對應到一組解 所以答案是 2^(n-1)*(m-1)

有prob_solve專版，雖然有點冷清，不過有駐站人員而且這種一看就知道一定是dp

看不懂版規?還是色盲看不到黃色的字?

對了，算冪次方也有也有O(lg次方數)的快速解喔，可自行google閱讀學習，概念可是非常容易以前刷題的時候看到mod一個很大數字就代表有特殊解法，但現在一時忘了現在才看到一樓正解，這題的確是用快速冪，O(lg10^36)=O(lg2^108)=O(108)，可是非常快速