結果
問題 | No.2989 Fibonacci Prize |
ユーザー | suisen |
提出日時 | 2024-12-14 18:13:12 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,625 bytes |
コンパイル時間 | 1,018 ms |
コンパイル使用メモリ | 94,272 KB |
実行使用メモリ | 83,896 KB |
最終ジャッジ日時 | 2024-12-14 18:13:33 |
合計ジャッジ時間 | 19,114 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 RE * 2 WA * 56 |
ソースコード
#include <cassert> #include <iostream> #include <map> #include <vector> void solve(int n, int m) { --m; std::map<std::pair<int, int>, int> memo; memo[{1 % n, 0}] = 0; int loop; std::vector<int> fib{ 1 % n }; for (int i = 1, x = 1 % n, y = 1 % n; ; ++i) { auto [it, inserted] = memo.try_emplace(std::make_pair(x, y), i); if (not inserted) { assert(it->second == 0); loop = i - it->second; break; } fib.push_back(x); y = (x + y) % n; std::swap(x, y); } std::vector<int> sm(loop + 1); for (int i = 0; i < loop; ++i) { sm[i + 1] = (sm[i] + fib[i]) % n; } assert(sm.back() == 0); std::vector<std::vector<int>> ms(n); std::vector<int> idx(loop); for (int i = 0; i < loop; ++i) { int siz = ms[sm[i]].size(); ms[sm[i]].push_back(i); idx[i] = siz; } long long ans = 0; // r=m if (fib[m % loop] == 0) ++ans; // r=m-1 { int lc = idx[m % loop], rc = ms[m % loop].size() - lc; ans += 1LL * lc * (m / loop + 1); ans += 1LL * rc * (m / loop); } // r<=m-2 for (int rm = 0; rm < loop; ++rm) { int lc = idx[rm], rc = ms[sm[rm]].size() - lc; if (m - rm - 1 < 0) break; int qmax = (m - rm - 1) / loop; ans += 1LL * lc * (qmax + 1) * (qmax + 2) / 2; ans += 1LL * rc * qmax * (qmax + 1) / 2; } std::cout << ans << '\n'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; solve(n, m); }