結果
問題 | No.1050 Zero (Maximum) |
ユーザー |
|
提出日時 | 2020-05-08 21:36:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 3,305 bytes |
コンパイル時間 | 948 ms |
コンパイル使用メモリ | 78,792 KB |
最終ジャッジ日時 | 2025-01-10 08:17:04 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include <iostream>#include <vector>template <int MOD>struct ModInt {using lint = long long;int val;// constructorModInt(lint v = 0) : val(v % MOD) {if (val < 0) val += MOD;};// unary operatorModInt operator+() const { return ModInt(val); }ModInt operator-() const { return ModInt(MOD - val); }ModInt inv() const { return this->pow(MOD - 2); }// arithmeticModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }ModInt pow(lint n) const {auto x = ModInt(1);auto b = *this;while (n > 0) {if (n & 1) x *= b;n >>= 1;b *= b;}return x;}// compound assignmentModInt& operator+=(const ModInt& x) {if ((val += x.val) >= MOD) val -= MOD;return *this;}ModInt& operator-=(const ModInt& x) {if ((val -= x.val) < 0) val += MOD;return *this;}ModInt& operator*=(const ModInt& x) {val = lint(val) * x.val % MOD;return *this;}ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }// comparebool operator==(const ModInt& b) const { return val == b.val; }bool operator!=(const ModInt& b) const { return val != b.val; }// I/Ofriend std::istream& operator>>(std::istream& is, ModInt& x) noexcept { return is >> x.val; }friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }};constexpr int MOD = 1e9 + 7;using mint = ModInt<MOD>;template <class T>using Vector = std::vector<T>;template <class T>using Matrix = Vector<Vector<T>>;template <class T>Matrix<T> operator*(const Matrix<T>& a, const Matrix<T>& b) {int n = a.size(), m = b.size(), l = b.front().size();Matrix<T> ret(n, Vector<T>(l, 0));for (int i = 0; i < n; ++i) {for (int k = 0; k < l; ++k) {for (int j = 0; j < m; ++j) {ret[i][k] += a[i][j] * b[j][k];}}}return ret;}template <class T>Vector<T> operator*(const Matrix<T>& a, const Vector<T>& v) {int n = a.size(), m = v.size();Vector<T> ret(n, 0);for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {ret[i] += a[i][j] * v[j];}}return ret;}template <class T, class Int>Matrix<T> mpow(Matrix<T> b, Int n) {Matrix<T> ret(b.size(), Vector<T>(b.size(), 0));for (int i = 0; i < (int)b.size(); ++i) ret[i][i] = 1;while (n > 0) {if (n & 1) ret = ret * b;n >>= 1;b = b * b;}return ret;}void solve() {int m, k;std::cin >> m >> k;Matrix<mint> a(m, Vector<mint>(m, 0));for (int i = 0; i < m; ++i) {for (int j = 0; j < m; ++j) {a[i][(i + j) % m] += 1;a[i][(i * j) % m] += 1;}}a = mpow(a, k);std::cout << a[0][0] << std::endl;}int main() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);solve();return 0;}