結果
問題 | No.2989 Fibonacci Prize |
ユーザー | suisen |
提出日時 | 2024-12-14 18:45:23 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,335 bytes |
コンパイル時間 | 863 ms |
コンパイル使用メモリ | 82,464 KB |
実行使用メモリ | 14,844 KB |
最終ジャッジ日時 | 2024-12-14 18:45:27 |
合計ジャッジ時間 | 3,587 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 76 WA * 1 |
ソースコード
#include <cassert> #include <iostream> #include <map> #include <vector> void solve(int n, int m) { --m; int w; std::vector<int> fib{ 1 % n }; for (int i = 1, x = 1 % n, y = 1 % n; ; ++i) { if (x == 1 % n and y == 0) { w = i; break; } fib.push_back(x); y = (x + y) % n; std::swap(x, y); } std::vector<int> sm(w + 1); for (int i = 0; i < w; ++i) sm[i + 1] = (sm[i] + fib[i]) % n; assert(sm.back() == 0); std::vector<int> num(n), idx(w); for (int i = 0; i < w; ++i) idx[i] = num[sm[i]]++; long long ans = 0; int fm = fib[m % w]; int fm1 = fib[(m + w - 1) % w]; int fm2 = fib[(m + w - 2) % w]; // f(m) = f(m-2)+f(m-1)+f(m)+...+f(0) + 1 // r=m ans += (fm % n == 0); // r=m-1 ans += (m >= 1 and fm1 % n == 0); ans += (m >= 2 and (fm1 + fm2) % n == 0); // r<=m-2 for (int rm = 0; rm < w; ++rm) if (rm <= m - 1) { int lc = idx[rm], rc = num[sm[rm]] - lc; int qmax = (m - 1 - rm) / w; ans += 1LL * lc * (qmax + 1) * (qmax + 2) / 2; ans += 1LL * rc * (qmax + 0) * (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); }