#817473 (C++17) No.1521 Playing Musical Chairs Alone

• 問題: No.1521 Playing Musical Chairs Alone
• ユーザー: Slephy
• 提出日時: 2022-11-18 12:16:58
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 11,219 bytes
• コンパイル時間: 4,302 ms
• コンパイル使用メモリ: 259,220 KB
• 最終ジャッジ日時: 2025-02-08 21:15:30
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 14 TLE * 9

ソースコード

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
    #include <atcoder/all>
    using namespace atcoder;
    using mint = modint1000000007;
    // using mint = modint998244353;
    // using mint = modint;
    // const int MOD = mint::mod();
#endif
#ifdef LOCAL_DEBUG
    #define cout cout<<' '
#endif
using ll = long long;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
// constexpr int MOD = (int)1e9 + 7;
// constexpr int MOD = (int)998244353;
constexpr int INF = (int)1e9 + 1001010;
constexpr ll llINF = (ll)4e18 + 11000010;
constexpr double PI = 3.14159265358979;
constexpr double EPS = 1e-10;
#define Isize(x) (int)(size(x))
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define UNIQUE(x) (x).erase(unique(ALL(x)), (x).end());
#define endn "\n"
#define SUM(v) accumulate(ALL(v), 0LL)
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

template <class T> inline vector<vector<T>> vector2(const size_t &i, const size_t &j, const T &init = T()) {
    return vector<vector<T>>(i, vector<T>(j, init));
}
template <class T> inline vector<vector<vector<T>>> vector3(const size_t &i, const size_t &j, const int &k, const T &init = T()) {
    return vector<vector<vector<T>>>(i, vector<vector<T>>(j, vector<T>(k, init)));
}
template <class T> inline vector<vector<vector<vector<T>>>> vector4(const size_t &i, const size_t &j, const size_t &k, const size_t &l, const T &init = T()) {
    return vector<vector<vector<vector<T>>>>(i, vector<vector<vector<T>>>(j, vector<vector<T>>(k, vector<T>(l, init))));
}

const string VEC_ELEM_SEPARATION = " ";
const string VEC_VEC_SEPARATION = endn;
template<class T> istream & operator >> (istream &i, vector<T> &A) {for(auto &I : A) {i >> I;} return i;}
template<class T> ostream & operator << (ostream &o, const vector<vector<T>> &A) {int i=A.size(); for(auto &I : A){o << I << (--i ? VEC_VEC_SEPARATION : "");} return o;}
template<class T> ostream & operator << (ostream &o, const vector<T> &A) {int i=A.size(); for(auto &I : A){o << I << (--i ? VEC_ELEM_SEPARATION : "");} return o;}
template<class T> ostream & operator << (ostream &o, const deque<T> &A) {int i=A.size(); for(auto &I : A){o << I << (--i ? VEC_ELEM_SEPARATION : "");} return o;}
template<class T, class U> istream & operator >> (istream &i, pair<T,U> &A) {i >> A.first >> A.second; return i;}
template<class T, class U> ostream & operator << (ostream &o, const pair<T,U> &A) {o << A.first << " " << A.second; return o;}
template<class T, class U, class V> istream & operator >> (istream &i, tuple<T,U,V>&A) {i >> get<0>(A) >> get<1>(A) >> get<2>(A); return i;}
template<class T, class U, class V> ostream & operator << (ostream &o, const tuple<T,U,V> &A) {o << get<0>(A) << " " << get<1>(A) << " " << get<2>(A); return o;}

template<class T> vector<T>& operator ++(vector<T> &A, int n) {for(auto &I : A) {I++;} return A;}
template<class T> vector<T>& operator --(vector<T> &A, int n) {for(auto &I : A) {I--;} return A;}

template<class T, class U> bool chmax(T &a, const U &b){return ((a < b) ? (a = b, true) : false);}
template<class T, class U> bool chmin(T &a, const U &b){return ((a > b) ? (a = b, true) : false);}

ll floor(ll a, ll b){assert(b != 0); return((a%b != 0 && ((a>0) != (b>0))) ? a/b-1 : a/b);}
ll ceil (ll a, ll b){assert(b != 0); return((a%b != 0 && ((a>0) == (b>0))) ? a/b+1 : a/b);}
ll gcd(ll a, ll b){return ((b==0) ? a : gcd(b, a%b));}
ll lcm(ll a, ll b){return a / gcd(a,b) * b;}
bool is_in(ll inf, ll n, ll sup){return(inf <= n && n <= sup);}
// ================================== ここまでテンプレ ==================================

template<class T>
struct Matrix{
public:
    // コンストラクタ
    // Matrix(size_t h, size_t w, T init = T()) : mat(vector<vector<T>>(h, vector<T>(w, init))) {}
    Matrix(size_t h, size_t w, T init = T()) : mat(h, vector<T>(w, init)) {}
    Matrix(const vector<vector<T>> &mat) : mat(mat) {}
    Matrix(const Matrix<T> &mat) = default;
    Matrix(Matrix<T> &&mat) = default;

    // 代入演算子のオーバーロード
    Matrix<T>& operator = (const Matrix<T> &mat_) = default; // copy
    Matrix<T>& operator = (Matrix<T> &&mat_) = default;      // move

    // ゲッター
    inline size_t height() const {return mat.size();}
    inline size_t width() const {return ((height() > 0) ? mat[0].size() : 0);} // (TODO: 0行目がないときの対処)


    // 添え字演算子のオーバーロード
    inline const vector<T> operator [](int index) const{
        // assert(0 <= index && index < height());
        // return mat[index];
        return mat.at(index);
    }
    inline vector<T>& operator [](int index){
        // assert(0 <= index && index < height());
        // return mat[index];
        return mat.at(index);
    }

    // // イテレータ
    // auto begin() {return mat.begin();}
    // auto end()   {return mat.end();}

    // 入出力ストリーム
    friend istream & operator >> (istream &i, Matrix<T> &mat) {for(auto &I : mat) for(auto &J : I){i >> J;} return i;}
    friend ostream & operator << (ostream &o, const Matrix &A) {o << A.mat; return o;}

    // 単位行列
    static Matrix<T> identity(size_t size){
        Matrix<T> res(size, size, 0);
        for(int i = 0; i < size; i++){
            res[i][i] = 1;
        }
        return res;
    }
    // static Matrix<T> identity(const Matrix<T> &mat_like){
    //     assert(mat_like.height() == mat_like.width());
    //     return Matrix<T>::identity(mat_like.height()); // (TODO: コピーを避ける)
    // }
    // static Matrix<T> zero(size_t size){
    //     return Matrix<T>(size, size, 0);
    // }
    // static Matrix<T> zero(size_t height, size_t width){
    //     return Matrix<T>(height, width, 0);
    // }
    // static Matrix<T> zero(const Matrix<T> &mat_like){
    //     return Matrix<T>::zero(mat_like.height(), mat_like.width());
    // }

    // 算術演算子のオーバーロード
    // Matrix<T> operator +(){
    //     return *this;
    // }
    // Matrix<T> operator -(){
    //     Matrix<T> res(height(), width());
    //     for(int i = 0; i < height(); i++){
    //         for(int j = 0; j < width(); j++){
    //             res[i][j] = -mat[i][j];
    //         }
    //     }
    //     return res;
    // }
    Matrix<T>& operator +=(const Matrix<T> &other){
        assert(height() == other.height() && width() == other.width());
        for(int i = 0; i < height(); i++){
            for(int j = 0; j < width(); j++){
                (*this)[i][j] += other[i][j];
            }
        }
        return *this;
    }
    Matrix<T>& operator -=(const Matrix<T> &other){
        assert(height() == other.height() && width() == other.width());
        for(int i = 0; i < height(); i++){
            for(int j = 0; j < width(); j++){
                (*this)[i][j] -= other[i][j];
            }
        }
        return *this;
    }
    Matrix<T>& operator *=(const Matrix<T> &other){
        assert(width() == other.height());
        // Matrix<T> res(height(), other.width());
        vector<vector<T>> res(height(), vector<T>(other.width(), 0));
        for(int i = 0; i < height(); i++){
            for(int j = 0; j < other.width(); j++){
                for(int k = 0; k < width(); k++){
                    res[i][j] += (*this)[i][k] * other[k][j];
                    // res[i][j] = (res[i][j] + (*this)[i][k] * other[k][j]);
                }
            }
        }
        // swap(res, *this);
        mat.swap(res);
        return *this;
    }
    Matrix<T>& operator ^=(unsigned long long n){
        assert(height() == width());
        Matrix<T> res = Matrix<T>::identity(height());
        while(n > 0){
            if(n & 1) res *= *this;
            *this *= *this;
            n >>= 1;
        }
        swap(res, *this);
        return *this;
    }
    Matrix<T> operator +(const Matrix<T> &other) const {
        return Matrix<T>(*this) += other;
    }
    Matrix<T> operator -(const Matrix<T> &other) const {
        return Matrix<T>(*this) -= other;
    }
    Matrix<T> operator *(const Matrix<T> &other) const {
        return Matrix<T>(*this) *= other;
    }
    Matrix<T> operator ^(unsigned long long n) const {
        return Matrix<T>(*this) ^= n;
    }
    // friend Matrix<T>& operator +=(Matrix<T> &mat, const T &val){
    //     for(int i = 0; i < mat.height(); i++) for(int j = 0; j < mat.width(); j++) mat[i][j] += val;
    //     return mat;
    // }
    // friend Matrix<T>& operator -=(Matrix<T> &mat, const T &val){
    //     for(int i = 0; i < mat.height(); i++) for(int j = 0; j < mat.width(); j++) mat[i][j] -= val;
    //     return mat;
    // }
    // friend Matrix<T>& operator *=(Matrix<T> &mat, const T &val){
    //     for(int i = 0; i < mat.height(); i++) for(int j = 0; j < mat.width(); j++) mat[i][j] *= val;
    //     return mat;
    // }
    // friend Matrix<T> operator +(const Matrix<T> &mat, const T &val){
    //     Matrix<T> res(mat.height(), mat.width());
    //     for(int i = 0; i < mat.height(); i++) for(int j = 0; j < mat.width(); j++) res[i][j] = mat[i][j] + val;
    //     return res;
    // }
    // friend Matrix<T> operator +(const T &val, const Matrix<T> &mat){
    //     return mat + val;
    // }
    // friend Matrix<T> operator -(const Matrix<T> &mat, const T &val){
    //     Matrix<T> res(mat.height(), mat.width());
    //     for(int i = 0; i < mat.height(); i++) for(int j = 0; j < mat.width(); j++) res[i][j] = mat[i][j] - val;
    //     return res;
    // }
    // friend Matrix<T> operator -(const T &val, const Matrix<T> &mat){
    //     Matrix<T> res(mat.height(), mat.width());
    //     for(int i = 0; i < mat.height(); i++) for(int j = 0; j < mat.width(); j++) res[i][j] = val - mat[i][j];
    //     return res;
    // }
    // friend Matrix<T> operator *(const Matrix<T> &mat, const T &val){
    //     Matrix<T> res(mat.height(), mat.width());
    //     for(int i = 0; i < mat.height(); i++) for(int j = 0; j < mat.width(); j++) res[i][j] = mat[i][j] * val;
    //     return res;
    // }
    // friend Matrix<T> operator *(const T &val, const Matrix<T> &mat){
    //     return mat * val;
    // }


    // 行列累乗
    Matrix<T> pow(unsigned long long n) const{
        assert(height() == width());
        Matrix<T> res = Matrix<T>::identity(height());
        Matrix<T> tmp = *this;
        while(n > 0){
            if(n & 1) res *= tmp;
            tmp *= tmp;
            n >>= 1;
        }
        return res;
    }

// メンバ変数
private:
    vector<vector<T>> mat;
    // size_t h, w;
};

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

    int n, k, l; cin >> n >> k >> l;
    Matrix<mint> mat(n, n, 0);
    for(int i = 0; i < n; i++){
        for(int j = 1; j <= l; j++){
            mat[i][(i+j)%n] = 1;
        }
    }

    Matrix<mint> init(1, n, 0);
    init[0][0] = 1;

    // auto ans = init * mat.pow(k);
    auto ans = init * (mat^k);
    for(int i = 0; i < n; i++){
        cout << ans[0][i].val() << endn;
    }
    return 0;
}