Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Dibs on Fibs CodeChef Solution
Problem -Dibs on Fibs CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Dibs on Fibs CodeChef Solution in C++14
#include<iostream>
#define ll long long int
#define mod 1000000007
int main()
{
int t;
std::cin>>t;
while(t--)
{
int n,m;
std::cin>>m>>n;
ll s1=0,s2=0;
for(int i=0;i<m;++i)
{
int x;
std::cin>>x;
s1=(s1+x)%mod;
}
s1=(s1*m)%mod;
for(int i=0;i<m;++i)
{
int y;
std::cin>>y;
s2=(s2+y)%mod;
}
s2=(s2*m)%mod;
if(n==1)
std::cout<<s1<<'\n';
else if(n==2)
std::cout<<s2<<'\n';
else
{
ll a=s1,b=s2,c=-1;
for(int i=3;i<=n;++i)
{
c=(a+b)%mod;
a=b;
b=c;
}
std::cout<<c<<'\n';
}
}
}Dibs on Fibs CodeChef Solution in PYTH 3
# cook your dish here
for _ in range(int(input())):
m,n=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
M=1000000007
A=[0,1]
B=[1,0]
for i in range(n):
A.append(A[-1]+A[-2])
B.append(B[-1]+B[-2])
u=A[n-1]
v=B[n-1]
print((m*(v*sum(a)+u*sum(b)))%M)Dibs on Fibs CodeChef Solution in C
#include <stdio.h>
int main(void) {
long long int t,i;
long long int mod=1000000007;
scanf("%lld",&t);
while(t--)
{
long long int m,n;
scanf("%lld %lld ",&m,&n);
long long int a[m],b[m],i;
long long int sum=0;
for(i=0;i<m;i++)
{
scanf("%lld ",&a[i]);
}
for(i=0;i<m;i++)
{
scanf("%lld ",&b[i]);
}
long long int x=1,y=0,x1;
for(i=2;i<=n;i++)
{
x1=x+y;
x=y%mod;
y=x1%mod;
}
for(i=0;i<m;i++)
{
sum=(sum+((x*m)%mod)*a[i])%mod;
}
for(i=0;i<m;i++)
{
sum=(sum+((y*m)%mod)*b[i])%mod;
}
printf("%lld \n",sum);
}
return 0;
}
Dibs on Fibs CodeChef Solution in JAVA
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args) throws IOException
{
try
{
Scanner inp = new Scanner(System.in);
int T = inp.nextInt();
for ( int j = 0; j < T ; j ++)
{
int M = inp.nextInt();
int N = inp.nextInt();
long A[] = new long[M];
long B[] = new long[M];
long C1;
long C2;
long sumA = 0 ;
long sumB = 0 ;
for ( int i = 0 ; i < M ; i++)
{
A[i] = inp.nextLong();
sumA = modAdd(sumA,A[i]);
}
for ( int i = 0 ; i < M ; i++)
{
B[i] = inp.nextLong() ;
sumB = modAdd(sumB,B[i]);
}
sumA = modMultiply(sumA,M);
sumB = modMultiply(sumB,M);
long fib2 = sumB;
long fib1 = sumA;
for ( int i = 2 ; i < N ; i++)
{
sumB = modAdd(fib1,fib2);
fib1 = fib2;
fib2 = sumB;
}
System.out.println(sumB);
}
} catch (Exception e)
{
e.printStackTrace();
return;
}
}
private static long modMultiply(long A , long B )
{
return ((A%(1000000000+7))*(B%(1000000000+7)))%(1000000000+7) ;
}
private static long modAdd(long A , long B )
{
return ((A%(1000000000+7) + B%(1000000000+7))%(1000000000+7));
}
}Dibs on Fibs CodeChef Solution in PYPY 3
import math
import os
m = 10**9+7
try:
T = int(input())
for l in range(T):
M,N = [int(i) for i in input().strip().split(" ")]
A = [int(i) for i in input().strip().split(" ")]
B = [int(i) for i in input().strip().split(" ")]
result = 0
s1 = 0
s2 = 0
for i in range(M):
s1 = (s1%m + A[i]%m)%m
s1 = s1%m
for i in range(M):
s2 = (s2%m + B[i]%m)%m
s2 = s2%m
fib = [0 for i in range(max(2,N)+1)]
if N == 1:
print((s1%m*M%m)%m)
elif N == 2:
print((s2%m*M%m)%m)
else:
fib[0] = 1
fib[1] = s1
fib[2] = s2
for k in range(3,N+1):
fib[k] = (fib[k-1]%m + fib[k-2]%m)%m
print((fib[N]%m*M%m)%m)
except EOFError:
pass
Dibs on Fibs CodeChef Solution in PYTH
MD = 1000000007
t = int(raw_input())
for i in range(t):
st = raw_input().split()
M = int(st[0])
N = int(st[1])
st = raw_input().split()
A = 0
for x in st:
A += int(x)
# endfor x
st = raw_input().split()
B = 0
for x in st:
B += int(x)
# endfor x
F = [0 for x in range(N+1)]
if N == 1:
r = A*M%MD
else:
F[1] = A*M%MD
F[2] = B*M%MD
for k in range(3,N+1):
F[k] = (F[k-1]+F[k-2])%MD
# endfor k
r = F[N]
# endif
print r
# endfor i
Dibs on Fibs CodeChef Solution in C#
using System;
using System.Collections;
using System.Text.RegularExpressions;
namespace Challenges
{
class Program
{
static void Main(string[] args)
{
var tests = Convert.ToInt32(Console.ReadLine());
for (var i = 0; i < tests;i++) {
var counts = Array.ConvertAll<string,long>(Console.ReadLine().Split(), s => Convert.ToInt64(s));
var numsA = Array.ConvertAll<string, long>(Console.ReadLine().Split(), s => Convert.ToInt64(s));
var numsB = Array.ConvertAll<string, long>(Console.ReadLine().Split(), s => Convert.ToInt64(s));
//var watch = System.Diagnostics.Stopwatch.StartNew();
//for (var j = 0; j < 1000; j++) DibsOnFibs(numsA, numsB, M: counts[0], N: counts[1]);
//Console.WriteLine(DibsOnFibs(numsA, numsB, M: counts[0], N: counts[1]));
//watch.Stop();
//var elapsedMs = watch.ElapsedMilliseconds;
//Console.WriteLine("ms: " +elapsedMs);
//watch = System.Diagnostics.Stopwatch.StartNew();
//for (var j = 0; j < 1000; j++) DibsOnFibsMatrix(numsA, numsB, M: Convert.ToInt32(counts[0]), N: Convert.ToInt32(counts[1]));
//if (Convert.ToInt32(counts[1])<10000)
//Console.WriteLine(DibsOnFibs(numsA, numsB, M: counts[0], N: counts[1]));
Console.WriteLine(DibsOnFibsHack(numsA, numsB, M: counts[0], N: counts[1]));
//else
// Console.WriteLine(DibsOnFibsMatrix(numsA, numsB, M: Convert.ToInt32(counts[0]), N: Convert.ToInt32(counts[1])));
//watch.Stop();
//elapsedMs = watch.ElapsedMilliseconds;
//Console.WriteLine("ms: "+elapsedMs);
}
}
private static long DibsOnFibsHack(long[] numsA, long[] numsB, long M, long N)
{
var div = Convert.ToInt64(1e+9) + 7;
var sumA = 0L;
var sumB = 0L;
for (var i = 0; i < M; i++) sumA = (sumA + numsA[i]) % div;
for (var i = 0; i < M; i++) sumB = (sumB + numsB[i]) % div;
sumA = (sumA * M) % div;
sumB = (sumB * M) % div;
var result = 0L;
var fib = new long[Math.Max(2, N)];
fib[1 - 1] = sumA;
fib[2 - 1] = sumB;
for (var k = 3; k <= N; k++)
{
fib[k - 1] = (fib[k - 1 - 1] + fib[k - 2 - 1]) % div;
}
result = (result + fib[Math.Max(2, N)-1]) % div;
return result;
}
private static long DibsOnFibs(long[] numsA, long[] numsB, long M, long N)
{
var div = Convert.ToInt64(1e+9) + 7;
var hash = new Hashtable();
var rowHashes = new Hashtable();
var result = 0L;
for (var i = 1; i <= M; i++) {
/*if (hash.Contains(i))
{
result = (result + (long)hash[i]) % div;
continue;
}*/
var rowResult = 0L;
for (var j = 1; j <= M; j++) {
if (hash.Contains($"{numsA[i - 1]},{numsB[j - 1]}"))
{
result = (result + (long)hash[$"{numsA[i - 1]},{numsB[j - 1]}"]) % div;
continue;
}
var fib = new long[Math.Max(2, N)];
fib[1 - 1] = numsA[i-1];
fib[2 - 1] = numsB[j-1];
for (var k = 3; k <= N;k++) {
fib[k - 1] = (fib[k - 1 - 1] + fib[k - 2 - 1])%div;
}
hash[$"{numsA[i - 1]},{numsB[j - 1]}"] = fib[N - 1];
rowResult = (rowResult + fib[N - 1])%div;
}
//rowHashes[i] = rowResult;
result = (result + rowResult) % div;
}
return result;
}
private static long DibsOnFibsMatrix(long[] numsA, long[] numsB, int M, int N)
{
var div = Convert.ToInt64(1e+9) + 7;
var hash = new Hashtable();
var result = 0L;
var ones = new Matrix(2, 2);
ones[0, 0] = 0;
ones[0, 1] = 1;
ones[1, 0] = 1;
ones[1, 1] = 1;
ones = Matrix.PowerModulo(ones, N - 1, div);
for (var i = 1; i <= M; i++)
{
for (var j = 1; j <= M; j++)
{
/*if (hash.Contains($"{numsA[i-1]},{numsB[j-1]}")) {
result = (result + (long)hash[$"{numsA[i - 1]},{numsB[j - 1]}"]) % div;
continue;
}*/
var fib = new Matrix(1, 2);
fib[0,0] = numsA[i - 1];
fib[0,1] = numsB[j - 1];
var fibEnd = Matrix.MultiplyModulo(fib, ones, div);
hash[$"{numsA[i - 1]},{numsB[j - 1]}"] = fibEnd[0, 0];
result = (result + fibEnd[0,0])%div;
}
}
return result;
}
}
public class Matrix
{
public int rows;
public int cols;
public long[,] mat;
public Matrix L;
public Matrix U;
private int[] pi;
private double detOfP = 1;
public Matrix(int iRows, int iCols) // Matrix Class constructor
{
rows = iRows;
cols = iCols;
mat = new long[rows, cols];
}
public Boolean IsSquare()
{
return (rows == cols);
}
public long this[int iRow, int iCol] // Access this matrix as a 2D array
{
get { return mat[iRow, iCol]; }
set { mat[iRow, iCol] = value; }
}
public Matrix GetCol(int k)
{
Matrix m = new Matrix(rows, 1);
for (int i = 0; i < rows; i++) m[i, 0] = mat[i, k];
return m;
}
public void SetCol(Matrix v, int k)
{
for (int i = 0; i < rows; i++) mat[i, k] = v[i, 0];
}
public void MakeLU() // Function for LU decomposition
{
if (!IsSquare()) throw new MException("The matrix is not square!");
L = IdentityMatrix(rows, cols);
U = Duplicate();
pi = new int[rows];
for (int i = 0; i < rows; i++) pi[i] = i;
double p = 0;
long pom2;
int k0 = 0;
int pom1 = 0;
for (int k = 0; k < cols - 1; k++)
{
p = 0;
for (int i = k; i < rows; i++) // find the row with the biggest pivot
{
if (Math.Abs(U[i, k]) > p)
{
p = Math.Abs(U[i, k]);
k0 = i;
}
}
if (p == 0) // samé nuly ve sloupci
throw new MException("The matrix is singular!");
pom1 = pi[k]; pi[k] = pi[k0]; pi[k0] = pom1; // switch two rows in permutation matrix
for (int i = 0; i < k; i++)
{
pom2 = L[k, i]; L[k, i] = L[k0, i]; L[k0, i] = pom2;
}
if (k != k0) detOfP *= -1;
for (int i = 0; i < cols; i++) // Switch rows in U
{
pom2 = U[k, i]; U[k, i] = U[k0, i]; U[k0, i] = pom2;
}
for (int i = k + 1; i < rows; i++)
{
L[i, k] = U[i, k] / U[k, k];
for (int j = k; j < cols; j++)
U[i, j] = U[i, j] - L[i, k] * U[k, j];
}
}
}
public Matrix SolveWith(Matrix v) // Function solves Ax = v in confirmity with solution vector "v"
{
if (rows != cols) throw new MException("The matrix is not square!");
if (rows != v.rows) throw new MException("Wrong number of results in solution vector!");
if (L == null) MakeLU();
Matrix b = new Matrix(rows, 1);
for (int i = 0; i < rows; i++) b[i, 0] = v[pi[i], 0]; // switch two items in "v" due to permutation matrix
Matrix z = SubsForth(L, b);
Matrix x = SubsBack(U, z);
return x;
}
public Matrix Invert() // Function returns the inverted matrix
{
if (L == null) MakeLU();
Matrix inv = new Matrix(rows, cols);
for (int i = 0; i < rows; i++)
{
Matrix Ei = Matrix.ZeroMatrix(rows, 1);
Ei[i, 0] = 1;
Matrix col = SolveWith(Ei);
inv.SetCol(col, i);
}
return inv;
}
public double Det() // Function for determinant
{
if (L == null) MakeLU();
double det = detOfP;
for (int i = 0; i < rows; i++) det *= U[i, i];
return det;
}
public Matrix GetP() // Function returns permutation matrix "P" due to permutation vector "pi"
{
if (L == null) MakeLU();
Matrix matrix = ZeroMatrix(rows, cols);
for (int i = 0; i < rows; i++) matrix[pi[i], i] = 1;
return matrix;
}
public Matrix Duplicate() // Function returns the copy of this matrix
{
Matrix matrix = new Matrix(rows, cols);
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
matrix[i, j] = mat[i, j];
return matrix;
}
public static Matrix SubsForth(Matrix A, Matrix b) // Function solves Ax = b for A as a lower triangular matrix
{
if (A.L == null) A.MakeLU();
int n = A.rows;
Matrix x = new Matrix(n, 1);
for (int i = 0; i < n; i++)
{
x[i, 0] = b[i, 0];
for (int j = 0; j < i; j++) x[i, 0] -= A[i, j] * x[j, 0];
x[i, 0] = x[i, 0] / A[i, i];
}
return x;
}
public static Matrix SubsBack(Matrix A, Matrix b) // Function solves Ax = b for A as an upper triangular matrix
{
if (A.L == null) A.MakeLU();
int n = A.rows;
Matrix x = new Matrix(n, 1);
for (int i = n - 1; i > -1; i--)
{
x[i, 0] = b[i, 0];
for (int j = n - 1; j > i; j--) x[i, 0] -= A[i, j] * x[j, 0];
x[i, 0] = x[i, 0] / A[i, i];
}
return x;
}
public static Matrix ZeroMatrix(int iRows, int iCols) // Function generates the zero matrix
{
Matrix matrix = new Matrix(iRows, iCols);
for (int i = 0; i < iRows; i++)
for (int j = 0; j < iCols; j++)
matrix[i, j] = 0;
return matrix;
}
public static Matrix IdentityMatrix(int iRows, int iCols) // Function generates the identity matrix
{
Matrix matrix = ZeroMatrix(iRows, iCols);
for (int i = 0; i < Math.Min(iRows, iCols); i++)
matrix[i, i] = 1;
return matrix;
}
public static Matrix RandomMatrix(int iRows, int iCols, int dispersion) // Function generates the random matrix
{
Random random = new Random();
Matrix matrix = new Matrix(iRows, iCols);
for (int i = 0; i < iRows; i++)
for (int j = 0; j < iCols; j++)
matrix[i, j] = random.Next(-dispersion, dispersion);
return matrix;
}
public static Matrix Parse(string ps) // Function parses the matrix from string
{
string s = NormalizeMatrixString(ps);
string[] rows = Regex.Split(s, "\r\n");
string[] nums = rows[0].Split(' ');
Matrix matrix = new Matrix(rows.Length, nums.Length);
try
{
for (int i = 0; i < rows.Length; i++)
{
nums = rows[i].Split(' ');
for (int j = 0; j < nums.Length; j++) matrix[i, j] = long.Parse(nums[j]);
}
}
catch (FormatException exc) { throw new MException("Wrong input format!"); }
return matrix;
}
public override string ToString() // Function returns matrix as a string
{
string s = "";
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++) s += String.Format("{0,5:0.00}", mat[i, j]) + " ";
s += "\r\n";
}
return s;
}
public static Matrix Transpose(Matrix m) // Matrix transpose, for any rectangular matrix
{
Matrix t = new Matrix(m.cols, m.rows);
for (int i = 0; i < m.rows; i++)
for (int j = 0; j < m.cols; j++)
t[j, i] = m[i, j];
return t;
}
public static Matrix Power(Matrix m, int pow) // Power matrix to exponent
{
if (pow == 0) return IdentityMatrix(m.rows, m.cols);
if (pow == 1) return m.Duplicate();
if (pow == -1) return m.Invert();
Matrix x;
if (pow < 0) { x = m.Invert(); pow *= -1; }
else x = m.Duplicate();
Matrix ret = IdentityMatrix(m.rows, m.cols);
while (pow != 0)
{
if ((pow & 1) == 1) ret *= x;
x *= x;
pow >>= 1;
}
return ret;
}
public static Matrix PowerModulo(Matrix m, int pow, long mod) // Power matrix to exponent
{
if (pow == 0) return IdentityMatrix(m.rows, m.cols);
if (pow == 1) return m.Duplicate();
if (pow == -1) return m.Invert();
Matrix x;
if (pow < 0) { x = m.Invert(); pow *= -1; }
else x = m.Duplicate();
Matrix ret = IdentityMatrix(m.rows, m.cols);
while (pow != 0)
{
if ((pow & 1) == 1) ret = MultiplyModulo(ret,x,mod);
x = MultiplyModulo(x,x,mod);
pow >>= 1;
}
return ret;
}
private static void SafeAplusBintoC(Matrix A, int xa, int ya, Matrix B, int xb, int yb, Matrix C, int size)
{
for (int i = 0; i < size; i++) // rows
for (int j = 0; j < size; j++) // cols
{
C[i, j] = 0;
if (xa + j < A.cols && ya + i < A.rows) C[i, j] += A[ya + i, xa + j];
if (xb + j < B.cols && yb + i < B.rows) C[i, j] += B[yb + i, xb + j];
}
}
private static void SafeAminusBintoC(Matrix A, int xa, int ya, Matrix B, int xb, int yb, Matrix C, int size)
{
for (int i = 0; i < size; i++) // rows
for (int j = 0; j < size; j++) // cols
{
C[i, j] = 0;
if (xa + j < A.cols && ya + i < A.rows) C[i, j] += A[ya + i, xa + j];
if (xb + j < B.cols && yb + i < B.rows) C[i, j] -= B[yb + i, xb + j];
}
}
private static void SafeACopytoC(Matrix A, int xa, int ya, Matrix C, int size)
{
for (int i = 0; i < size; i++) // rows
for (int j = 0; j < size; j++) // cols
{
C[i, j] = 0;
if (xa + j < A.cols && ya + i < A.rows) C[i, j] += A[ya + i, xa + j];
}
}
private static void AplusBintoC(Matrix A, int xa, int ya, Matrix B, int xb, int yb, Matrix C, int size)
{
for (int i = 0; i < size; i++) // rows
for (int j = 0; j < size; j++) C[i, j] = A[ya + i, xa + j] + B[yb + i, xb + j];
}
private static void AminusBintoC(Matrix A, int xa, int ya, Matrix B, int xb, int yb, Matrix C, int size)
{
for (int i = 0; i < size; i++) // rows
for (int j = 0; j < size; j++) C[i, j] = A[ya + i, xa + j] - B[yb + i, xb + j];
}
private static void ACopytoC(Matrix A, int xa, int ya, Matrix C, int size)
{
for (int i = 0; i < size; i++) // rows
for (int j = 0; j < size; j++) C[i, j] = A[ya + i, xa + j];
}
private static Matrix StrassenMultiply(Matrix A, Matrix B) // Smart matrix multiplication
{
if (A.cols != B.rows) throw new MException("Wrong dimension of matrix!");
Matrix R;
int msize = Math.Max(Math.Max(A.rows, A.cols), Math.Max(B.rows, B.cols));
if (msize < 32)
{
R = ZeroMatrix(A.rows, B.cols);
for (int i = 0; i < R.rows; i++)
for (int j = 0; j < R.cols; j++)
for (int k = 0; k < A.cols; k++)
R[i, j] += A[i, k] * B[k, j];
return R;
}
int size = 1; int n = 0;
while (msize > size) { size *= 2; n++; };
int h = size / 2;
Matrix[,] mField = new Matrix[n, 9];
/*
* 8x8, 8x8, 8x8, ...
* 4x4, 4x4, 4x4, ...
* 2x2, 2x2, 2x2, ...
* . . .
*/
int z;
for (int i = 0; i < n - 4; i++) // rows
{
z = (int)Math.Pow(2, n - i - 1);
for (int j = 0; j < 9; j++) mField[i, j] = new Matrix(z, z);
}
SafeAplusBintoC(A, 0, 0, A, h, h, mField[0, 0], h);
SafeAplusBintoC(B, 0, 0, B, h, h, mField[0, 1], h);
StrassenMultiplyRun(mField[0, 0], mField[0, 1], mField[0, 1 + 1], 1, mField); // (A11 + A22) * (B11 + B22);
SafeAplusBintoC(A, 0, h, A, h, h, mField[0, 0], h);
SafeACopytoC(B, 0, 0, mField[0, 1], h);
StrassenMultiplyRun(mField[0, 0], mField[0, 1], mField[0, 1 + 2], 1, mField); // (A21 + A22) * B11;
SafeACopytoC(A, 0, 0, mField[0, 0], h);
SafeAminusBintoC(B, h, 0, B, h, h, mField[0, 1], h);
StrassenMultiplyRun(mField[0, 0], mField[0, 1], mField[0, 1 + 3], 1, mField); //A11 * (B12 - B22);
SafeACopytoC(A, h, h, mField[0, 0], h);
SafeAminusBintoC(B, 0, h, B, 0, 0, mField[0, 1], h);
StrassenMultiplyRun(mField[0, 0], mField[0, 1], mField[0, 1 + 4], 1, mField); //A22 * (B21 - B11);
SafeAplusBintoC(A, 0, 0, A, h, 0, mField[0, 0], h);
SafeACopytoC(B, h, h, mField[0, 1], h);
StrassenMultiplyRun(mField[0, 0], mField[0, 1], mField[0, 1 + 5], 1, mField); //(A11 + A12) * B22;
SafeAminusBintoC(A, 0, h, A, 0, 0, mField[0, 0], h);
SafeAplusBintoC(B, 0, 0, B, h, 0, mField[0, 1], h);
StrassenMultiplyRun(mField[0, 0], mField[0, 1], mField[0, 1 + 6], 1, mField); //(A21 - A11) * (B11 + B12);
SafeAminusBintoC(A, h, 0, A, h, h, mField[0, 0], h);
SafeAplusBintoC(B, 0, h, B, h, h, mField[0, 1], h);
StrassenMultiplyRun(mField[0, 0], mField[0, 1], mField[0, 1 + 7], 1, mField); // (A12 - A22) * (B21 + B22);
R = new Matrix(A.rows, B.cols); // result
/// C11
for (int i = 0; i < Math.Min(h, R.rows); i++) // rows
for (int j = 0; j < Math.Min(h, R.cols); j++) // cols
R[i, j] = mField[0, 1 + 1][i, j] + mField[0, 1 + 4][i, j] - mField[0, 1 + 5][i, j] + mField[0, 1 + 7][i, j];
/// C12
for (int i = 0; i < Math.Min(h, R.rows); i++) // rows
for (int j = h; j < Math.Min(2 * h, R.cols); j++) // cols
R[i, j] = mField[0, 1 + 3][i, j - h] + mField[0, 1 + 5][i, j - h];
/// C21
for (int i = h; i < Math.Min(2 * h, R.rows); i++) // rows
for (int j = 0; j < Math.Min(h, R.cols); j++) // cols
R[i, j] = mField[0, 1 + 2][i - h, j] + mField[0, 1 + 4][i - h, j];
/// C22
for (int i = h; i < Math.Min(2 * h, R.rows); i++) // rows
for (int j = h; j < Math.Min(2 * h, R.cols); j++) // cols
R[i, j] = mField[0, 1 + 1][i - h, j - h] - mField[0, 1 + 2][i - h, j - h] + mField[0, 1 + 3][i - h, j - h] + mField[0, 1 + 6][i - h, j - h];
return R;
}
// function for square matrix 2^N x 2^N
private static void StrassenMultiplyRun(Matrix A, Matrix B, Matrix C, int l, Matrix[,] f) // A * B into C, level of recursion, matrix field
{
int size = A.rows;
int h = size / 2;
if (size < 32)
{
for (int i = 0; i < C.rows; i++)
for (int j = 0; j < C.cols; j++)
{
C[i, j] = 0;
for (int k = 0; k < A.cols; k++) C[i, j] += A[i, k] * B[k, j];
}
return;
}
AplusBintoC(A, 0, 0, A, h, h, f[l, 0], h);
AplusBintoC(B, 0, 0, B, h, h, f[l, 1], h);
StrassenMultiplyRun(f[l, 0], f[l, 1], f[l, 1 + 1], l + 1, f); // (A11 + A22) * (B11 + B22);
AplusBintoC(A, 0, h, A, h, h, f[l, 0], h);
ACopytoC(B, 0, 0, f[l, 1], h);
StrassenMultiplyRun(f[l, 0], f[l, 1], f[l, 1 + 2], l + 1, f); // (A21 + A22) * B11;
ACopytoC(A, 0, 0, f[l, 0], h);
AminusBintoC(B, h, 0, B, h, h, f[l, 1], h);
StrassenMultiplyRun(f[l, 0], f[l, 1], f[l, 1 + 3], l + 1, f); //A11 * (B12 - B22);
ACopytoC(A, h, h, f[l, 0], h);
AminusBintoC(B, 0, h, B, 0, 0, f[l, 1], h);
StrassenMultiplyRun(f[l, 0], f[l, 1], f[l, 1 + 4], l + 1, f); //A22 * (B21 - B11);
AplusBintoC(A, 0, 0, A, h, 0, f[l, 0], h);
ACopytoC(B, h, h, f[l, 1], h);
StrassenMultiplyRun(f[l, 0], f[l, 1], f[l, 1 + 5], l + 1, f); //(A11 + A12) * B22;
AminusBintoC(A, 0, h, A, 0, 0, f[l, 0], h);
AplusBintoC(B, 0, 0, B, h, 0, f[l, 1], h);
StrassenMultiplyRun(f[l, 0], f[l, 1], f[l, 1 + 6], l + 1, f); //(A21 - A11) * (B11 + B12);
AminusBintoC(A, h, 0, A, h, h, f[l, 0], h);
AplusBintoC(B, 0, h, B, h, h, f[l, 1], h);
StrassenMultiplyRun(f[l, 0], f[l, 1], f[l, 1 + 7], l + 1, f); // (A12 - A22) * (B21 + B22);
/// C11
for (int i = 0; i < h; i++) // rows
for (int j = 0; j < h; j++) // cols
C[i, j] = f[l, 1 + 1][i, j] + f[l, 1 + 4][i, j] - f[l, 1 + 5][i, j] + f[l, 1 + 7][i, j];
/// C12
for (int i = 0; i < h; i++) // rows
for (int j = h; j < size; j++) // cols
C[i, j] = f[l, 1 + 3][i, j - h] + f[l, 1 + 5][i, j - h];
/// C21
for (int i = h; i < size; i++) // rows
for (int j = 0; j < h; j++) // cols
C[i, j] = f[l, 1 + 2][i - h, j] + f[l, 1 + 4][i - h, j];
/// C22
for (int i = h; i < size; i++) // rows
for (int j = h; j < size; j++) // cols
C[i, j] = f[l, 1 + 1][i - h, j - h] - f[l, 1 + 2][i - h, j - h] + f[l, 1 + 3][i - h, j - h] + f[l, 1 + 6][i - h, j - h];
}
public static Matrix StupidMultiply(Matrix m1, Matrix m2) // Stupid matrix multiplication
{
if (m1.cols != m2.rows) throw new MException("Wrong dimensions of matrix!");
Matrix result = ZeroMatrix(m1.rows, m2.cols);
for (int i = 0; i < result.rows; i++)
for (int j = 0; j < result.cols; j++)
for (int k = 0; k < m1.cols; k++)
result[i, j] += m1[i, k] * m2[k, j];
return result;
}
private static Matrix Multiply(long n, Matrix m) // Multiplication by constant n
{
Matrix r = new Matrix(m.rows, m.cols);
for (int i = 0; i < m.rows; i++)
for (int j = 0; j < m.cols; j++)
r[i, j] = m[i, j] * n;
return r;
}
private static Matrix Add(Matrix m1, Matrix m2) // Sčítání matic
{
if (m1.rows != m2.rows || m1.cols != m2.cols) throw new MException("Matrices must have the same dimensions!");
Matrix r = new Matrix(m1.rows, m1.cols);
for (int i = 0; i < r.rows; i++)
for (int j = 0; j < r.cols; j++)
r[i, j] = m1[i, j] + m2[i, j];
return r;
}
public static string NormalizeMatrixString(string matStr) // From Andy - thank you! :)
{
// Remove any multiple spaces
while (matStr.IndexOf(" ") != -1)
matStr = matStr.Replace(" ", " ");
// Remove any spaces before or after newlines
matStr = matStr.Replace(" \r\n", "\r\n");
matStr = matStr.Replace("\r\n ", "\r\n");
// If the data ends in a newline, remove the trailing newline.
// Make it easier by first replacing \r\n’s with |’s then
// restore the |’s with \r\n’s
matStr = matStr.Replace("\r\n", "|");
while (matStr.LastIndexOf("|") == (matStr.Length - 1))
matStr = matStr.Substring(0, matStr.Length - 1);
matStr = matStr.Replace("|", "\r\n");
return matStr.Trim();
}
// O P E R A T O R S
public static Matrix operator -(Matrix m)
{ return Matrix.Multiply(-1, m); }
public static Matrix operator +(Matrix m1, Matrix m2)
{ return Matrix.Add(m1, m2); }
public static Matrix operator -(Matrix m1, Matrix m2)
{ return Matrix.Add(m1, -m2); }
public static Matrix operator *(Matrix m1, Matrix m2)
{ return Matrix.StrassenMultiply(m1, m2); }
public static Matrix operator *(long n, Matrix m)
{ return Matrix.Multiply(n, m); }
public static Matrix MultiplyModulo(Matrix A, Matrix B, long mod) // Smart matrix multiplication
{
if (A.cols != B.rows) throw new MException("Wrong dimension of matrix!");
Matrix R;
int msize = Math.Max(Math.Max(A.rows, A.cols), Math.Max(B.rows, B.cols));
R = ZeroMatrix(A.rows, B.cols);
for (int i = 0; i < R.rows; i++)
for (int j = 0; j < R.cols; j++)
for (int k = 0; k < A.cols; k++)
R[i, j] = (R[i, j] + (A[i, k] * B[k, j]) % mod) % mod;
return R;
}
}
// The class for exceptions
public class MException : Exception
{
public MException(string Message)
: base(Message)
{ }
}
}Dibs on Fibs CodeChef Solution in GO
package main
import (
"bufio"
"strconv"
"os"
"fmt"
)
func main() {
reader := bufio.NewReaderSize(os.Stdin, 1000000)
scanner := bufio.NewScanner(reader)
scanner.Split(bufio.ScanWords)
DBFB(scanner)
}
func DBFB(scanner *bufio.Scanner) {
testCases := nextInt(scanner)
Fibonacci()
for i := 0; i < testCases; i++ {
m := nextInt(scanner)
n := nextInt(scanner)
arr1 := make([]int64, m)
arr2 := make([]int64, m)
for j := 0; j < m; j++ {
arr1[j] = nextInt64(scanner)
}
for j := 0; j < m; j++ {
arr2[j] = nextInt64(scanner)
}
fmt.Println(GetResult(arr1, arr2, m, n))
}
}
func nextInt(scanner *bufio.Scanner) int {
scanner.Scan()
num, _ := strconv.Atoi(scanner.Text())
return num
}
func nextInt64(scanner *bufio.Scanner) int64 {
scanner.Scan()
var num int64
num, _ = strconv.ParseInt(scanner.Text(), 10, 64)
return num
}
const modVal = 1000000000+7
var FibArr [100000]int64
func GetResult(arr1, arr2 []int64, m, n int) int64 {
var res, sumA, sumB int64
for i := 0 ; i < m; i++ {
sumA = (sumA + arr1[i]) % modVal
sumB = (sumB + arr2[i]) % modVal
}
sumA = (sumA * int64(m)) % modVal
sumB = (sumB * int64(m)) % modVal
if n == 1 {
return sumA % modVal
}
if n == 2 {
return sumB % modVal
}
res = (FibArr[n-2] * sumB) % modVal + (FibArr[n - 3] * sumA) % modVal
return res % modVal
}
func Fibonacci() {
FibArr[0] = 1
FibArr[1] = 1
first := int64(1)
second := int64(1)
fib := (first + second)
for i := 2; i < 100000; i++ {
first = second
second = fib
FibArr[i] = fib
fib = (first + second) % modVal
}
}Dibs on Fibs CodeChef Solution Review:
In our experience, we suggest you solve this Dibs on Fibs CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Dibs on Fibs CodeChef Solution.
Conclusion:
I hope this Dibs on Fibs CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
