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

• 問題: No.1521 Playing Musical Chairs Alone
• ユーザー: goodbaton
• 提出日時: 2021-05-28 23:33:50
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 113 ms / 2,000 ms
• コード長: 8,552 bytes
• コンパイル時間: 1,358 ms
• コンパイル使用メモリ: 128,736 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-07 10:40:32
• 合計ジャッジ時間: 3,497 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	32 ms; 5,248 KB
testcase_06	AC	23 ms; 5,248 KB
testcase_07	AC	41 ms; 5,248 KB
testcase_08	AC	4 ms; 5,248 KB
testcase_09	AC	4 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	70 ms; 5,248 KB
testcase_12	AC	2 ms; 5,248 KB
testcase_13	AC	2 ms; 5,248 KB
testcase_14	AC	2 ms; 5,248 KB
testcase_15	AC	75 ms; 5,248 KB
testcase_16	AC	90 ms; 5,248 KB
testcase_17	AC	86 ms; 5,248 KB
testcase_18	AC	78 ms; 5,248 KB
testcase_19	AC	79 ms; 5,248 KB
testcase_20	AC	89 ms; 5,248 KB
testcase_21	AC	88 ms; 5,248 KB
testcase_22	AC	81 ms; 5,248 KB
testcase_23	AC	71 ms; 5,248 KB
testcase_24	AC	82 ms; 5,248 KB
testcase_25	AC	113 ms; 5,248 KB

ソースコード

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>
#include <bitset>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include <cassert>
#include <functional>

using ll = long long;
using namespace std;

template<typename A, typename B>
bool chmin(A &a, const B b) {
  if (a <= b) return false;
  a = b;
  return true;
}

template<typename A, typename B>
bool chmax(A &a, const B b) {
  if (a >= b) return false;
  a = b;
  return true;
}

#ifndef LOCAL
#define debug(...) ;
#else
#define debug(...) cerr << __LINE__ << " : " << #__VA_ARGS__ << " = " << _tostr(__VA_ARGS__) << endl;

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v);

template<typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}

void _tostr_rec(ostringstream &oss) {
  oss << "\b\b \b";
}

template<typename Head, typename... Tail>
void _tostr_rec(ostringstream &oss, Head &&head, Tail &&...tail) {
  oss << head << ", ";
  _tostr_rec(oss, forward<Tail>(tail)...);
}

template<typename... T>
string _tostr(T &&...args) {
  ostringstream oss;
  int size = sizeof...(args);
  if (size > 1) oss << "{";
  _tostr_rec(oss, forward<T>(args)...);
  if (size > 1) oss << "}";
  return oss.str();
}
#endif

constexpr int mod = 1'000'000'007; //1e9+7(prime number)
constexpr int INF = 1'000'000'000; //1e9
constexpr ll LLINF = 2'000'000'000'000'000'000LL; //2e18
constexpr int SIZE = 200010;

template<int M = mod>
struct ModInt {
  using ll = long long;
  ll val;

  ModInt(ll x = 0): val(x >= 0 ? x % M : (x % M + M) % M) {}

  explicit operator bool() const { return val != 0; }

  ModInt operator+() const { return *this; }
  ModInt operator-() const { return ModInt(-val); }

  ModInt operator+(const ModInt &rhs) const { return ModInt(*this) += rhs; }
  ModInt operator-(const ModInt &rhs) const { return ModInt(*this) -= rhs; }
  ModInt operator*(const ModInt &rhs) const { return ModInt(*this) *= rhs; }
  ModInt operator/(const ModInt &rhs) const { return ModInt(*this) /= rhs; }

  bool operator==(const ModInt &rhs) const { return val == rhs.val; }
  bool operator!=(const ModInt &rhs) const { return val != rhs.val; }
  bool operator<(const ModInt &rhs) const { return val < rhs.val; }
  bool operator>(const ModInt &rhs) const { return val > rhs.val; }
  bool operator<=(const ModInt &rhs) const { return val <= rhs.val; }
  bool operator>=(const ModInt &rhs) const { return val >= rhs.val; }

  ModInt operator++() { return *this += 1; }
  ModInt operator--() { return *this -= 1; }
  ModInt operator++(int) { return ++*this, *this - 1; }
  ModInt operator--(int) { return --*this, *this + 1; }

  ModInt &operator+=(const ModInt &rhs) {
    val += rhs.val;
    if (val >= M) val -= M;
    return *this;
  }
  ModInt &operator-=(const ModInt &rhs) {
    val -= rhs.val;
    if (val < 0) val += M;
    return *this;
  }
  ModInt &operator*=(const ModInt &rhs) {
    val = val * rhs.val % M;
    return *this;
  }
  ModInt &operator/=(ModInt rhs) {
    for (int exp = M - 2; exp; exp /= 2) {
      if (exp % 2) *this *= rhs;
      rhs *= rhs;
    }
    return *this;
  }

  friend int abs(const ModInt &arg) {
    return arg.val;
  }

  friend ostream &operator<<(ostream &os, const ModInt &rhs) {
    return os << rhs.val;
  }

  friend istream &operator>>(istream &is, ModInt &rhs) {
    ll x;
    is >> x;
    rhs = ModInt(x);
    return is;
  }
};

template<typename T, typename U = double>
class Matrix {
  std::vector<std::vector<T>> val;

public:
  int H, W;

  Matrix(int H, int W, T init = 0): val(H, std::vector<T>(W, init)), H(H), W(W) {};

  template<typename T2, typename U2 = double>
  operator Matrix<T2, U2>() const {
    Matrix<T2, U2> res(H, W);
    for (int i = 0; i < H; i++)
      for (int j = 0; j < W; j++)
        res[i][j] = val[i][j];
    return res;
  }

  Matrix(std::initializer_list<std::initializer_list<T>> init)
    : val(init.size(), std::vector<T>(init.begin()->size())), H(init.size()), W(init.begin()->size()) {
    auto list_it = init.begin();
    for (int i = 0; i < H; i++) {
      auto it = list_it->begin();
      for (int j = 0; j < W; j++)
        if (it != list_it->end())
          val[i][j] = *it++;
      list_it++;
    }
  }

  std::vector<T> &operator[](size_t idx) { return val[idx]; }
  const std::vector<T> &operator[](size_t idx) const { return val[idx]; }

  const Matrix operator+() const { return *this; }

  const Matrix operator-() const {
    Matrix res(H, W);
    for (int i = 0; i < H; i++)
      for (int j = 0; j < W; j++)
        res[i][j] = -val[i][j];
    return res;
  }

  const Matrix operator+(const Matrix &m) const {
    assert(H == m.H && W == m.W);
    Matrix res(H, W);
    for (int i = 0; i < H; i++)
      for (int j = 0; j < W; j++)
        res.val[i][j] = val[i][j] + m[i][j];
    return res;
  }

  const Matrix operator-(const Matrix &m) const {
    assert(H == m.H && W == m.W);
    Matrix res(H, W);
    for (int i = 0; i < H; i++)
      for (int j = 0; j < W; j++)
        res.val[i][j] = val[i][j] - m[i][j];
    return res;
  }

  const Matrix operator*(const Matrix &m) const {
    assert(W == m.H);
    Matrix res(H, m.W);
    for (int i = 0; i < H; i++)
      for (int j = 0; j < m.W; j++)
        for (int k = 0; k < W; k++)
          res[i][j] += val[i][k] * m[k][j];
    return res;
  }

  Matrix &operator+=(const Matrix &m) {
    assert(H == m.H && W == m.W);
    for (int i = 0; i < H; i++)
      for (int j = 0; j < W; j++)
        val[i][j] += m[i][j];
    return *this;
  }

  Matrix &operator-=(const Matrix &m) {
    assert(H == m.H && W == m.W);
    for (int i = 0; i < H; i++)
      for (int j = 0; j < W; j++)
        val[i][j] -= m[i][j];
    return *this;
  }

  Matrix &operator*=(const Matrix &m) {
    assert(H == m.H && W == m.W);
    this->val = (*this * m).val;
    return *this;
  }

  const std::vector<std::vector<T>> &toVector() const { return val; }

  Matrix pow(ll N) {
    assert(H == W);
    Matrix res(H, W), k = *this;
    for (int i = 0; i < H; i++) res[i][i] = 1;
    for (; N; N /= 2) {
      if (N & 1) res = res * k;
      k = k * k;
    }
    return res;
  }

  Matrix<U, U> inv() const {
    assert(H == W);
    Matrix<U, U> tmp = *this, res(H, W);

    for (int i = 0; i < H; i++) res[i][i] = 1;

    for (int i = 0; i < H; i++) {
      int pivot = i;
      for (int j = i; j < H; j++)
        if (abs(tmp[j][i]) > abs(tmp[pivot][i]))
          pivot = j;

      assert(tmp[pivot][i] != 0); //逆行列は存在しない

      if (pivot != i) {
        swap(tmp[i], tmp[pivot]);
        swap(res[i], res[pivot]);
      }

      U p = 1 / tmp[i][i];
      for (int j = 0; j < H; j++) {
        tmp[i][j] *= p;
        res[i][j] *= p;
      }
      for (int j = 0; j < H; j++) {
        if (i != j) {
          U p = tmp[j][i];
          for (int k = 0; k < H; k++) {
            tmp[j][k] -= tmp[i][k] * p;
            res[j][k] -= res[i][k] * p;
          }
        }
      }
    }
    return res;
  }

  U det() const {
    assert(H == W);
    Matrix<U, U> v = *this;
    U res = 1;

    for (int i = 0; i < H; i++) {
      for (int j = i; j < H; j++) {
        if (v[j][i]) {
          swap(v[i], v[j]);
          if (i != j) res *= -1;
          break;
        }
      }

      U a = (U)1 / v[i][i];
      for (int j = i + 1; j < H; j++) {
        U b = v[j][i] * a;
        for (int k = 0; k < H; k++)
          v[j][k] -= v[i][k] * b;
      }
      res *= v[i][i];
    }

    return res;
  }

  friend ostream &operator<<(ostream &os, const Matrix &rhs) {
    for (int i = 0; i < rhs.H; i++) {
      os << (i == 0 ? "[[" : " [");
      for (int j = 0; j < rhs.W; j++) {
        os << rhs.val[i][j] << (j + 1 == rhs.W ? "]" : " ");
      }
      os << (i + 1 == rhs.H ? "]" : "\n");
    }
    return os;
  }
};

int main() {
  int N, L, K;

  cin >> N >> K >> L;

  Matrix<ModInt<>, ModInt<>> mat(N, N);

  for (int i = 0; i < N; i++) {
    for (int j = 1; j <= L; j++) {
      mat[i][(i + j) % N] = 1;
    }
  }

  auto ans = mat.pow(K);

  debug(mat, ans);

  for (int i = 0; i < N; i++) {
    cout << ans[0][i] << endl;
  }


  return 0;
}