QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#772393#9225. Fibonacci FusionRaresFelixWA 176ms153740kbC++234.7kb2024-11-22 19:14:282024-11-22 19:14:28

Judging History

你现在查看的是最新测评结果

  • [2024-11-22 19:14:28]
  • 评测
  • 测评结果:WA
  • 用时:176ms
  • 内存:153740kb
  • [2024-11-22 19:14:28]
  • 提交

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'