问题连结: 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)，可是非常快速