結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
ユーザー cp_newbiecp_newbie
提出日時 2023-08-08 02:15:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,481 bytes
コンパイル時間 2,638 ms
コンパイル使用メモリ 208,848 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-25 20:14:19
合計ジャッジ時間 3,423 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,948 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 WA -
testcase_12 AC 2 ms
6,944 KB
testcase_13 WA -
testcase_14 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using i64 = long long;

int P = 998244353;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b, T base=1) {
	T res = std::move(base);
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(i64 x) : x(norm(x % P)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};
template<class T>
struct Mat {
	std::vector<std::vector<T>> val;
	int n, m;
	Mat(int n, int m, int x=0) : n(n), m(m) {
		assert(x == 0 || (n == m && x == 1));
		val.resize(n, std::vector<T>(m));
		if (x == 1) {
			for (int i = 0; i < n; i++) {
				val[i][i] = 1;
			}
		}
	}
	Mat &operator*=(const T &rhs) {
		for (auto &row : val) {
			for (auto &x : row) {
				x *= rhs;
			}
		}
		return *this;
	}	
	friend Mat operator*(const Mat &lhs, const T &rhs) {
		Mat res = lhs;
		res *= rhs;
		return res;	
	}
	friend Mat operator*(const T &lhs, const Mat &rhs) {
		Mat res = rhs;
		res *= lhs;
		return res;
	}
	Mat &operator+=(const Mat &rhs) {
		assert(n == rhs.n && m == rhs.m);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				val[i][j] += rhs.val[i][j];
			}
		}
		return *this;
	}
	friend Mat operator+(const Mat &lhs, const Mat &rhs) {
		assert(lhs.n == rhs.n && lhs.m == rhs.m);
		Mat res = lhs;
		res += rhs;
		return res;
	}
	friend Mat operator*(const Mat &lhs, const Mat &rhs) {
		assert(lhs.m == rhs.n);
		Mat res(lhs.n, rhs.m);
		for (int k = 0; k < lhs.m; k++) {
			for (int i = 0; i < lhs.n; i++) {
				for (int j = 0; j < rhs.m; j++) {
					res.val[i][j] += lhs.val[i][k] * rhs.val[k][j];
				}
			}
		}
		return res;
	}
	Mat &operator*=(const Mat &rhs) {
		assert(m == rhs.n);
		auto res = (*this) * rhs;
		*this = std::move(res);
		return *this;
	}	
};

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int N, M;
	std::cin >> N >> M;

	P = M;

	auto a = std::vector<std::vector<Z>>({{1, 1}, {1, 0}});
	Mat<Z> A(2, 2);
	A.val = std::move(a);

	A = power(A, N, Mat<Z>(2, 2, 1));	

	Mat<Z> B(2, 1);
	B.val[1][0] = 1;

	A *= B;
	std::cout << A.val[1][0] << "\n"; 

	return 0;
}
0