//#define _GLIBCXX_DEBUG #include using namespace std; #if __has_include() #include 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 using pqg = priority_queue, greater>; // 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 inline vector> vector2(const size_t &i, const size_t &j, const T &init = T()) { return vector>(i, vector(j, init)); } template inline vector>> vector3(const size_t &i, const size_t &j, const int &k, const T &init = T()) { return vector>>(i, vector>(j, vector(k, init))); } template inline vector>>> vector4(const size_t &i, const size_t &j, const size_t &k, const size_t &l, const T &init = T()) { return vector>>>(i, vector>>(j, vector>(k, vector(l, init)))); } const string VEC_ELEM_SEPARATION = " "; const string VEC_VEC_SEPARATION = endn; template istream & operator >> (istream &i, vector &A) {for(auto &I : A) {i >> I;} return i;} template ostream & operator << (ostream &o, const vector> &A) {int i=A.size(); for(auto &I : A){o << I << (--i ? VEC_VEC_SEPARATION : "");} return o;} template ostream & operator << (ostream &o, const vector &A) {int i=A.size(); for(auto &I : A){o << I << (--i ? VEC_ELEM_SEPARATION : "");} return o;} template ostream & operator << (ostream &o, const deque &A) {int i=A.size(); for(auto &I : A){o << I << (--i ? VEC_ELEM_SEPARATION : "");} return o;} template istream & operator >> (istream &i, pair &A) {i >> A.first >> A.second; return i;} template ostream & operator << (ostream &o, const pair &A) {o << A.first << " " << A.second; return o;} template istream & operator >> (istream &i, tuple&A) {i >> get<0>(A) >> get<1>(A) >> get<2>(A); return i;} template ostream & operator << (ostream &o, const tuple &A) {o << get<0>(A) << " " << get<1>(A) << " " << get<2>(A); return o;} template vector& operator ++(vector &A, int n) {for(auto &I : A) {I++;} return A;} template vector& operator --(vector &A, int n) {for(auto &I : A) {I--;} return A;} template bool chmax(T &a, const U &b){return ((a < b) ? (a = b, true) : false);} template 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 Matrix{ public: // コンストラクタ // Matrix(size_t h, size_t w, T init = T()) : mat(vector>(h, vector(w, init))) {} Matrix(size_t h, size_t w, T init = T()) : mat(h, vector(w, init)) {} // Matrix(const vector> &mat) : mat(mat) {} Matrix(const Matrix &mat) = default; Matrix(Matrix &&mat) = default; // 代入演算子のオーバーロード Matrix& operator = (const Matrix &mat_) = default; // copy Matrix& operator = (Matrix &&mat_) = default; // move // ゲッター size_t height() const {return mat.size();} size_t width() const {return ((height() > 0) ? mat[0].size() : 0);} // (TODO: 0行目がないときの対処) // 添え字演算子のオーバーロード inline vector& operator [](int index){ assert(0 <= index && index < height()); return mat[index]; } inline const vector operator [](int index) const{ assert(0 <= index && index < height()); return mat[index]; } // // イテレータ // auto begin() {return mat.begin();} // auto end() {return mat.end();} // 入出力ストリーム friend istream & operator >> (istream &i, Matrix &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 identity(size_t size){ Matrix res(size, size, 0); for(int i = 0; i < size; i++){ res[i][i] = 1; } return res; } static Matrix identity(const Matrix &mat_like){ assert(mat_like.height() == mat_like.width()); return Matrix::identity(mat_like.height()); } static Matrix zero(size_t size){ return Matrix(size, size, 0); } static Matrix zero(size_t height, size_t width){ return Matrix(height, width, 0); } static Matrix zero(const Matrix &mat_like){ return Matrix::zero(mat_like.height(), mat_like.width()); } // 算術演算子のオーバーロード // Matrix operator +(){ // return *this; // } // Matrix operator -(){ // Matrix 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& operator +=(const Matrix &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& operator -=(const Matrix &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& operator *=(const Matrix &other){ assert(width() == other.height()); // Matrix res(height(), other.width()); vector> res(height(), vector(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& operator ^=(unsigned long long n){ assert(height() == width()); Matrix res = Matrix::identity(height()); while(n > 0){ if(n & 1) res *= *this; *this *= *this; n >>= 1; } swap(res, *this); return *this; } Matrix operator +(const Matrix &other) const { return Matrix(*this) += other; } Matrix operator -(const Matrix &other) const { return Matrix(*this) -= other; } Matrix operator *(const Matrix &other) const { return Matrix(*this) *= other; } Matrix operator ^(unsigned long long n) const { return Matrix(*this) ^= n; } // friend Matrix& operator +=(Matrix &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& operator -=(Matrix &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& operator *=(Matrix &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 operator +(const Matrix &mat, const T &val){ // Matrix 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 operator +(const T &val, const Matrix &mat){ // return mat + val; // } // friend Matrix operator -(const Matrix &mat, const T &val){ // Matrix 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 operator -(const T &val, const Matrix &mat){ // Matrix 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 operator *(const Matrix &mat, const T &val){ // Matrix 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 operator *(const T &val, const Matrix &mat){ // return mat * val; // } // 行列累乗 Matrix pow(unsigned long long n) const{ assert(height() == width()); Matrix res = Matrix::identity(height()); Matrix tmp = *this; while(n > 0){ if(n & 1) res *= tmp; tmp *= tmp; n >>= 1; } return res; } // メンバ変数 private: vector> mat; // size_t h, w; }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, k, l; cin >> n >> k >> l; Matrix 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 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; }