結果
問題 | 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=mans += (fm % n == 0);// r=m-1ans += (m >= 1 and fm1 % n == 0);ans += (m >= 2 and (fm1 + fm2) % n == 0);// r<=m-2for (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);}