QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#685763#8340. 3 SumUESTC_NLNS#WA 9ms3772kbC++202.5kb2024-10-28 21:11:362024-10-28 21:11:40

Judging History

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

  • [2024-10-28 21:11:40]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:3772kb
  • [2024-10-28 21:11:36]
  • 提交

answer

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
using u64 = unsigned long long;
u64 base = 1331;
vector<u64> powb;

using ll = long long;
using i128 = ll;
const int mod = 1068299123;

ll qpow(ll x, ll y) {
    i128 ans = 1;
    for (; y; y >>= 1, x = (i128)x * x % mod) {
        if (y & 1) ans = ans * x % mod;
    }
    return ans;
}

int n, k;

bool check(const vector<int>& a) {
    for (int i = 0; i < k; ++i)
        if (a[i] != 9) return 0;
    return 1;
}
int main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    cin >> n >> k;
    ll M = qpow(10, k) - 1;
    vector<ll> a(n);

    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        reverse(s.begin(), s.end());
        // while (s.size() % k != 0) s.push_back('0');
        vector<int> ans(k);
        for (int i = 0; i < s.size(); i += k) {
            int carry = 0;
            for (int j = i; j < i + k && (carry == 0 && j < s.size()); ++j) {
                int t1 = (j - i) == s.size() ? '0' : s[i];
                ans[j - i] = ans[j - i] + t1 - '0' + carry;
                if (ans[j - i] >= 10) {
                    carry = 1;
                    ans[j - i] -= 10;
                }
            }

            if (carry == 1) {
                for (int j = 0; j < k && carry; ++j) {
                    ans[j] = ans[j] + carry;
                    if (ans[j] >= 10) {
                        carry = 1;
                        ans[j] -= 10;
                    }
                }
            }
            if (check(ans)) ans.assign(k, 0);
        }
        i128 tmp = 0;
        i128 f = 1;

        for (int i = 0; i < k; ++i, f = f * 10 % mod) {
            tmp = (tmp + f * ans[i]) % mod;
        }
        a[i] = tmp;
    }

    auto query = [&](ll x) -> int {
        unordered_map<ll, int> mp;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                ll a2 = (a[i] + a[j]) % mod;
                if (mp.find(a2) == mp.end()) {
                    mp[a2] = 1;
                } else {
                    mp[a2]++;
                }
            }
            int t = (x - a[i] + mod) % mod;
            if (mp.find(t) != mp.end())
                ans += mp[(x - a[i] + mod) % mod];
        }
        return ans;
    };
    cout << query(0) + query(M) + query((i128)2 * M % mod) << '\n';
}
/*
4 1
0
1
10
17
*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3580kb

input:

4 1
0
1
10
17

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: -100
Wrong Answer
time: 9ms
memory: 3772kb

input:

500 859
7118711592236878297922359501613604144948355616986970837340677671376753603836852811886591300370143151943368529129749813118476151865844255212534355441611481420938483178075143062691345257288242460282715389758789648541099090735875617822348551942134616963557723055980260082230902505269975518146286...

output:

2925

result:

wrong answer 1st numbers differ - expected: '0', found: '2925'