#325220 (C++14) No.801 エレベーター

提出ソース

結果

問題	No.801 エレベーター
ユーザー	a
提出日時	2019-03-17 23:10:45
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	5,172 bytes
コンパイル時間	1,923 ms
コンパイル使用メモリ	179,572 KB
実行使用メモリ	186,268 KB
最終ジャッジ日時	2024-07-08 02:03:08
合計ジャッジ時間	12,089 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,764 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	703 ms 6,940 KB
testcase_04	AC	641 ms 6,940 KB
testcase_05	AC	652 ms 6,944 KB
testcase_06	AC	637 ms 6,944 KB
testcase_07	AC	715 ms 6,940 KB
testcase_08	AC	735 ms 6,940 KB
testcase_09	AC	783 ms 6,940 KB
testcase_10	AC	625 ms 6,944 KB
testcase_11	AC	706 ms 6,944 KB
testcase_12	AC	655 ms 6,940 KB
testcase_13	TLE	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include "bits/stdc++.h"

using namespace std;

template <int p>
struct Modint
{
	int value;

	Modint() : value(0) {}
	Modint(long x) : value(x >= 0 ? x % p : (p + x % p) % p) {}

	inline Modint &operator+=(const Modint &b)
	{
		if ((this->value += b.value) >= p)
			this->value -= p;
		return (*this);
	}
	inline Modint &operator-=(const Modint &b)
	{
		if ((this->value += p - b.value) >= p)
			this->value -= p;
		return (*this);
	}
	inline Modint &operator*=(const Modint &b)
	{
		this->value = (int)((1LL * this->value * b.value) % p);
		return (*this);
	}
	inline Modint &operator/=(const Modint &b)
	{
		(*this) *= b.inverse();
		return (*this);
	}

	Modint operator+(const Modint &b) const { return Modint(*this) += b; }
	Modint operator-(const Modint &b) const { return Modint(*this) -= b; }
	Modint operator*(const Modint &b) const { return Modint(*this) *= b; }
	Modint operator/(const Modint &b) const { return Modint(*this) /= b; }

	inline Modint &operator++(int) { return (*this) += 1; }
	inline Modint &operator--(int) { return (*this) -= 1; }

	inline bool operator==(const Modint &b) const { return this->value == b.value; }
	inline bool operator!=(const Modint &b) const { return this->value != b.value; }
	inline bool operator<(const Modint &b) const { return this->value < b.value; }
	inline bool operator<=(const Modint &b) const { return this->value <= b.value; }
	inline bool operator>(const Modint &b) const { return this->value > b.value; }
	inline bool operator>=(const Modint &b) const { return this->value >= b.value; }

	//requires that "this->value and p are co-prime"
	// a_i * v + a_(i+1) * p = r_i
	// r_i = r_(i+1) * q_(i+1) * r_(i+2)
	// q == 1 (i > 1)
	// reference: https://atcoder.jp/contests/agc026/submissions/2845729 (line:93)
	inline Modint inverse() const
	{
		assert(this->value != 0);
		int r0 = p, r1 = this->value, a0 = 0, a1 = 1;
		while (r1)
		{
			int q = r0 / r1;
			r0 -= q * r1;
			swap(r0, r1);
			a0 -= q * a1;
			swap(a0, a1);
		}
		return Modint(a0);
	}

	friend istream &operator>>(istream &is, Modint<p> &a)
	{
		long t;
		is >> t;
		a = Modint<p>(t);
		return is;
	}
	friend ostream &operator<<(ostream &os, const Modint<p> &a)
	{
		return os << a.value;
	}
};

const int MOD = 1e9 + 7;

using Int = Modint<MOD>;

template<class T>
struct Matrix
{
	vector<vector<T>> A;

	Matrix(size_t n) : A(n, vector<T>(n, 0)) {}
	Matrix(size_t h, size_t w) : A(h, vector<T>(w, 0)) {}
	Matrix(vector<vector<T>> &X) : A(X) {}

	inline vector<T> &operator[](int idx) {return A[idx];}
	inline const vector<T> &operator[](int idx) const {return A[idx];}

	size_t height() const {return A.size();}
	size_t width()  const {return A[0].size();}

	//ex)auto E = Matrix<int>::E(3);
	static Matrix E(int n)
	{
		Matrix e(n);
		for (int i = 0; i < n; i++) e[i][i] = 1;
		return e;
	}

	Matrix operator+(const Matrix &B) const
	{
		size_t h = this->height(), w = this->width();
		assert(h == B.height() && w == B.width());
		Matrix C(h, w);
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
			{
				C[i][j] = (*this)[i][j] + B[i][j];
			}
		return C;
	}

	Matrix operator-(const Matrix &B)
	{
		size_t h = this->height(), w = this->width();
		assert(h == B.height() && w == B.width());
		Matrix C(h, w);
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
			{
				C[i][j] = (*this)[i][j] - B[i][j];
			}
		return C;
	}

	Matrix operator*(const Matrix &B)
	{
		size_t h = this->height(), x = this->width(), w = B.width();
		assert(x == B.height());
		Matrix C(h, w);
		for (size_t i = 0; i < h; i++)
			for (size_t k = 0; k < x; k++)
				for (size_t j = 0; j < w; j++)
				{
					C[i][j] += (*this)[i][k] * B[k][j];
				}
		return C;
	}

	Matrix &operator+=(const Matrix &B) { return (*this) = (*this) + B; }
	Matrix &operator-=(const Matrix &B) { return (*this) = (*this) - B; }
	Matrix &operator*=(const Matrix &B) { return (*this) = (*this) * B; }

	Matrix power(long k)
	{
		auto n = this->height();
		assert(k >= 0 && this->width() == n);
		auto R = Matrix<T>::E(n), C = Matrix(*this);
		while(k)
		{
			if (k&1) R *= C;
			C *= C;
			k >>= 1;
		}
		return R;
	}

	friend ostream &operator<<(ostream &o, const Matrix &A)
	{
		for (int i = 0; i < A.height(); i++)
		{
			for (int j = 0; j < A.width(); j++)
			{
				o << A[i][j] << " ";
			}
			o << endl;
		}
		return o;
	}
};

void solve()
{
	int n, m, k;
	cin >> n >> m >> k;
	//L -> R
	vector<vector<Int>> imos(n+2, vector<Int>(n+2));
	Matrix<Int> mv(n, n);
	while (m--)
	{
		int l, r;
		cin >> l >> r;
		r++;
		imos[l][l]++;
		imos[l][r]--;
		imos[r][l]--;
		imos[r][r]++;
	}
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= n+1; j++)
		{
			imos[i+1][j] += imos[i][j];
		}
	}
	for (int i = 0; i <= n+1; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			imos[i][j+1] += imos[i][j];
		}
	}

	Matrix<Int> dp(n, 1);
	dp[0][0] = 1;

	for (int l = 0; l < n; l++)
	{
		mv[l][l] = imos[l + 1][l + 1];
		//cout << l << ' ' << d << endl;
		for (int r = l + 1; r < n; r++)
		{
			mv[l][r] = mv[r][l] = imos[l + 1][r + 1];
		}
	}

	dp = mv.power(k) * dp;

	cout << dp[n-1][0] << endl;
}

int main(void)
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード