結果
問題 |
No.1521 Playing Musical Chairs Alone
|
ユーザー |
![]() |
提出日時 | 2021-05-04 10:58:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 285 ms / 2,000 ms |
コード長 | 1,100 bytes |
コンパイル時間 | 3,729 ms |
コンパイル使用メモリ | 201,064 KB |
最終ジャッジ日時 | 2025-01-21 06:40:34 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; #pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define rep(i,n) for(int i=0; i<(int) (n); i++) const long long mod = 1000000007; vector<vector<int>> mul(vector<vector<int>>& xx, vector<vector<int>>& yy) { int a = xx.size(), b = yy[0].size(), c = yy.size(); vector<vector<int>> ans(a, vector<int>(b)); rep(i, a) { rep(j, b) { rep(k, c) { ans[i][j] += (long long)xx[i][k] * (long long)yy[k][j] % mod; if (mod <= ans[i][j])ans[i][j] -= mod; } } } return ans; } signed main() { int N, K, L; cin >> N >> K >> L; vector<vector<int>>path(N, vector<int>(N)), dp(N, vector<int>(N)); rep(i, N) { for (int j = 1; j <= L; j++) { path[i][(i + j) % N] = 1; } } rep(i, N) { dp[i][i] = 1; } for (; K; K >>= 1) { if (K & 1) { dp= mul(dp, path); } path = mul(path, path); } rep(i,N){ cout<<dp[0][i]<<endl; } }