結果
問題 | 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;}}