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

提出ソース

結果

問題	No.1521 Playing Musical Chairs Alone
ユーザー	Slephy
提出日時	2022-11-18 12:19:58
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	122 ms / 2,000 ms
コード長	10,913 bytes
コンパイル時間	4,584 ms
コンパイル使用メモリ	270,888 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-09-19 19:42:02
合計ジャッジ時間	6,454 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	33 ms 6,940 KB
testcase_06	AC	25 ms 6,944 KB
testcase_07	AC	44 ms 6,940 KB
testcase_08	AC	5 ms 6,948 KB
testcase_09	AC	4 ms 6,944 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	73 ms 6,944 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	81 ms 6,940 KB
testcase_16	AC	97 ms 6,940 KB
testcase_17	AC	94 ms 6,944 KB
testcase_18	AC	86 ms 6,940 KB
testcase_19	AC	86 ms 6,944 KB
testcase_20	AC	96 ms 6,940 KB
testcase_21	AC	94 ms 6,940 KB
testcase_22	AC	88 ms 6,944 KB
testcase_23	AC	73 ms 6,944 KB
testcase_24	AC	87 ms 6,944 KB
testcase_25	AC	122 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

//#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);}


    // 添え字演算子のオーバーロード
    inline const vector<T>& operator [](size_t index) const{
        assert(0 <= index && index < height());
        return mat[index];
    }
    inline vector<T>& operator [](size_t index){
        assert(0 <= index && index < height());
        return mat[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;
}

yukicoder

結果

テストケース

ソースコード