test/EDPC-R.test.cpp

• View this file on GitHub
• Last update: 2023-01-19 10:12:43+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_1_A
• Link: https://atcoder.jp/contests/dp/submissions/38145011

Depends on

• matrix (行列) (src/math/matrix.hpp)
• modint (src/math/modint.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_1_A"

#include "../src/math/modint.hpp"
#include "../src/math/matrix.hpp"

// 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;
	std::cout << "Hello World" << std::endl;
}

/*
 * EDPC - R Walk
 * https://atcoder.jp/contests/dp/submissions/38145011
 */

#line 1 "test/EDPC-R.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all/ITP1_1_A"

#line 1 "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 "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 5 "test/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;
	std::cout << "Hello World" << std::endl;
}

/*
 * EDPC - R Walk
 * https://atcoder.jp/contests/dp/submissions/38145011
 */

Back to top page