Please Help me in solving The Unlucky 13 question on the link I provided.I am thinking it in terms of recursion but the value of n is huge to memoize the solution.

Seems like a simple PnC problem. Example for 2 : 10c1*10c1 - 1 = 99. Will ping you after I code this up.

PS: Calculation doesn’t seem to be easy. Gotta find a way make it simpler.

Have u solved the question?

Do you know matrix multiplication?

Let dp_{i,j} be the number of valid strings of length i such that the last character is j.

We can notice dp_{i,j} = \sum dp_{i-1,k} where k sums over all the numbers from 0 to 9.

The only special case is j=3, in which case k does not contain 1.

Now we can notice that dp_{i,j} is equal for all j!=3.

So let dp_{i,0} be the value of dp_{i,j} for j!=3, and dp_{i,1} as the number of strings with length one that end with 3(dp_{i,3}).

Now using our redefined states,

dp_{i,0} = 9\times dp_{i-1,0} + dp_{i-1,1}

dp_{i,1} = 8\times dp_{i-1,0} + dp_{i-1,1}.

Now this can be computed with basic matrix exponentiation.

## matrix

Thanks buddy

Can u plz suggest some good resources to learn where to apply matrix exponentiation.

Yes I also want it. If you get it. Plz send me too. Thnx in advance.

Please explain. I am not able to understand.

@shobhit01

For large N such recurrences can be solved using Matrix Exponentiation. Let us denote characters ending with {0,2,3,4,5,6,7,8,9} as happy states (H) and character ending with {1} as sad(S).

For the number to be valid, we don’t want a 3 after the sad state i.e. after {1}. Let the current states be H(n-1) and S(n-1). There are 9 ways to transition from H(n-1) to H(n) (i.e.{0,2,3,4,5,6,7,8,9}) and 8(i.e.{0,2,4,5,6,7,8,9}) ways to transition from S(n-1) to S(n). There is only 1(i.e.{1}) way to transition from H(n-1) to S(n) and 1(i.e.{1}) way to transition from S(n-1) to S(n).

So we get something like :

9 *H(n-1) + 8* S(n-1) = H(n)

1 *H(n-1) + 1* S(n-1) = S(n) , S(1) = H(1) = 1

So [[9 8] * [H(n-1)]= [H(n)]

[1 1]] * [S(n-1)]= [S(n)]

This is a basic matrix exponentiation with can be done in log(n). So the overall complexity is (M^3 * log(n)) where M is size of matrix(here it is 2).

**Here is the code for reference.**

#include<bits/stdc++.h>

#define ll long long

#define rep(i,k) for (int i = 0 ; i<k ; i++)using namespace std;

ll n;

const int mod = 1e9+9;

struct Matrix{

vector<vector>a = vector<vector>(2,vector(2,0));

Matrix operator*(const Matrix& other){

Matrix res;

rep(i,2){

rep(j,2){

rep(k,2){

res.a[i][k] += a[i][j] * other.a[j][k];

res.a[i][k] %= mod;

}

}

}

return res;

}

};Matrix expo_power(Matrix single,ll p){

Matrix id;

rep(i,2)id.a[i][i] = 1;

while (p>0){

if (p & 1)id = idsingle;single;

single = single

p = p>>1;

}

return id;

}

void solve(){

cin>>n;

Matrix single;

single.a[0][0] = 9;

single.a[0][1] = 1;

single.a[1][0] = 8;

single.a[1][1] = 1;`Matrix ans = expo_power(single,n); cout<<(ans.a[0][0] + ans.a[0][1])%mod<<endl;`

}

int main(){

int t;

cin>>t;

while (t–){

solve();

}

}