QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#655001#9225. Fibonacci Fusionreal_sigma_team#WA 219ms13436kbC++171.8kb2024-10-18 23:40:442024-10-18 23:40:45

Judging History

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

  • [2024-10-18 23:40:45]
  • 评测
  • 测评结果:WA
  • 用时:219ms
  • 内存:13436kb
  • [2024-10-18 23:40:44]
  • 提交

answer

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

uint64_t mod = 1836311903ull * 1134903170;
uint64_t mod2 = 1836311903ull * 1134903170;

const int K = 2200;

uint64_t add(uint64_t a, uint64_t b) {
    return a + b >= mod ? a + b - mod : a + b;
}
uint64_t sub(uint64_t a, uint64_t b) {
    return a >= b ? a - b : a + mod - b;
}
uint64_t mul(uint64_t a, uint64_t b) {
    return 1ll * a * b % mod;
}

std::vector<uint64_t> st, hsh;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    {
        uint64_t a = 0, b = 1;
        st = {a, b};
        for (int i = 0; i < 1e6; ++i) {
            uint64_t c = add(a, b);
            st.push_back(c);
            a = b;
            b = c;
        }
        std::sort(st.begin(), st.end());
        st.resize(std::unique(st.begin(), st.end()) - st.begin());
    }

//    {
//        mod = (1ll << 61) - 1;
//        uint64_t a = 0, b = 1;
//        hsh = {a, b};
//        for (int i = 0; i < 1e7; ++i) {
//            uint64_t c = add(a, b);
//            hsh.push_back(c);
//            a = b;
//            b = c;
//        }
//        std::sort(hsh.begin(), hsh.end());
//    }

    int n;
    std::cin >> n;
    gp_hash_table<uint64_t, int> mp;
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        std::string s;
        std::cin >> s;
        uint64_t h = 0;
        for (auto x : s) {
            uint64_t h2 = add(h, h);
            uint64_t h4 = add(h2, h2);
            uint64_t h8 = add(h4, h4);
            h = add(add(h8, h2), x - '0');
        }
        for (auto x : st) {
            uint64_t need = sub(x, h);
            if (mp.find(need) != mp.end()) ans += mp[need];
        }
        mp[h]++;
    }
    std::cout << ans;
}

詳細信息

Test #1:

score: 100
Accepted
time: 46ms
memory: 12504kb

input:

6
50
8
8
5
72
354224848179261915070

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 69ms
memory: 12592kb

input:

28
200878223506436882933619847964496455022155117513398820563747455993172799881403389571477889821109288771413214004090719097929400406252135763028179112130390003528046316900603668569910008417315162907579003880220844686222148696041857432602133894827753998572080650383305777912447151917272483538029469449...

output:

27

result:

ok 1 number(s): "27"

Test #3:

score: -100
Wrong Answer
time: 219ms
memory: 13436kb

input:

5187
2640352926124261912741724778991366987330659389621881876017670644497364093930668042530271338851702874394631009332660937266680740235862107353443518003194307853104942996827176097428402408674756368623972812842571069642405111849826172879369776309763468485788964245903781380419155348915131587410703749...

output:

6086

result:

wrong answer 1st numbers differ - expected: '6073', found: '6086'