Submission #38145011

---

Source Code Expand

#line 1 "/home/zawatin/compro/library/src/math/modint.hpp"
namespace zawa {

    template<long long mod>
    class modint {
    private:
        long long x;

    public:
        modint() : x(0) {}
        
        modint(long long x) : x((x % mod + mod) % mod) {}

        modint& operator+=(modint p) {
            x += p.x;
            if (x >= mod) x -= mod;
            return *this;
        }

        modint& operator-=(modint p) {
            x += mod - p.x;
            if (x >= mod) x -= mod;
            return *this;
        }

        modint& operator*=(modint p) {
            x = (1LL * x * p.x % mod);
            return *this;
        }

        modint& operator/=(modint p) {
            *this *= p.inv();
            return *this;
        }

        modint operator-() const {
            return modint(-x);
        }

        modint operator+(const modint& p) const {
            return modint(*this) += p;
        }

        modint operator-(const modint& p) const {
            return modint(*this) -= p;
        }

        modint operator*(const modint& p) const {
            return modint(*this) *= p;
        }

        modint operator/(const modint& p) const {
            return modint(*this) /= p;
        }

        long long val() {
            return x;
        }

        modint pow(long long p) {
            modint res(1), val(x);
            while(p) {
                if (p & 1) res *= val;
                val *= val;
                p >>= 1;
            }
            return res;
        }

        modint inv() {
            return pow(mod - 2);
        }
    };

}// namespace zawa
#line 2 "/home/zawatin/compro/library/src/math/matrix.hpp"

#include <vector>

namespace zawa {

template <class T = long long>
class matrix {
private:
	std::vector<std::vector<T>> dat;

public:
	std::size_t r, c;

	matrix(const std::vector<T>& dat) : dat(dat), r(dat.size()), c(dat[0].size())  {}
	matrix(std::size_t r, std::size_t c) : dat(r, std::vector<T>(c)), r(r), c(c) {}
	matrix(const matrix<T>& mat) : dat(mat.r, std::vector<T>(mat.c)), r(mat.r), c(mat.c) {
		for (std::size_t i = 0 ; i < r ; i++) {
			for (std::size_t j = 0 ; j < c ; j++) {
				dat[i][j] = mat[i][j];
			}
		}	
	}

	std::vector<T>& operator[](std::size_t i) {
		return dat[i];
	}
	const std::vector<T>& operator[](std::size_t i) const {
		return dat[i];
	}

	matrix& operator+=(const matrix<T>& mat) {
		for (std::size_t i = 0 ; i < r ; i++) {
			for (std::size_t j = 0 ; j < c ; j++) {
				dat[i][j] += mat[i][j];
			}
		}
		return *this;
	}
	matrix operator+(const matrix<T>& mat) {
		return matrix(*this) += mat;
	}

	matrix& operator-=(const matrix<T>& mat) {
		for (std::size_t i = 0 ; i < r ; i++) {
			for (std::size_t j = 0 ; j < c ; j++) {
				dat[i][j] -= mat[i][j];
			}
		}
		return *this;
	}
	matrix& operator-(const matrix<T>& mat) {
		return matrix(*this) -= mat;	
	}

	matrix operator*(const matrix<T>& mat) {
		matrix res(r, mat.c);
		for (std::size_t i = 0 ; i < r ; i++) {
			for (std::size_t j = 0 ; j < mat.c ; j++) {
				for (std::size_t k = 0 ; k < c ; k++) {
					res[i][j] += dat[i][k] * mat[k][j];
				}
			}
		}
		return res;
	}
	matrix operator*=(const matrix<T>& mat) {
		return (*this) = (*this) * mat;
	}

	matrix pow(long long p);
};

template <class T>
matrix<T> id_mul(std::size_t n) {
	matrix<T> res(n, n);
	for (std::size_t i = 0 ; i < n ; i++) {
		res[i][i] = 1;
	}
	return res;
}

template <class T>
matrix<T> matrix<T>::pow(long long p) {
	matrix<T> res = id_mul<T>(this->r);
	matrix<T> base(*this);
	while (p > 0) {
		if (p & 1) {
			res *= base;
		}
		base *= base;
		p >>= 1;
	}
	return res;
}

} // namespace zawa
#line 3 "EDPC-R.test.cpp"

using mint = zawa::modint<1000000007>;
using mat = zawa::matrix<mint>;

#include <iostream>

int main() {
	int N; std::cin >> N;
	long long K; std::cin >> K;
	mat G(N, N);
	for (int i = 0 ; i < N ; i++) {
		for (int j = 0 ; j < N ; j++) {
			int a; std::cin >> a;
			G[i][j] = a;
		}
	}
	G = G.pow(K);
	mint ans;
	for (int i = 0 ; i < N ; i++) {
		for (const mint& a : G[i]) {
			ans += a;
		}
	}
	std::cout << ans.val() << std::endl;
}

Submission Info

Compile Error

EDPC-R.test.cpp: In function ‘int main()’:
EDPC-R.test.cpp:19:13: warning: implicitly-declared ‘zawa::matrix<zawa::modint<1000000007> >& zawa::matrix<zawa::modint<1000000007> >::operator=(const zawa::matrix<zawa::modint<1000000007> >&)’ is deprecated [-Wdeprecated-copy]
/home/zawatin/compro/library/src/math/matrix.hpp:17:2: note: because ‘zawa::matrix<zawa::modint<1000000007> >’ has user-provided ‘zawa::matrix<T>::matrix(const zawa::matrix<T>&) [with T = zawa::modint<1000000007>]’
/home/zawatin/compro/library/src/math/matrix.hpp: In instantiation of ‘zawa::matrix<T> zawa::matrix<T>::operator*=(const zawa::matrix<T>&) [with T = zawa::modint<1000000007>]’:
/home/zawatin/compro/library/src/math/matrix.hpp:89:8:   required from ‘zawa::matrix<T> zawa::matrix<T>::pow(long long int) [with T = zawa::modint<1000000007>]’
EDPC-R.test.cpp:19:13:   required from here
/home/zawatin/compro/library/src/math/matrix.hpp:68:18: warning: implicitly-declared ‘zawa::matrix<zawa::modint<1000000007> >& zawa::matrix<zawa::modint<1000000007> >::operator=(const zawa::matrix<zawa::modint<1000000007> >&)’ is deprecated [-Wdeprecated-copy]
/home/zawatin/compro/library/src/math/matrix.hpp:17:2: note: because ‘zawa::matrix<zawa::modint<1000000007> >’ has user-provided ‘zawa::matrix<T>::matrix(const zawa::matrix<T>&) [with T = zawa::modint<1000000007>]’

Judge Result