QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#772393 | #9225. Fibonacci Fusion | RaresFelix | WA | 176ms | 153740kb | C++23 | 4.7kb | 2024-11-22 19:14:28 | 2024-11-22 19:14:28 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pl = pair<ll, ll>;
const ll MOD1 = 1e9 + 7;
//const ll MOD2 = 998244353;
const ll MOD2 = 1e9 + 9;
struct Big {
vi V;
Big(int v = 0) {
while(v) {
V.push_back(v % 10);
v /= 10;
}
if(V.empty()) V.push_back(0);
}
Big(string s) {
for(auto it : s)
V.push_back(it - '0');
reverse(V.begin(), V.end());
}
Big &operator+=(const Big &rhs) {
if(rhs.V.size() > V.size())
V.resize(rhs.V.size(), 0);
int t = 0;
for(int i = 0; i < (int)max(V.size(), rhs.V.size()); ++i) {
V[i] += rhs.V[i];
V[i] += t;
t = V[i] / 10;
V[i] %= 10;
}
while(t) {
V.push_back(t % 10);
t /= 10;
}
return *this;
}
Big operator+(const Big &rhs) {
return Big(*this) += rhs;
}
Big &operator-=(const Big &rhs) {
//assert((*this) >= rhs);
int t = 0;
for(int i = 0; i < (int)V.size(); ++i) {
V[i] += t;
V[i] -= rhs.V[i];
t = 0;
if(V[i] < 0) {
t = -1;
V[i] += 10;
}
}
assert(!t);
while((int)V.size() > 1 && !V.back()) V.pop_back();
return *this;
}
Big operator-(const Big &rhs) { return Big(*this) -= rhs; }
bool operator<=(const Big &rhs) const {
if(V.size() != rhs.V.size()) return V.size() <= rhs.V.size();
for(int i = (int)V.size() - 1; i >= 0; --i)
if(V[i] != rhs.V[i]) return V[i] < rhs.V[i];
return true;
}
bool operator<(const Big &rhs) const {
if(V.size() != rhs.V.size()) return V.size() <= rhs.V.size();
for(int i = (int)V.size() - 1; i >= 0; --i)
if(V[i] != rhs.V[i]) return V[i] < rhs.V[i];
return false;
}
friend istream &operator>>(istream &i, Big &that) {
string s;
i >> s;
that = Big(s);
return i;
}
friend ostream &operator<<(ostream &o, Big &that) {
for(int i = (int)(that.V.size()) - 1; i >= 0; --i)
o << that.V[i];
return o;
}
double approx_log() {
double val = 0;
double f = 1.;
for(int i = int(V.size()) - 1; i >= 0; --i) {
val = val + V[i] * f;
f /= 10;
}
const double phi = (1 + sqrt(5.)) / 2.;
double log_val = log(val) + log(10.) * (int(V.size()) - 1);
return log_val / log(phi);
}
ll operator%(const ll &rhs) {
ll re = 0;
for(int i = (int)V.size() - 1; i >= 0; --i) {
re = (re * 10 + V[i]) % rhs;
}
return re;
}
};
vector<pl> get_fibo_pairs() {
auto get_fib_mods = [&](int len, ll MOD) -> vector<ll> {
ll a = 0, b = 1, c;
vll V;
for(int i = 0; i < len; ++i) {
V.push_back(a);
c = (a + b) % MOD;
a = b;
b = c;
}
return V;
};
const int MAX_FIB_N = 4e6;
vll R1 = get_fib_mods(MAX_FIB_N, MOD1), R2 = get_fib_mods(MAX_FIB_N, MOD2);
vector<pl> S;
for(int i = 0; i < MAX_FIB_N; ++i) {
S.push_back({R1[i], R2[i]});
}
return S;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n;
cin >> n;
vector<Big> V(n);
for(int i = 0; i < n; ++i)
cin >> V[i];
vi Ord;
for(int i = 0; i < n; ++i) {
Ord.push_back(i);
}
sort(V.begin(), V.end());
auto S = get_fibo_pairs();
vector<pl> R;
for(auto it : V) {
R.push_back({it % MOD1, it % MOD2});
}
sort(R.begin(), R.end());
R.resize(unique(R.begin(), R.end()) - R.begin());
vi Fr(R.size(), 0);
int re = 0;
for(int i = 0; i < n; ++i) {
ll bound = ll(round(V[i].approx_log()));
ll r1 = V[i] % MOD1, r2 = V[i] % MOD2;
for(int j = bound + 2; j < bound + 5; ++j) {
///check S[j] - i
auto [s1, s2] = S[j];
ll f1 = (s1 - r1 + MOD1) % MOD1;
ll f2 = (s2 - r2 + MOD2) % MOD2;
pl f{f1, f2};
auto p = lower_bound(R.begin(), R.end(), f);
if(p != R.end() && *p == f) {
re += Fr[p - R.begin()];
}
}
++Fr[lower_bound(R.begin(), R.end(), pl{r1, r2}) - R.begin()];
}
cout << re << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 42ms
memory: 134444kb
input:
6 50 8 8 5 72 354224848179261915070
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 152ms
memory: 153740kb
input:
28 200878223506436882933619847964496455022155117513398820563747455993172799881403389571477889821109288771413214004090719097929400406252135763028179112130390003528046316900603668569910008417315162907579003880220844686222148696041857432602133894827753998572080650383305777912447151917272483538029469449...
output:
27
result:
ok 1 number(s): "27"
Test #3:
score: 0
Accepted
time: 176ms
memory: 152600kb
input:
5187 2640352926124261912741724778991366987330659389621881876017670644497364093930668042530271338851702874394631009332660937266680740235862107353443518003194307853104942996827176097428402408674756368623972812842571069642405111849826172879369776309763468485788964245903781380419155348915131587410703749...
output:
6073
result:
ok 1 number(s): "6073"
Test #4:
score: -100
Wrong Answer
time: 97ms
memory: 147600kb
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:
2118847371
result:
wrong answer 1st numbers differ - expected: '15003749259', found: '2118847371'