剛剛沒貼好抱歉

這題的解題思路是矩陣運算

首先我們可以把題目看成

起始    | 女生數量：a    |   男生數量：b

-------------------------------------------------

第一天 |      a+b         |      a

-------------------------------------------------

第二天 |      2a+b       |     a+b

-------------------------------------------------

第三天 |     3a+2b      |     2a+b

-------------------------------------------------

第四天 |     5a+3b      |     3a+2b

.

.

.

所以我們可以把數列看成 |   a   b   |   a+b   a   |   2a+b   a+b   |   3a+2b   2a+b   |......

我們可以找到一個矩陣A=|   1   1   |   (如何推導，我這裡就不多敘述了)

                                |   1   0   |

A * 數列的一個區塊 = 下一個區塊

ex .

A * |   2a+b   | = |   3a+2b   |

      |   a+b     |    |   2a+b     |

所以

A*數列第 i 個區塊 = 數列第 i+1 個區塊

我們還可以觀察到

(A^n)*數列第 1 個區塊 = 數列第 1+n 個區塊

所以題目給了我們初始的區塊，將A*A*A*....*A k次後在乘上初始的區塊就是答案

但k可能很大

所以最好的做法是

  (請把n當成k)

最後別忘了矩陣的數字要mod(100000007)

將(A^k)*初始區塊後的結果即為第k天後女與男的數量

將這兩個數字相加取mod即為答案

在寫這一題時建議可以先做做看d639: 企鵝村三兄弟penguin