結果
問題 |
No.2989 Fibonacci Prize
|
ユーザー |
|
提出日時 | 2024-12-14 18:24:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,642 bytes |
コンパイル時間 | 1,022 ms |
コンパイル使用メモリ | 87,428 KB |
最終ジャッジ日時 | 2025-02-26 14:28:33 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 57 WA * 20 |
ソースコード
#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<int> mod_count(n); std::vector<int> idx(loop); for (int i = 0; i < loop; ++i) { idx[i] = mod_count[sm[i]]++; } long long ans = 0; // r=m if (fib[m % loop] == 0) ++ans; // r=m-1 if (m >= 1) { if (fib[(m - 1) % loop] == 0) ++ans; } if (m >= 2) { if ((fib[(m - 2) % loop] + fib[(m - 1) % loop]) % n == 0) ++ans; } // r<=m-2 for (int rm = 0; rm < loop; ++rm) { if (rm > m - 1) break; int lc = idx[rm], rc = mod_count[sm[rm]] - lc; int qmax = (m - rm - 1) / loop; ans += 1LL * lc * (qmax + 1) * (qmax + 2) / 2; ans += 1LL * rc * (qmax + 0) * (qmax + 1) / 2; } // l=1, r=m-2 if ((fib[m % loop] + 1) % n == 0) --ans; 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); }