結果
問題 | No.2576 LCM Pattern |
ユーザー |
|
提出日時 | 2023-12-06 14:40:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,298 bytes |
コンパイル時間 | 1,156 ms |
コンパイル使用メモリ | 87,472 KB |
最終ジャッジ日時 | 2025-02-18 08:29:21 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 TLE * 1 -- * 12 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<numeric>#include<atcoder/modint>using namespace std;using namespace atcoder;using ll=long long;using mint=modint998244353;#define all(v) v.begin(),v.end()#define rall(v) v.rbegin(),v.rend()template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;}template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;}template <class T>struct Matrix {vector<vector<T>> A;Matrix(int n, int m) : A(n, vector<T>(m, 0)) {}Matrix(int n) : A(n, vector<T>(n, 0)) {}int height() const {return (A.size());}int width() const {return (A[0].size());}const vector<T> &operator[](int k) const {return (A[k]);}vector<T> &operator[](int k) {return (A[k]);}static Matrix I(int n) {Matrix mat(n);for (int i = 0; i < n; i++) mat[i][i] = 1;return mat;}Matrix &operator+=(const Matrix &B) {int n = height(), m = width();assert(n == B.height() && m == B.width());for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {(*this)[i][j] += B[i][j];}}return (*this);}Matrix &operator-=(const Matrix &B) {int n = height(), m = width();assert(n == B.height() && m == B.width());for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {(*this)[i][j] -= B[i][j];}}return (*this);}Matrix &operator*=(const Matrix &B) {int n = height(), m = B.width(), p = width();assert(p == B.height());vector<vector<T>> C(n, vector<T>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int k = 0; k < p; k++) {C[i][j] += (*this)[i][k] * B[k][j];}}}A.swap(C);return (*this);}Matrix &operator^=(long long k) {int n = height();assert(n == width());Matrix B = Matrix::I(n);while (k > 0) {if (k & 1) B *= *this;*this *= *this;k >>= 1LL;}A.swap(B.A);return (*this);}Matrix operator+(const Matrix &B) const {return (Matrix(*this) += B);}Matrix operator-(const Matrix &B) const {return (Matrix(*this) -= B);}Matrix operator*(const Matrix &B) const {return (Matrix(*this) *= B);}Matrix operator^(const long long k) const {return (Matrix(*this) ^= k);}};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int N,M;cin>>N>>M;vector<int>V;for(int x=1;x*x<=M;x++){if(M%x==0){V.push_back(x);if(x*x<M)V.push_back(M/x);}}sort(all(V));int L=V.size();Matrix<mint>mat(L);for(int i=0;i<L;i++){for(int j=0;j<L;j++){for(int k=0;k<L;k++){if(lcm(V[j],V[k])==V[i])mat[i][j]++;}}}mat^=N-1;mint ans=0;for(int i=0;i<L;i++)ans+=mat[L-1][i];cout<<ans.val()<<"\n";}