Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

我的理解

Posted by vici at 2010-08-21 02:45:01 on Problem 3734 and last updated at 2010-08-21 02:46:43
In Reply To:Re:雁过留声——矩阵乘法是王道 Posted by:HeClover at 2009-08-09 10:45:09

2 1 1 0
1 2 0 1
1 0 2 1
0 1 1 2

（已知red和green必须为偶 yellow和blue随意）

矩阵第一行代表red和green均为偶的种数（情况1）
    第二行代表red为奇 green为偶的种数（情况2）
    第三行代表red为偶 green为奇的种数（情况3）
    第四行代表red和green均为奇的种数（情况4）

然后构造转移矩阵  矩阵（N-1） -> 矩阵（N）
以第一行（情况1）来举例：
（1，1）：可以由(N-1)个砖的情况1 添加yellow或blue构成
（1，2）：可以由(N-1)个砖的情况2 添加1个red构成 
（1，3）：可以由(N-1)个砖的情况3 添加1个green构成
（1，4）：无论如何都不能由(N-1)个砖的情况4构成 所以为0

其他行类似可推出