Cerinta completa

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

The numbers used as seeds are . is the 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 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, and , respectively.
The second line contains the space-separated integers describing (all these numbers are non-negative integers ).
The third line contains the space-separated coefficients of the recurrence formula, . All of these coefficients are positive integers .

Constraints

Output Format

The output must be one line containing the space-separated seeds of the random numbers – .

Sample Input

2 6
13 8
1 1

Sample Output

1 1

Explanation

This is the classic Fibonacci recurrence. We have the and terms, and, of course, the seeds are the numbers and .

Limbajul de programare folosit: cpp14

Cod:

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

Scor obtinut: 1.0

Submission ID: 464649118

Link challenge: https://www.hackerrank.com/challenges/find-the-seed/problem

Find the Seed