結果
問題 | No.1847 Good Sequence |
ユーザー |
![]() |
提出日時 | 2021-12-22 12:18:45 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 3,000 ms |
コード長 | 1,889 bytes |
コンパイル時間 | 3,687 ms |
コンパイル使用メモリ | 251,956 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-01 12:33:15 |
合計ジャッジ時間 | 5,235 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/modint>using namespace std;using Modint = atcoder::modint1000000007;struct Matrix{Modint a[10][11][10][11] = {};auto operator[](int i){ return a[i]; }auto operator[](int i) const { return a[i]; }Matrix operator*(const Matrix& b) const {Matrix c;for(int i0 = 0; i0 < 10; i0++) for(int i1 = 0; i1 <= i0 + 1; i1++){for(int i2 = 0; i2 < 10; i2++) for(int i3 = 0; i3 <= i2 + 1; i3++){for(int i4 = 0; i4 < 10; i4++) for(int i5 = 0; i5 <= i4 + 1; i5++){c[i0][i1][i4][i5] += a[i0][i1][i2][i3] * b[i2][i3][i4][i5];}}}return c;}Matrix& operator*=(const Matrix& b){ return *this = *this * b; }Matrix pow(uint64_t b){Matrix a = *this, c;for(int i0 = 0; i0 < 10; i0++) for(int i1 = 0; i1 <= i0 + 1; i1++) c[i0][i1][i0][i1] = 1;while(b){if(b & 1) c *= a;a *= a;b >>= 1;}return c;}};int main(){uint64_t L;int N, M;cin >> L >> N >> M;vector<bool> ng(N);while(M--){int K;cin >> K;ng[K - 1] = 1;}Matrix a;for(int i0 = 0; i0 < N; i0++) for(int i1 = 0; i1 <= i0 + 1; i1++){a[i0][i1][i0][min(i0, i1) + 1] = 1;}for(int i0 = 0; i0 < N; i0++) for(int i1 = 0; i1 <= i0 + 1; i1++){if(i0 == i1 && ng[i0]) continue;for(int i2 = 0; i2 < N; i2++) if(i0 != i2){a[i0][i1][i2][0] = 1;}}Matrix s;for(int i0 = 0; i0 < N; i0++) s[0][0][i0][0] = 1;s *= a.pow(L - 1);Modint ans = Modint::raw(N).pow(L);for(int i0 = 0; i0 < N; i0++) for(int i1 = 0; i1 <= i0 + 1; i1++){if(i0 == i1 && ng[i0]) continue;ans -= s[0][0][i0][i1];}cout << ans.val() << endl;}