QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#605797 | #9225. Fibonacci Fusion | ucup-team3215# | TL | 297ms | 340228kb | C++23 | 1.6kb | 2024-10-02 19:40:33 | 2024-10-02 19:40:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
constexpr ll k = 3;
constexpr array<ll, k> mod{(ll) 1e9 + 7, 998244353, (ll) 1e6 + 3};
int main() {
cin.tie(0)->sync_with_stdio(false);
constexpr ll N = 1e7;
ld phi = log10((1 + sqrtl(5)) / 2);
vector<array<ll, k + 1>> fib(N);
fib[1] = fib[0] = {1, 1, 1, 1};
for (int i = 2; i < N; ++i) {
fib[i][0] = (int) (i * phi);
for (int j = 1; j <= k; ++j) {
fib[i][j] = (fib[i - 1][j] + fib[i - 2][j]) % mod[j - 1];
}
}
ll n;
cin >> n;
vector<string> a(n);
for (auto &i: a)cin >> i;
sort(a.begin(), a.end(), [&](const string &s, const string &t) {
if (s.size() != t.size())return s.size() < t.size();
return s < t;
});
map<array<ll, k>, ll> cnt;
ll res=0;
for (auto &x: a) {
array<ll, k> rem{};
for (int i = 0; i < k; ++i) {
ll cur = 0;
for (auto c: x) {
cur = (cur * 10 + (c - '0')) % mod[i];
}
rem[i] = cur;
}
auto it = lower_bound(fib.begin(), fib.end(), array<ll, 4>{(ll) x.size() - 5, 0, 0, 0});
for (; it[0][0] <= (x.size() + 5) && it != fib.end(); ++it) {
auto &v = *it;
array<ll, k> need{};
for(int i = 0;i < k;++i){
need[i] = (v[i + 1]-rem[i])%mod[i];
if(need[i] < 0)need[i] += mod[i];
}
res += cnt[need];
}
cnt[rem]++;
}
cout << res;
}
详细
Test #1:
score: 100
Accepted
time: 108ms
memory: 315632kb
input:
6 50 8 8 5 72 354224848179261915070
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 197ms
memory: 320992kb
input:
28 200878223506436882933619847964496455022155117513398820563747455993172799881403389571477889821109288771413214004090719097929400406252135763028179112130390003528046316900603668569910008417315162907579003880220844686222148696041857432602133894827753998572080650383305777912447151917272483538029469449...
output:
27
result:
ok 1 number(s): "27"
Test #3:
score: 0
Accepted
time: 297ms
memory: 340228kb
input:
5187 2640352926124261912741724778991366987330659389621881876017670644497364093930668042530271338851702874394631009332660937266680740235862107353443518003194307853104942996827176097428402408674756368623972812842571069642405111849826172879369776309763468485788964245903781380419155348915131587410703749...
output:
6073
result:
ok 1 number(s): "6073"
Test #4:
score: 0
Accepted
time: 190ms
memory: 321936kb
input:
200000 2 2 2 2 1 2 1 1 2 2 1 1 1 2 2 1 1 2 1 1 2 2 1 2 2 2 1 1 1 1 2 2 1 2 1 2 1 1 2 2 1 1 1 2 1 1 2 1 2 2 2 2 1 2 2 1 1 1 2 1 1 1 1 1 2 1 2 2 1 1 1 2 2 2 1 1 2 1 1 2 1 2 1 1 1 2 2 2 1 1 1 1 2 1 2 1 1 2 2 1 1 2 1 1 2 1 2 2 1 2 1 2 2 1 1 2 1 1 1 2 2 2 1 2 2 1 1 2 2 2 2 1 2 1 1 2 1 2 2 1 1 1 1 2 2 2 2...
output:
15003749259
result:
ok 1 number(s): "15003749259"
Test #5:
score: -100
Time Limit Exceeded
input:
200000 944176313232170622314 2590599414036674999101 753315073608896000424 9299685298577430049245 9361800333778142620806 8988699166328904060999 9606920674025578304023 4203331868598952026136 5183047027116137697788 3968714342776915029801 8130984095583566992354 3206443643596048048798 6248561214283254355...