作者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/cn.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