結果
問題 |
No.2989 Fibonacci Prize
|
ユーザー |
|
提出日時 | 2024-12-14 17:05:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 965 bytes |
コンパイル時間 | 2,059 ms |
コンパイル使用メモリ | 197,768 KB |
最終ジャッジ日時 | 2025-02-26 14:26:00 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 WA * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m, p; cin >> n >> m; if(m <= 2){ cout << (n <= 1) + (n <= 2) << '\n'; return 0; } if(n == 1){ ll len = m - 2; cout << len * (len + 1) / 2 + 2 << '\n'; return 0; } vector<int> a = {1, 1}, cnt(n); a.reserve(2 * n); do{ a.emplace_back(a.rbegin()[1] + a.back()); if(a.back() >= n) a.back() -= n; }while(a.rbegin()[1] != 1 || a.back() != 1); a.pop_back(); a.pop_back(); const int r = a.size(), d = (m - 2) / r, rem = (m - 2) - r * d; int sv = 0; cnt[0]++; for(int i = 0; i < r; i++){ sv += a[i]; if(sv >= n) sv -= n; cnt[sv] += d; if(i < rem) cnt[sv]++; } ll ans = (a[(m - 1) % r] == 0) * 2; for(auto &&v : cnt) ans += (ll)(v) * (v - 1) / 2; cout << ans << '\n'; }