# 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 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 {
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;
}

public StringTokenizer tokenizer;

tokenizer = null;
}

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

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--;
}
}
}

```