这个问题一开始想的是首先就是要确定零食蔬菜的顺序，之后在算种类。其实正确解法是递推，即每一个食物是蔬菜还是零食可以由前两个的种类决定。 设0代表零食，1代表蔬菜，那么前两种食物的种类我们有四种选择，也就是00， 01， 10， 11 这时往后选择食物，种类就要由前面的两种决定，如果出现00，就只能是1 情况如下： 1 2 \space \space\space 2 3 0 0 -> 0 1 0 1 -> 1 0 0 1 -> 1 1 1 0 -> 0 0 1 0 -> 0 1 1 1 -> 1 0 1 1 -> 1 1 即
[ 00 01 10 11 ] = [ 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 ] ∗ [ 00 01 10 11 ] \begin{bmatrix} 00 \\ 01 \\ 10 \\ 11 \end{bmatrix}=\begin{bmatrix} 0&0&1&0\\ 1&0&1&0\\ 0&1&0&1\\ 0&1&0&1\\ \end{bmatrix}*\begin{bmatrix} 00 \\ 01 \\ 10 \\ 11 \end{bmatrix} ⎣⎢⎢⎡00011011⎦⎥⎥⎤=⎣⎢⎢⎡0100001111000011⎦⎥⎥⎤∗⎣⎢⎢⎡00011011⎦⎥⎥⎤
由于0有a种，1有b种，所以
[ 00 01 10 11 ] = [ 0 0 a 0 b 0 b 0 0 a 0 a 0 b 0 b ] ∗ [ 00 01 10 11 ] \begin{bmatrix} 00 \\ 01 \\ 10 \\ 11 \end{bmatrix}=\begin{bmatrix} 0&0&a&0\\ b&0&b&0\\ 0&a&0&a\\ 0&b&0&b\\ \end{bmatrix}*\begin{bmatrix} 00 \\ 01 \\ 10 \\ 11 \end{bmatrix} ⎣⎢⎢⎡00011011⎦⎥⎥⎤=⎣⎢⎢⎡0b0000abab0000ab⎦⎥⎥⎤∗⎣⎢⎢⎡00011011⎦⎥⎥⎤
前两个零食的方法数是递推边界,为
[ 00 01 10 11 ] = [ a 2 a b a b b 2 ] \begin{bmatrix} 00 \\ 01 \\ 10 \\ 11 \end{bmatrix}=\begin{bmatrix} a^2\\ ab\\ ab\\ b^2 \end{bmatrix} ⎣⎢⎢⎡00011011⎦⎥⎥⎤=⎣⎢⎢⎡a2ababb2⎦⎥⎥⎤
从第三个 i = 3 i=3 i=3开始，为
[ 00 01 10 11 ] = [ 0 0 a 0 b 0 b 0 0 a 0 a 0 b 0 b ] i − 2 ∗ [ a 2 a b a b b 2 ] \begin{bmatrix} 00 \\ 01 \\ 10 \\ 11 \end{bmatrix}=\begin{bmatrix} 0&0&a&0\\ b&0&b&0\\ 0&a&0&a\\ 0&b&0&b\\ \end{bmatrix}^{i-2}*\space\space\begin{bmatrix} a^2\\ ab\\ ab\\ b^2 \end{bmatrix} ⎣⎢⎢⎡00011011⎦⎥⎥⎤=⎣⎢⎢⎡0b0000abab0000ab⎦⎥⎥⎤i−2∗ ⎣⎢⎢⎡a2ababb2⎦⎥⎥⎤
代码如下：
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #define ll long long using namespace std; const ll mod = 1e9+7; struct Matrix{ ll m[4][4]; Matrix(){ memset(m, 0, sizeof(m)); } void unitial(){ for(int i = 0; i < 4; i++) m[i][i] = 1; } Matrix operator* (const Matrix& b) const { Matrix ans; for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) for(int k = 0; k < 4; k++) ans.m[i][j] = (ans.m[i][j] + m[i][k]*b.m[k][j] % mod) % mod; return ans; } }; Matrix my_pow(const Matrix& x, ll b){ Matrix ans, a = x; ans.unitial(); while(b){ if(b&1) ans = ans * a; a = a * a; b >>= 1; } return ans; } int main(){ ll n, a, b; while(~scanf("%lld%lld%lld", &n, &a, &b)){ if(n == 0) printf("%lld\n", 0); else if(n == 1) printf("%lld\n", (a+b)%mod); else{ Matrix ans; ll k[4][4] = {0, 0, a, 0, b, 0, b, 0, 0, a, 0, a, 0, b, 0, b}; memcpy(ans.m, k, sizeof(k)); ans = my_pow(ans, n-2); Matrix tmp; ll kk[4][4] = {a*a%mod, 0, 0, 0, a*b%mod, 0, 0, 0, a*b%mod, 0, 0, 0, b*b%mod, 0, 0, 0}; memcpy(tmp.m, kk, sizeof(kk)); ans = ans*tmp; ll sum = 0; for(int i = 0; i < 4; i++){ sum = (sum + ans.m[i][0] + mod) % mod; } printf("%lld\n", sum); } } return 0; }