結果
問題 | No.1521 Playing Musical Chairs Alone |
ユーザー |
![]() |
提出日時 | 2021-05-28 21:31:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 100 ms / 2,000 ms |
コード長 | 2,522 bytes |
コンパイル時間 | 4,706 ms |
コンパイル使用メモリ | 260,372 KB |
最終ジャッジ日時 | 2025-01-21 19:50:46 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint1000000007;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000001template <typename T,typename F0,typename F1>struct matrix{F0 func0;F1 func1;vector<vector<T>> value;int height,width;T init_value0,init_value1;matrix(vector<vector<T>> X,F0 f0,F1 f1,T iv0,T iv1):func0(f0),func1(f1){height = X.size();width = X[0].size();value = X;init_value0 = iv0,init_value1 = iv1;}matrix(int h,int w,F0 f0,F1 f1,T iv0,T iv1):func0(f0),func1(f1){vector<vector<T>> d(h,vector<T>(w,iv0));height = h,width = w;value = d;init_value0 = iv0,init_value1 = iv1;}void set_1(){for(int i=0;i<height;i++){for(int j=0;j<width;j++){if(i==j)value[i][j] = init_value1;else value[i][j]=init_value0;}}}void show(){for(int i=0;i<height;i++){for(int j=0;j<width;j++){if(j!=0)cout<<' ';cout<<value[i][j];}cout<<endl;}}matrix &operator=(const matrix &another){value = another.value;height = another.height;width = another.width;return *this;}matrix &operator*=(const matrix &another){matrix<T,decltype(func0),decltype(func1)> R(height,another.width,func0,func1,init_value0,init_value1);for(int i=0;i<R.value.size();i++){for(int j=0;j<R.value[i].size();j++){R.value[i][j]=init_value0;for(int k=0;k<width;k++){R.value[i][j] = func0(R.value[i][j],func1(value[i][k],another.value[k][j]));}}}value = R.value;return (*this);}matrix operator*(const matrix &another)const{return (matrix(*this)*=another);}matrix beki(long long cnt){matrix<T,decltype(func0),decltype(func1)> R(height,width,func0,func1,init_value0,init_value1);R.set_1();auto temp = *this;while(cnt!=0LL){if(cnt%2==1){R *= temp;}temp *= temp;cnt/=2;}return R;}};int main(){int N,K,L;cin>>N>>K>>L;vector<vector<mint>> A(N,vector<mint>(N,0));rep(i,N){for(int j=1;j<=L;j++){int t = (i+j)%N;A[t][i] ++;}}auto f0 = [](mint a,mint b){return a+b;};auto f1 = [](mint a,mint b){return a*b;};matrix<mint,decltype(f0),decltype(f1)> AA(A,f0,f1,0,1);AA = AA.beki(K);vector<vector<mint>> B(N,vector<mint>(1,0));B[0][0] = 1;matrix<mint,decltype(f0),decltype(f1)> BB(B,f0,f1,0,1);BB = AA * BB;rep(i,N){cout<<BB.value[i][0].val()<<endl;}return 0;}