1 / 3
Nov 2020

I am not getting what’s wrong in my code.
Here’s my code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;


class SkeletonCP {
    static final int mod = (int) 1e9 + 7;
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(System.out);
    static StringTokenizer str = new StringTokenizer("");
    static int a[][] = new int[50][50];
    static int I[][] = new int[50][50];

    public static void arrayInput(int[] a, int n) throws IOException {
        str = new StringTokenizer(in.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(str.nextToken());
        }
    }

    public static void arrayInput_2D(int a[][], int m) throws IOException {
        for (int i = 0; i < m; i++) {
            str = new StringTokenizer(in.readLine());
            for (int j = 0; j < m; j++) {
                a[i][j] = Integer.parseInt(str.nextToken());
            }
        }
    }

    public static void matrixShow(int a[][], int m) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                out.print(a[i][j] + " ");
            }
            out.println();
        }
    }

    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(in.readLine());
        while (t-- > 0) {
            str = new StringTokenizer(in.readLine());
            int m = Integer.parseInt(str.nextToken());
            int n = Integer.parseInt(str.nextToken());
            arrayInput_2D(a, m);
            matrixExp(a, m, n);
            matrixShow(I, m);
        }
        out.flush();
    }

    private static void matrixMul(int a[][], int b[][], int m) {
        int res[][] = new int[m][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                int c = 0;
                for (int k = 0; k < m; k++) {
                    c += (a[i][k] * b[k][j]) % mod;
                }
                res[i][j] = c;
            }
        }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                a[i][j] = res[i][j];

    }

    private static void matrixExp(int a[][], int m, int n) {
        for (int i = 0; i < m; i++)
            I[i][i] = 1;
        while (n != 0) {
            if (n % 2 != 0)
                matrixMul(I, a, m);
            matrixMul(a, a, m);
            n /= 2;
        }
    }
}
  • created

    Nov '20
  • last reply

    Dec '20
  • 2

    replies

  • 688

    views

  • 3

    users

Overflow?

Yeah, try

1
2 50
100000 100000
100000 100000

Expected answer

391291256 391291256
391291256 391291256

1 month later

First. Do not use int. Use long. When a and b are int’s, computing “(a*b) % mod” will overflow on the value (a * b).

Second. The matrix multiply calculation is incorrect. The calculation “c += (a * b) % mod” will eventually overflow the value of c. Use “c = (c + ((a * b) % mod)) % mod”.

The first observation is a generalizes to most mod problems at SPOJ. When a value fits in a Java integer, the calculation is performed using a Java long to prevent overflow.

The second observation generalizes for most mod problems at SPOJ. For complex calculations, each add or multiply will require a mod operation. In the matrix multiplication, there is an add and a multiply. Hence, two mods.