QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#694951#8340. 3 SumLegend_dyAC ✓295ms4076kbC++202.1kb2024-10-31 19:00:472024-10-31 19:00:49

Judging History

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

  • [2024-10-31 19:00:49]
  • 评测
  • 测评结果:AC
  • 用时:295ms
  • 内存:4076kb
  • [2024-10-31 19:00:47]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int mod = 1e18 + 9;
constexpr int base = 10;

void inc(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}
int add(int x, int y) {
    inc(x, y);
    return x;
}
int mul(int x, int y) {
    return __int128_t(x) * y % mod;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, K;
    cin >> n >> K;

    auto Mod = [&](string s) {
        reverse(s.begin(), s.end());
        int m = s.size();
        vector<int> b(K);
        for (int j = 0; j < s.size(); j++) {
            b[j % K] += s[j] - '0';
        }
        while (true) {
            bool ok = 1;
            for (int j = 0; j < K; j++) {
                if (b[j] >= 10) ok = 0;
            }
            if (ok) break;

            vector<int> c(K);
            for (int j = 0; j < K; j++) {
                c[j] += b[j] % 10;
                c[(j + 1) % K] += b[j] / 10;
            }
            b = move(c);
        }
        if (b == vector<int>(K, 9)) b = vector<int>(K, 0);
        return b;
    };
    auto Hash = [&](vector<int>b) {
        reverse(b.begin(), b.end());
        int hash = 0;
        for (int j = 0; j < K; j++) {
            hash = add(mul(hash, base), b[j]);
        }
        return hash;
    };


    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        
        a[i] = Hash(Mod(s));
    }
    

    int ans = 0;
    auto solve = [&](int val) {
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                for (int k = j; k < n; k++) {
                    if (add(add(a[i], a[j]), a[k]) == val) {
                        ans++;
                    }
                }
            }
        }
    };
    solve(0);

    int h1 = 0;
    for (int i = 0; i < K; i++) {
        h1 = add(mul(h1, base), 9);
    }
    solve(h1);


    int h2 = 1;
    for (int i = 0; i < K - 1; i++) {
        h2 = add(mul(h2, base), 9);
    }
    h2 = add(mul(h2, base), 8);
    solve(h2);

    cout << ans;

    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 1
0
1
10
17

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 74ms
memory: 3860kb

input:

500 859
7118711592236878297922359501613604144948355616986970837340677671376753603836852811886591300370143151943368529129749813118476151865844255212534355441611481420938483178075143062691345257288242460282715389758789648541099090735875617822348551942134616963557723055980260082230902505269975518146286...

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 295ms
memory: 4076kb

input:

500 17336
11871159223687829792235950161360414494835561698697083734067767137675360383685281188659130037014315194336852912974981311847615186584425521253435544161148142093848317807514306269134525728824246028271538975878964854109909073587561782234855194213461696355772305598026008223090250526997551814628...

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 108ms
memory: 3760kb

input:

500 1
751324443898124078584847834484321089092662321556147445230263526014359393841194947303407593948729802551881289193716611867931891257925091769456350249725997883453296895094445731130479434019358742162771547784250401546380268386074363779242500860317042151185119666027858022664683818314351285215150806...

output:

2327631

result:

ok 1 number(s): "2327631"

Test #5:

score: 0
Accepted
time: 106ms
memory: 3724kb

input:

500 2
408542968136435277974575411503179002415404345446801430469044749372949272333801248935236224652806667129749035002588943020176263162139056819871274824302889304493205266143688886696157147111754418731401856424401766968832165255416237731963027205324149660112574729610391396555581935236134531799950318...

output:

212002

result:

ok 1 number(s): "212002"

Test #6:

score: 0
Accepted
time: 250ms
memory: 3712kb

input:

500 11500
75411775796562109942642493394321873284995260953010112281856775261847503626737348402159485133662757032091519863427156582689971229143089317472838196453888261138079171290535429921921548971897026706656838415620603757605079012541561774699628665865662183868374645956694140356716037674688084770628...

output:

7675

result:

ok 1 number(s): "7675"

Test #7:

score: 0
Accepted
time: 241ms
memory: 3816kb

input:

500 11500
85355036663164764459816544518601485185320972076300982726542821424439713703229669576802138231401047471351087455159512255765325323540671792953715169122669767368905391325060775725733157611188832204902997772518104188947349204726490597030311894441123834099315122116302203972018409854605418988681...

output:

1070

result:

ok 1 number(s): "1070"

Test #8:

score: 0
Accepted
time: 1ms
memory: 3756kb

input:

1 11500
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...

output:

1

result:

ok 1 number(s): "1"

Extra Test:

score: 0
Extra Test Passed