The Unlucky 13 (HackerEarth)

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.

1 Like

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.

\begin{bmatrix} 1 & 1 \end{bmatrix}\times \begin{bmatrix} 9 & 8 \\ 1 & 1 \end{bmatrix}^{n-1}

Thanks buddy :blush:

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. :smile:

Please explain. I am not able to understand.

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.


#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;
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
p = p>>1;
return id;
void solve(){
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;
while (t–){


@fub_123 If you want to learn more about matrix exponentiation, there’s a good series by errichto on youtube codechef’s DSA series also discusses the logic behind in for 15-20 mins I guess, and a question set on codeforces handling these questions, matrix exponentiation helps in scenarios where you want to find recursive solutions;( DP sometimes fails in those scenarios, you can check by simplest example if you want to find Nth Fibonacci number where N<=1e18.
PS: I am also not very well versed in this as well, as I’ve not come across these questions much.Thanks.

can somebody help me I didn’t quite get it?