HackerRank Find the Seed problem solution

In this HackerRank Find the Seed problem solution a company needs random numbers for its operation. N random numbers have been generated using N numbers as seed and the following recurrence formula:

F(K) = (C(1) x F(K - 1) + C(2) x F(K - 2) + .... + C(N - 1) x F(K - N + 1) + C(N) x F(K - N)%(10 power to 9 + 7))

The numbers used as seeds are F(N - 1), F(N - 2),...., F(1), F(0). F(K) is the Kth term of the recurrence. due to failure on the servers, the company lost its seed numbers. now they just have the recurrence formula and the previously generated N random number. the company wants to recover the numbers used as seeds.

Problem solution in Python.

MOD = 1000000007

def generalizedEuclidianAlgorithm(a, b):
    if b > a:
        return generalizedEuclidianAlgorithm(b,a);
    elif b == 0:
        return (1, 0);
    else:
        (x, y) = generalizedEuclidianAlgorithm(b, a % b);
        return (y, x - (a // b) * y)

def inversemodp(a, p):
    a = a % p
    if a == 0:
        return 0
    (x, y) = generalizedEuclidianAlgorithm(p, a % p);
    return y % p

def identitymatrix(n):
    return [[int(x == y) for x in range(0, n)] for y in range(0, n)]

def multiply_vector_scalar(vector, scalar, q):
    kq = []
    for i in range (0, len(vector)):
        kq.append(vector[i] * scalar % q)
    return kq

def minus_vector_scalar1(vector1, scalar, vector2, q):
    kq = []
    for i in range (0, len(vector1)):
        kq.append((vector1[i] - scalar * vector2[i]) % q)
    return kq

def inversematrix1(matrix, q):
    n = len(matrix)
    A =[]
    for j in range (0, n):
        temp = []
        for i in range (0, n):
            temp.append(matrix[j][i])
        A.append(temp)
    Ainv = identitymatrix(n)
    for i in range(0, n):
        factor = inversemodp(A[i][i], q)
        A[i] = multiply_vector_scalar(A[i], factor, q)
        Ainv[i] = multiply_vector_scalar(Ainv[i], factor, q)
        for j in range(0, n):
            if i != j:
                factor = A[j][i]
                A[j] = minus_vector_scalar1(A[j], factor, A[i], q)
                Ainv[j] = minus_vector_scalar1(Ainv[j], factor,Ainv[i], q)
    return Ainv

def mult(x, y):
    c = [[0 for _ in range(len(y[0]))] for _ in range(len(x))]
    for i in range(len(x)):
        for j in range(len(y[0])):
            for k in range(len(x)):
                c[i][j] += x[i][k] * y[k][j]
                c[i][j] = c[i][j] % MOD
    return c

def matpow(b, p):
    if p == 0: return identitymatrix(n)
    if p == 1: return b
    if p % 2 == 1:
        return mult(b, matpow(b, p - 1))
    ret = matpow(b, p // 2)
    return mult(ret, ret)

n, k = map(int, input().split())
arrk = list(map(int, input().split()))
arrc = list(map(int, input().split()))
left = [[x] for x in arrk];
middle = [[0 for _ in range(n)] for _ in range(n)]
middle[0] = list(arrc)
for i in range(1,n):
    middle[i][i-1] = 1
inv = inversematrix1(middle, MOD)
inv = [[int(x) for x in y] for y in inv]
ans = matpow(inv, k - n + 1)
ans = mult(ans, left)
print(' '.join(map(lambda x : str(x[0]), ans)))

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {
private static InputReader in;
private static PrintWriter out;
public static long mod = 1000000007;

public static long inv(long N, long M) {
long x = 0, lastx = 1, y = 1, lasty = 0, q, t, a = N, b = M;
while (b != 0) {
q = a / b; t = a % b; a = b; b = t;
t = x; x = lastx - q * x; lastx = t;
t = y; y = lasty - q * y; lasty = t;
}
return (lastx + M) % M;
}

public static void main(String[] args) throws IOException {
in = new InputReader(System.in);
out = new PrintWriter(System.out, true);

int N = in.nextInt(), K = in.nextInt();
long[][] mat = new long[N][N];
long[] vec = new long[N];
long[] coef = new long[N];
for (int i = 0; i < N; i++) vec[i] = in.nextInt();
for (int i = 0; i < N; i++) coef[i] = in.nextInt();
for (int i = 0; i < N-1; i++) mat[i][i+1] = 1;

long iv = inv(coef[N-1], mod);
mat[N-1][0] = iv;
for (int i = 1; i < N; i++)
mat[N-1][i] = (mod - coef[i-1]) * iv % mod;

mat = mat_exp(mat, K - N + 1);
for (int i = 0; i < N; i++) {
long s = 0;
for (int j = 0; j < N; j++) {
s = (s + mat[i][j] * vec[j]) % mod;
}
if (i > 0) out.print(" ");
out.print(s);
}
out.println();
out.close();
System.exit(0);
}

private static long[][] mat_exp(long[][] A, int e) {
if (e == 0) {
long[][] ret = new long[A.length][A.length];
for (int i = 0; i < A.length; i++) ret[i][i] = 1;
return ret;
}
if (e == 1)
return A;
else if (e % 2 == 0) {
long[][] A1 = mat_exp(A, e / 2);
return matrix_mult(A1, A1);
} else
return matrix_mult(A, mat_exp(A, e - 1));
}

private static long[][] matrix_mult(long[][] A, long[][] B) {
long[][] C = new long[A.length][A.length];
for (int i = 0; i < A.length; i++)
for (int j = 0; j < A.length; j++)
for (int k = 0; k < A.length; k++)
C[i][k] = (C[i][k] + A[i][j] * B[j][k]) % mod;
return C;
}

static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;

public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}

public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}

public int nextInt() {
return Integer.parseInt(next());
}
}


}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50 + 2;
const int MAXK = 1e9 + 9;
const int MOD = 1e9 + 7;

void printmat( const vector< vector< int > > &mat ){ // for debug
    for( int i = 0; i < mat.size(); ++i, puts( "" ) )
        for( int j = 0; j < mat[ i ].size(); ++j )
            printf( "%d ", mat[ i ][ j ] );
}

int N, K;
int F[ MAXN ];
int C[ MAXN ];

int fastpow( int v, int p ){
    int res = 1;
    while( p ){
        if( p & 1 ) res = 1LL * res * v % MOD;
        p >>= 1;
        v = 1LL * v * v % MOD;
    }
    return res;
}

int inv( int n ){
    return fastpow( n, MOD - 2 );
}

vector< vector< int> > matmul( const vector< vector< int > > &a, const vector< vector< int > > &b ){
    assert( a[ 0 ].size() == b.size() );
    vector< vector< int > > res( a.size(), vector< int >( b[ 0 ].size() ) );
    for( int i = 0; i < a.size(); ++i )
        for( int j = 0; j < b[ 0 ].size(); ++j )
            for( int k = 0; k < a[ 0 ].size(); ++k )
                ( res[ i ][ j ] += 1LL * a[ i ][ k ] * b[ k ][ j ] % MOD ) %= MOD;
    return res;
}

vector< vector< int > > matpow( vector< vector< int > > a, int p ){
    assert( a.size() == a[ 0 ].size() );
    vector< vector< int > > res( a.size(), vector< int >( a[ 0 ].size() ) );
    for( int i = 0; i < a.size(); ++i )
        res[ i ][ i ] = 1;
    while( p ){
        if( p & 1 ) res = matmul( res, a );
        p >>= 1;
        a = matmul( a, a );
    }
    return res;
}

void solve(){
    vector< vector< int > > tmat( N, vector< int >( N ) );
    int z = inv( C[ N - 1 ] );
    for( int i = 0; i < N - 1; ++i )
        tmat[ 0 ][ i ] = ( ( 1LL * z * -C[ N - 2 - i ] % MOD ) + MOD ) % MOD;
    tmat[ 0 ][ N - 1 ] = z;
    for( int i = 0; i < N - 1; ++i )
        tmat[ i + 1 ][ i ] = 1;
    vector< vector< int > > f( N, vector< int >( 1 ) );
    for( int i = 0; i < N; ++i )
        f[ i ][ 0 ] = F[ N - 1 - i ];
    vector< vector< int > > ans = matmul( matpow( tmat, K - N + 1 ), f );
    for( int i = N - 1; i >= 0; --i )
        printf( "%d%c", ans[ i ][ 0 ], i == 0 ? '\n' : ' ' );
}

int main(){
    scanf( "%d%d", &N, &K );
    for( int i = 0; i < N; ++i )
        scanf( "%d", F + i );
    for( int i = 0; i < N; ++i )
        scanf( "%d", C + i );
    solve();
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
long long modInverse(long long a,long long mod);
void one(long long*a,int SIZE);
void mul(long long*a,long long*b,int SIZE);
void powm(long long*a,int n,long long*res,int SIZE);
int F[50],C[50];
long long a[50][50],ans[50][50],A[50];

int main(){
  int N,K,i,j;
  scanf("%d%d",&N,&K);
  for(i=0;i<N;i++)
    scanf("%d",F+i);
  for(i=0;i<N;i++)
    scanf("%d",C+i);
  for(i=0;i<N-1;i++)
    for(j=0;j<N;j++)
      if(i==j-1)
        a[i][j]=1;
      else
        a[i][j]=0;
  a[N-1][0]=modInverse(C[N-1],MOD);
  for(i=1;i<N;i++)
    a[N-1][i]=(MOD-C[i-1])*a[N-1][0]%MOD;
  powm(&a[0][0],K-N+1,&ans[0][0],50);
  for(i=0;i<N;i++)
    for(j=0,A[i]=0;j<N;j++)
      A[i]=(A[i]+F[j]*ans[i][j])%MOD;
  for(i=0;i<N;i++)
    printf("%lld ",A[i]);
  return 0;
}
long long modInverse(long long a,long long mod){
    long long b0 = mod, t, q;
    long long x0 = 0, x1 = 1;
    while (a > 1) {
        q = a / mod;
        t = mod; mod = a % mod; a = t;
        t = x0; x0 = x1 - q * x0; x1 = t;
    }
    if (x1 < 0) x1 += b0;
    return x1;
}
void one(long long*a,int SIZE){
    int i,j;
    for (i = 0; i < SIZE; i++)
        for (j = 0; j < SIZE; j++)
            a[i*SIZE+j] = (i == j);
    return;
}
void mul(long long*a,long long*b,int SIZE){
    int i,j,k;
    long long res[SIZE][SIZE];
    for(i=0;i<SIZE;i++)
      for(j=0;j<SIZE;j++)
        res[i][j]=0;
    for (i = 0; i < SIZE; i++)
        for (j = 0; j < SIZE; j++)
            for (k = 0; k < SIZE; k++)
                res[i][j] =(res[i][j] + a[i*SIZE+k] * b[k*SIZE+j])%MOD;
    for (i = 0; i < SIZE; i++)
        for (j = 0; j < SIZE; j++)
            a[i*SIZE+j] = res[i][j];
    return;
}
void powm(long long*a,int n,long long*res,int SIZE){
    one(res,SIZE);
    while (n > 0) {
        if (n % 2 == 0)
        {
            mul(a, a,SIZE);
            n /= 2;
        }
        else {
            mul(res, a,SIZE);
            n--;
        }
    }
}