結果
| 問題 | No.1521 Playing Musical Chairs Alone |
| コンテスト | |
| ユーザー |
 goodbaton
|
| 提出日時 | 2021-05-28 23:33:50 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 117 ms / 2,000 ms |
| コード長 | 8,552 bytes |
| コンパイル時間 | 1,252 ms |
| コンパイル使用メモリ | 124,820 KB |
| 最終ジャッジ日時 | 2025-01-21 20:21:03 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 |
ソースコード
#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;
}