0829 upc训练小静的零食 矩阵快速幂

tech2022-10-24  106

这个问题一开始想的是首先就是要确定零食蔬菜的顺序,之后在算种类。其实正确解法是递推,即每一个食物是蔬菜还是零食可以由前两个的种类决定。 设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=010000111100001100011011

由于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=0b0000abab0000ab00011011

前两个零食的方法数是递推边界,为

[ 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=0b0000abab0000abi2  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; }
最新回复(0)