結果
問題 | 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=mif (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-2for (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);}