TAPSY - EDITORIAL

editorial
,
1

PROBLEM LINK:CodeChef: Practical coding for everyone
DIFFICULTY: Medium-Hard
PREREQUISITES: Dynamic-Programming, Matrix-Exponentiation
EXPLANATION:
Let say we have to find the answer to the Query “4”.
1. if we append 1 and 4 at the end of all number having digit’s sum equals 3 then we get digit’s sum as 4.
2. if we append 2 at the end of all number having digit’s sum equals 2 then we get digit’s sum as 4.
3. if we append 3 at the end of all number having digit’s sum equals 1 then we get digit’s sum as 4.

So dp[n]=2*dp[n-1] + dp[n-2] + dp[n-3]

We can solve this by using Matrix Exponentiation

| F(4) |  =  | 2 1 1 |  *           | F(3) |
| F(3) |     | 1 0 0 |              | F(2) |
| F(2) |     | 0 1 0 |              | F(1) |

Similarily for n,

| F(n)   |  =  | a b c | * | a b c | * ... * | a b c | * | F(3) |
| F(n-1) |     | 1 0 0 |   | 1 0 0 |         | 1 0 0 |   | F(2) |
| F(n-2) |     | 0 1 0 |   | 0 1 0 |         | 0 1 0 |   | F(1) |

| F(n)   |  =  [ | a b c | ] ^ (n-3)   *  | F(3) |
| F(n-1) |     [ | 1 0 0 | ]              | F(2) |
| F(n-2) |     [ | 0 1 0 | ]              | F(1) |

Where a,b,c are 2,1,1 respectively.
We can perform (mat)^n for any matrix in Log(n) times.

SOLUTION:
(Python 3)

mat=[[2,1,1],[1,0,0],[0,1,0]]
val=[13,5,2]
mod=10**9 + 7

def matmul(a,b):
    row=len(a)
    try:
        col=len(b[0])
    except:
        col=1
    dp=[[0 for i in range(col) ] for j in range(row)]
    for i in range(row):
        for j in range(col):
            ans=0
            for k in range(len(b)):
                ans+=a[i][k]*b[k][j]
                ans%=mod
            dp[i][j]=ans
    return dp


def solve(mat1,m):
    ans=[[1,0,0],[0,1,0],[0,0,1]]

    while m>0:
        if m%2==1:
            ans=matmul(ans,mat1)
        m//=2
        mat1=matmul(mat1,mat1)
    return (ans[0][0]*val[0] + ans[0][1]*val[1] + ans[0][2]*val[2])%mod


import random as r
t=int(input())
for i in range(t):
    n=int(input())
    if n<=3:
        ans=val[-n]
    else:
        ans=solve(mat,n-3)
    print(ans)
1 Like