Chef and Tiling | CodeChef

general
1

Help with this problem please!

1 Like
2

This may help.

1 Like
3

Its matrix exponentiation.
The dp relation is trivial.
dp[x]=2 \times (dp[x-1]+dp[x-2])
To convert it into matrix
\begin{bmatrix} dp[x] & dp[x+1] \end{bmatrix} \times \begin{bmatrix} a & b \\ c& d \end{bmatrix} = \begin{bmatrix} dp[x+1] & dp[x+2]\end{bmatrix}
Using this we get
a \times dp[x] + c \times dp[x+1]=dp[x+1]
b \times dp[x] + d \times dp[x+1] = dp[x+2]
therefore
a=0, b= 2, c=1,d=2
We also know dp[0]=1\ \&\ dp[1]=2
Now ans will be
\begin{bmatrix} dp[0] & dp[1] \end{bmatrix} \times \begin{bmatrix} 0 & 2 \\ 1& 2 \end{bmatrix}^n = \begin{bmatrix} dp[n] & dp[n+1]\end{bmatrix}
and therefore find dp[n].
If need be, then use this

struct matrix{
    vector<vector<ll>> mat;
    matrix(int n, int m){
        mat.resize(n,vector<ll>(m));
    }
    matrix operator*(matrix a){
        matrix ans(this->mat.size(),a.mat[0].size());
        for(int i=0;i<this->mat.size();i++){
            for(int j=0;j<a.mat[0].size();j++){
                for(int k=0;k<a.mat.size();k++){
                    ans.mat[i][j]+=this->mat[i][k]*a.mat[k][j];
                    ans.mat[i][j]%=p;
                }
            }
        }
        return ans;
    }
};

for matrix multiplication.

6 Likes
4

@everule1
Thanks for the explanation as I was also stuck in this problem. After the contest ended, and I was going through the accepted solutions I saw some magical matrix appear in each one of them and had no idea what it was. I searched google but was unable to find the keywords for it. Thanks!! this helped me alot. :smiley:

2 Likes
5

what is difference btw line a.mat[0].size() and a.mat.size() ?

6

There’s no difference in this example, but a.mat
size() is the number of rows, and a.mat[0].size() is the number of columns.

7

Thanks for replying ,I mean since You need no of rows of matrix a and no of column of matrix a
so why you include row of first matrix mat and column of first matrix mat

8

in matrix multiplication of A*B no. of columns of ‘A’ needs to be equal to no. of rows of ‘B’.

9

so you should better write it mat[0].size() only why a.mat[0].size(); ?

10

I don’t think you understand. mat is an element of a struct, you can’t have an empty reference. It’s like writing .first It means nothing.

11

okay okay

12

in given problem, the answer is a recurrence relation
t(n) = 2t(n-1) + 2t(n-2)
if you smartly observe the sequence

below give link will help you find nth term of any recurrence relation

further consider this article it will help u get the final answer