QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#654994 | #9225. Fibonacci Fusion | real_sigma_team# | TL | 75ms | 14632kb | C++17 | 1.7kb | 2024-10-18 23:38:43 | 2024-10-18 23:38:45 |
Judging History
answer
#include<bits/stdc++.h>
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;
std::unordered_map<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) {
ans += mp[sub(x, h)];
}
mp[h]++;
}
std::cout << ans;
}
详细
Test #1:
score: 100
Accepted
time: 42ms
memory: 13240kb
input:
6 50 8 8 5 72 354224848179261915070
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 75ms
memory: 14632kb
input:
28 200878223506436882933619847964496455022155117513398820563747455993172799881403389571477889821109288771413214004090719097929400406252135763028179112130390003528046316900603668569910008417315162907579003880220844686222148696041857432602133894827753998572080650383305777912447151917272483538029469449...
output:
27
result:
ok 1 number(s): "27"
Test #3:
score: -100
Time Limit Exceeded
input:
5187 2640352926124261912741724778991366987330659389621881876017670644497364093930668042530271338851702874394631009332660937266680740235862107353443518003194307853104942996827176097428402408674756368623972812842571069642405111849826172879369776309763468485788964245903781380419155348915131587410703749...