結果
問題 | No.2487 Multiple of M |
ユーザー |
👑 ![]() |
提出日時 | 2023-09-29 23:29:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 4,783 bytes |
コンパイル時間 | 949 ms |
コンパイル使用メモリ | 84,472 KB |
最終ジャッジ日時 | 2025-02-17 03:36:23 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
#line 1 "..\\Main.cpp" #include <iostream> #include <string> #include <vector> #include <numeric> #include <algorithm> #include <atcoder/modint> #line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\linear-modulo\\matrix-modulo.hpp" #line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\linear-modulo\\matrix-modulo.hpp" #include <cassert> #include <utility> namespace nachia{ template<class Elem> struct MatrixModulo{ private: int h; int w; std::vector<Elem> elems; public: MatrixModulo(int new_h=0, int new_w=0){ h = new_h; w = new_w; elems.assign(h * w, 0); } MatrixModulo(const MatrixModulo &) = default; int numRow() const { return h; } int numColumn() const { return w; } int height() const { return numRow(); } int width() const { return numColumn(); } typename std::vector<Elem>::iterator operator[](int y){ return elems.begin() + (y * w); } typename std::vector<Elem>::const_iterator operator[](int y) const { return elems.begin() + (y * w); } static MatrixModulo Identity(int idx){ auto res = MatrixModulo(idx, idx); for(int i = 0; i < idx; i++) res[i][i] = 1; return res; } void swapColumns(int x1, int x2){ assert(0 <= x1 && x1 < numColumn()); assert(0 <= x2 && x2 < numColumn()); for(int y=0; y<numRow(); y++) std::swap((*this)[y][x1], (*this)[y][x2]); } void swapRows(int y1, int y2){ assert(0 <= y1 && y1 < numRow()); assert(0 <= y2 && y2 < numRow()); for(int x=0; x<numColumn(); x++) std::swap((*this)[y1][x], (*this)[y2][x]); } MatrixModulo operator*(const MatrixModulo& r) const { assert(width() == r.height()); auto res = MatrixModulo(h, r.w); for (int i=0; i<h; i++) for (int j=0; j<w; j++) for (int k=0; k<r.w; k++) res[i][k] += (*this)[i][j] * r[j][k]; return res; } Elem det() const { assert(height() == width()); MatrixModulo g = *this; Elem ans = 1; for (int i=0; i<h; i++) { int tg = -1; for (int j=i; j<h; j++) { if (g[j][i].val() != 0) tg = j; } if (tg == -1) return 0; if (tg != i) ans = -ans; for (int j=0; j<h; j++) std::swap(g[i][j], g[tg][j]); tg = i; ans *= g[i][i]; Elem const_coeff = g[i][i].inv(); for (int j=0; j<h; j++) g[i][j] *= const_coeff; for (int j=i+1; j<h; j++) for(int k=h-1; k>=i; k--) g[j][k] -= g[j][i] * g[i][k]; } return ans; } int rank() const { MatrixModulo g = *this; int y = 0; for (int d=0; d<w; d++) { if(y == h) break; int tg = -1; for (int i=y; i<h; i++) { if (g[i][d].val() != 0){ tg = i; break; } } if (tg == -1) continue; for (int j=d; j<w; j++) std::swap(g[y][j], g[tg][j]); tg = y; Elem const_coeff = g[y][d].inv(); for (int j=d; j<w; j++) g[y][j] *= const_coeff; for (int i=y+1; i<h; i++) for(int j=w-1; j>=d; j--) g[i][j] -= g[i][d] * g[y][j]; y++; } return y; } MatrixModulo pow(unsigned long long i){ auto a = *this; auto res = Identity(height()); while(i){ if(i % 2 == 1) res = res * a; a = a * a; i /= 2; } return res; } }; } // namespace nachia #line 9 "..\\Main.cpp" using Modint = atcoder::static_modint<998244353>; using namespace std; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; pair<Modint, Modint> solve(i64 N, i64 M, i64 K, i64 Q = 1){ if(N == 0) return { 1, 0 }; i64 g = std::gcd(M, K); if(g == 1){ auto mat = nachia::MatrixModulo<Modint>(2,2); mat[0][0] = Modint(Q-1); mat[0][1] = Modint(Q); mat[1][0] = Modint(M-1)*(Q); mat[1][1] = Modint(M-2)*(Q) + Modint(Q-1); mat = mat.pow(N); // cout << "solve(" << N << ", " << M << ", " << K << ", " << Q << ") = "; // cout << "(" << mat[0][0].val() << ", " << (mat[0][1] * (M-1)).val() << ")" << endl; return make_pair(mat[0][0], mat[0][1] * (M-1)); } auto [c0, c1] = solve(N-1, M/g, K, Q*g); Modint a0 = (c1 * 1) * Q + c0 * (Q-1); Modint a1 = (c0 * (M-1) + c1 * (M - 2)) * Q + c1 * (Q-1); // cout << "solve(" << N << ", " << M << ", " << K << ", " << Q << ") = "; // cout << "(" << a0.val() << ", " << a1.val() << ")" << endl; return { a0, a1 }; } void testcase(){ i64 N, M, K; cin >> N >> M >> K; cout << solve(N,M,K).first.val() << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); testcase(); return 0; }