結果
問題 | No.2857 Div Array |
ユーザー |
|
提出日時 | 2024-08-25 14:31:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 4,947 bytes |
コンパイル時間 | 2,148 ms |
コンパイル使用メモリ | 212,972 KB |
最終ジャッジ日時 | 2025-02-24 01:10:34 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/modint>#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")using namespace std;using mint = atcoder::modint998244353;template <typename T>class Matrix {public:Matrix() {}explicit Matrix(int N) : Matrix(N, N) {}explicit Matrix(int H, int W) : mat(H, vector<T>(W)) {}int height() const {return (int) mat.size();}int width() const {return (int) mat[0].size();}const std::vector<T> &operator[](int k) const {return mat[k];}std::vector<T> &operator[](int k) {return mat[k];}static inline Matrix I(int N) {Matrix ret(N);for(int i = 0; i < N; i++) ret[i][i] = T(1);return ret;}Matrix &operator+=(const Matrix &other) {int H = height();int W = width();assert(H == other.height() && W == other.width());for(int i = 0; i < H; i++) {for(int j = 0; j < W; j++) {(*this)[i][j] += other[i][j];}}return (*this);}Matrix &operator+=(T X) {int H = height();int W = width();for(int i = 0; i < H; i++) {for(int j = 0; j < W; j++) {mat[i][j] += X;}}return (*this);}Matrix &operator-=(const Matrix &other) {int H = height();int W = width();assert(H == other.height() && W == other.width());for(size_t i = 0; i < H; i++) {for(size_t j = 0; j < W; j++) {(*this)[i][j] -= other[i][j];}}return (*this);}Matrix &operator-=(T X) {int H = height();int W = width();for(int i = 0; i < H; i++) {for(int j = 0; j < W; j++) {mat[i][j] -= X;}}return (*this);}Matrix &operator*=(T X) {int H = height();int W = width();for(int i = 0; i < H; i++) {for(int j = 0; j < W; j++) {mat[i][j] *= X;}}return (*this);}Matrix &operator/=(T X) {int H = height();int W = width();for(int i = 0; i < H; i++) {for(int j = 0; j < W; j++) {mat[i][j] /= X;}}return (*this);}Matrix operator+(const Matrix &other) const {return (Matrix(*this) += other);}Matrix operator+(T X) const {return (Matrix(*this) += X);}Matrix operator-(const Matrix &other) const {return (Matrix(*this) -= other);}Matrix operator-(T X) const {return (Matrix(*this) -= X);}Matrix operator*(T X) const {return (Matrix(*this) *= X);}Matrix operator/(T X) const {return (Matrix(*this) /= X);}Matrix mat_mul(Matrix &other) {int h0 = height();int w0 = width();int h1 = other.height();int w1 = other.width();assert(w0 == h1);vector<vector<T>> ret(h0, vector<T>(w1, T(0)));for(int i = 0; i < h0; i++) {for(int j = 0; j < w1; j++) {for(int k = 0; k < w0; k++) {ret[i][j] += (*this)[i][k] * other[k][j];}}}this->mat.swap(ret);return (*this);}Matrix pow(long long k) const {Matrix A = (*this);assert(height() == width());Matrix ret = Matrix::I(height());while(k) {if(k & 1) {ret.mat_mul(A);}A.mat_mul(A);k >>= 1LL;}return ret;}T sum() {Matrix A = (*this);T ret = 0;int h = height();int w = width();for(int i = 0; i < h; i++) {for(int j = 0; j < w; j++) {ret += A[i][j];}}return T(ret);}vector<T> rsum() {Matrix A = (*this);int h = height();int w = width();vector<T> ret(h, T(0));for(int i = 0; i < h; i++) {for(int j = 0; j < w; j++) {ret[i] += A[i][j];}}return ret;}private:std::vector<std::vector<T>> mat;};int main() {cin.tie(0); cout.tie(0);ios::sync_with_stdio(false);int N, M, K;cin >> N >> M >> K;vector<int> C(M + 1);for(int i = 1; i <= M; i++) {C[M / i]++;}vector<int> I(M + 1), V;int sz = 0;for(int i = 0; i <= M; i++) {if(C[i] > 0) {I[i] = sz++;V.emplace_back(C[i]);}}assert(accumulate(V.begin(), V.end(), 0) == M);assert(accumulate(C.begin(), C.end(), 0) == M);Matrix<mint> m(sz);for(int i = 0; i <= M; i++) {if(C[i] == 0) {continue;}for(int j = 0; j <= M; j++) {if(C[j] == 0) {continue;}if(abs(i - j) <= K) {m[I[j]][I[i]] += C[j];}}}m = m.pow(N - 1);mint ans = 0;for(int i = 0; i < sz; i++) {for(int j = 0; j < sz; j++) {ans += m[i][j] * V[j];}}cout << ans.val() << '\n';return 0;}