QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#386483#8340. 3 SumJerryTclRE 135ms30740kbC++202.3kb2024-04-11 17:21:412024-04-11 17:21:42

Judging History

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

  • [2024-09-20 10:20:30]
  • hack成功,自动添加数据
  • (/hack/848)
  • [2024-04-11 17:21:42]
  • 评测
  • 测评结果:RE
  • 用时:135ms
  • 内存:30740kb
  • [2024-04-11 17:21:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, K, ans = 0; cin >> n >> K;
    vector<string> s(n + 1); s[0].assign(K, 9);
    for(int i = 1; i <= n; ++i) {
        cin >> s[i], reverse(s[i].begin(), s[i].end());
        for(char &ch : s[i]) ch -= 48;
        const int l = (int)s[i].size() - K;
        for(int w = l - 1; w >= 0; ) {
            s[i][w] += s[i][w + K], s[i][w + K] = 0;
            if(s[i][w] >= 10) s[i][w] -= 10, ++s[i][w + 1];
            while(w >= 0 && !s[i][w + K]) --w;
        }
        s[i].resize(K); if(s[i] == s[0]) s.assign(K, 0);
    }
    vector<vector<bitset<501>>> r(n + 1);
    for(auto &it : r) it.resize(n + 1);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j) r[i][j].set();
    const auto &check = [&](const int64 mod) {
        unordered_map<int64, bitset<501>> M;
        vector<int64> t(n + 1);
        for(int i = 0, j; i <= n; t[i++] %= mod) {
            for(j = K - 1; j >= 3; j -= 4)
                t[i] = (t[i] * 10000 + s[i][j] * 1000 \
                    + s[i][j - 1] * 100 + s[i][j - 2] * 10 + s[i][j - 3]) % mod;
            while(j >= 0) t[i] = t[i] * 10 + s[i][j--];
        }
        const auto &add = [&](int64 x, int64 y)
            { return x + y >= mod ? x + y - mod : x + y; };
        const auto &sub = [&](int64 x, int64 y)
            { return x - y < 0 ? x - y + mod : x - y; };
        for(int i = 1; i <= n; ++i) {
            M[t[i]].set(i);
            for(int j = i; j <= n; ++j) {
                const int64 k = add(t[i], t[j]);
                const int64 v0 = k ? sub(t[0], k) : 0;
                const int64 v1 = add(t[0], v0);
                if(M.count(v0) && M.count(v1))
                    r[i][j] &= M[v0] | M[v1];
                else if(M.count(v0)) r[i][j] &= M[v0];
                else if(M.count(v1)) r[i][j] &= M[v1];
                else r[i][j].reset();
            }
        }
    };
    check(0x66ccff'ff0000 + 43);
    check(0x66ccff'ff0000 + 61);
    check(0x66ccff'ff0000 + 157);
    check(0x66ccff'ff0000 + 215);
    check(0x66ccff'ff0000 + 263);
    for(int i = 1; i <= n; ++i)
        for(int j = i; j <= n; ++j)
            ans += r[i][j].count(); printf("%d\n", ans);
}

詳細信息

Test #1:

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

input:

4 1
0
1
10
17

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 33ms
memory: 20192kb

input:

500 859
7118711592236878297922359501613604144948355616986970837340677671376753603836852811886591300370143151943368529129749813118476151865844255212534355441611481420938483178075143062691345257288242460282715389758789648541099090735875617822348551942134616963557723055980260082230902505269975518146286...

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 135ms
memory: 30740kb

input:

500 17336
11871159223687829792235950161360414494835561698697083734067767137675360383685281188659130037014315194336852912974981311847615186584425521253435544161148142093848317807514306269134525728824246028271538975878964854109909073587561782234855194213461696355772305598026008223090250526997551814628...

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: -100
Runtime Error

input:

500 1
751324443898124078584847834484321089092662321556147445230263526014359393841194947303407593948729802551881289193716611867931891257925091769456350249725997883453296895094445731130479434019358742162771547784250401546380268386074363779242500860317042151185119666027858022664683818314351285215150806...

output:


result: