# Find the Seed

### Problem Statement :

```A company needs random numbers for its operation. N random numbers have been generated using  N numbers as seeds and the following recurrence formula:

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 a failure on the servers, the company lost its seed numbers. Now they just have the recurrence formula and the previously generated N random numbers.

The company wants to recover the numbers used as seeds, so they have hired you for doing this task.

Input Format

The first line contains two space-separated integers, N and K, respectively.
The second line contains the space-separated integers describing   F(K),F(K-1),...,F(K-N+2),F(K-N+1). F(K)(all these numbers are non-negative integers < 10^9).
The third line contains the space-separated coefficients of the recurrence formula, C(1),C(2),...,C(N-1),C(N). All of these coefficients are positive integers <10^9.

Constraints

1 <= N <= 50
1 <= K <=10^9
0 <= K-N+1```

### Solution :

```                            ```Solution in C :

In C++ :

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

ll MOD = 1000000007;
ll powe(ll a, ll b) {
if (b == 0) return 1;
if (b % 2 == 0) return powe( (a*a)%MOD, b/2);
return (a*powe(a, b-1)) % MOD;
}

ll inv(ll a) {
return powe(a, MOD-2);
}

struct matrix {
vector<vector<ll>> M;
matrix I() const {
matrix ans;
ans.M = M;
for (int i = 0; i < M.size(); ++i)
for (int j = 0; j < M.size(); ++j)
ans.M[i][j] = !!(i==j);
return ans;
}
matrix operator*(const matrix& rhs) const {
matrix ans;
ans.M = M;
int N = M.size();
for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
ans.M[i][j] = 0;
for (int k = 0; k < N; ++k)
ans.M[i][j] = (ans.M[i][j] + M[i][k]*rhs.M[k][j]) % MOD;
}
return ans;
}
};

matrix powm(const matrix& M, int b) {
if (b == 0) return M.I();
if (b % 2 == 0) return powm( M*M, b/2);
return M*powm(M, b-1);
}

int main() {
ll N, K;
cin >> N >> K;
vector<ll> F(N);
for (ll &x : F) cin >> x;
vector<ll> C(N);
for (ll &x : C) cin >> x;
matrix M;
M.M = vector<vector<ll>>(N, vector<ll>(N));
for (int i = 0; i < N-1; ++i)
for (int j = 0; j < N; ++j)
M.M[i][j] = !!((i+1) == j);
ll cinv = inv(C.back());
M.M[N-1][0] = cinv;
for (int j = 1; j < N; ++j)
M.M[N-1][j] = ((MOD - C[j-1])*cinv)%MOD;
auto M2 = powm(M, K-N+1);
vector<ll> ans(N);
for (int i = 0; i < N; ++i) {
ans[i] = 0;
for (int j = 0; j < N; ++j)
ans[i] = (ans[i] + F[j]*M2.M[i][j]) % MOD;
}
for (int i = 0; i < N; ++i) {
if (i) printf(" ");
printf("%lld", ans[i]);
}
printf("\n");
return 0;
}

In Java :

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

static final int Q = 1000000007;

/** Assume 1 <= a < M and (a, M) = 1.  Return b such that 1 <= b < M and a*b = 1(mod M). */
static int inv(int a, int M) {
//assert a >= 1 && a < M;
int t = 0;
int r = M;
int newt = 1;
int newr = (int) a;
while (newr != 0) {
int q = r / newr;
int temp = t - q * newt;
t = newt;
newt = temp;
temp = r - q * newr;
r = newr;
newr = temp;
}
int result = (t < 0) ? t + M : t;
//assert (a * result) % M == 1 && result >= 1 && result < M;
return result;
}

static long[][] multiply(long[][] m1, long[][] m2) {
int N = m1.length;
long[][] m3 = new long[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
m3[i][j] = (m3[i][j] + ((m1[i][k] * m2[k][j]) % Q)) % Q;
}
}
}
return m3;
}

/** Assume b >= 1 and each a[i][j] * (Q - 1) is in long range. */
static long[][] pow(long[][] a, long b) {
if (b == 1L) {
return a;
}
long[][] half = pow(a, b / 2);
long[][] almost = multiply(half, half);
return (b % 2 == 0) ? almost : multiply(almost, a);
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long k = in.nextLong();
long[] f = new long[n];
int i;
for (i = 0; i < n; i++) {
f[i] = in.nextLong();
}
int[] c = new int[n];
for (i = 0; i < n; i++) {
c[i] = in.nextInt();
}

StringBuilder builder = new StringBuilder();
if (k - n + 1 == 0L) {
for (i = 0; i < n; i++) {
if (i != 0) {
builder.append(' ');
}
builder.append(f[i]);
}
}
else {
long[][] mat = new long[n][n];
for (i = 0; i < n - 1; i++) {
mat[i + 1][i] = 1L;
}
mat[0][n - 1] = (long) inv(c[n - 1], Q);
for (i = 1; i < n; i++) {
mat[i][n - 1] = (Q - ((c[i - 1] * mat[0][n - 1]) % Q)) % Q;
}
long[][] power = pow(mat, k - n + 1);
int j;
long a;
for (i = 0; i < n; i++) {
a = 0L;
for (j = 0; j < n; j++) {
a = (a + f[j] * power[j][i]) % Q;
}
if (i != 0) {
builder.append(' ');
}
builder.append(a);
}
}
System.out.println(builder);
}
}

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

In Python3 :

#http://stackoverflow.com/questions/24701490/modular-matrix-inversion-with-large-number?lq=1
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):
# print "a is 0 mod p"
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)))```
```

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element