QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#743074#7024. Distance Between SweetheartsSGColinAC ✓1079ms52980kbC++172.4kb2024-11-13 18:09:392024-11-13 18:09:40

Judging History

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

  • [2024-11-13 18:09:40]
  • 评测
  • 测评结果:AC
  • 用时:1079ms
  • 内存:52980kb
  • [2024-11-13 18:09:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

constexpr int N = (1 << 11);
constexpr int mod = 998244353;

int a[N][N], b[N][N], c[N][N], testcase;

ll A[N], B[N], C[N], lst[N];

void FWT(ll *a, int n, int f) {
    for (int k = 1; k < n; k <<= 1)
        for (int i = 0; i < n; i += (k << 1))
            for (int j = 0; j < k; ++j) {
                if (f == 1) {
                    ll x = a[i + j];
                    ll y = a[i + j + k];
                    a[i + j] = x + y;
                    a[i + j + k] = x - y;
                } else {
                    ll x = a[i + j];
                    ll y = a[i + j + k];
                    a[i + j] = (x + y) / 2;
                    a[i + j + k] = (x - y) / 2;
                }
            }
}

inline void work() {
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    memset(lst, 0, sizeof(lst));
    int a1 = rd(), b1 = rd(), c1 = rd();
    int a2 = rd(), b2 = rd(), c2 = rd();
    rep(i, 0, a1) rep(j, 0, a2) a[abs(i - j)][i ^ j]++;
    rep(i, 0, b1) rep(j, 0, b2) b[abs(i - j)][i ^ j]++;
    rep(i, 0, c1) rep(j, 0, c2) c[abs(i - j)][i ^ j]++;

    ull ans = 0;
    rep(k, 0, 2000) {
        if (k) {
            rep(w, 0, N - 1) {
                a[k][w] += a[k - 1][w];
                b[k][w] += b[k - 1][w];
                c[k][w] += c[k - 1][w];
            }
        }
        rep(w, 0, N - 1) {
            A[w] = a[k][w];
            B[w] = b[k][w];
            C[w] = c[k][w];
        }
        FWT(A, N, 1); FWT(B, N, 1); FWT(C, N, 1);
        rep(w, 0, N - 1) A[w] = A[w] * B[w] * C[w];
        FWT(A, N, -1);
        rep(w, 0, N - 1) {
            ull num = A[w] - lst[w];
            ans += (k ^ w) * num;
        }
        rep(w, 0, N - 1) lst[w] = A[w];
    }
    printf("Case #%d: %llu\n", ++testcase, ans);
}

int main() {
    per(t, rd(), 1) work();
    return 0;
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 304ms
memory: 52896kb

input:

3
3 1 2 4 3 3
1 2 1 2 1 3
3 2 5 4 3 5

output:

Case #1: 3880
Case #2: 369
Case #3: 24728

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 1033ms
memory: 52980kb

input:

10
474 431 418 416 475 400
492 482 487 488 481 499
499 485 486 498 495 485
2000 50 100 200 2000 2000
1999 50 100 200 1998 1997
1999 100 50 200 1998 1997
1995 100 50 200 2000 2000
2000 100 100 100 2000 2000
2000 66 300 100 1995 2000
90 50 600 2000 1990 1800

output:

Case #1: 1733077153413584909
Case #2: 3455567571304141510
Case #3: 3590382470720836074
Case #4: 7430839420470979674
Case #5: 7405417838059708742
Case #6: 7405417923933950624
Case #7: 7409635628016931244
Case #8: 7360521863394701030
Case #9: 14724638002272683520
Case #10: 18310280976211709616

result:

ok 10 lines

Test #3:

score: 0
Accepted
time: 1079ms
memory: 52976kb

input:

10
0 0 0 0 0 0
0 0 0 0 2000 0
0 2000 0 2000 0 0
2000 0 2000 0 0 1000
0 2000 2000 1000 2000 0
2000 0 0 2000 2000 2000
2000 1000 1000 1000 0 1000
1000 2000 1000 1000 0 2000
1000 2000 0 2000 2000 1000
2000 1000 2000 2000 0 2000

output:

Case #1: 0
Case #2: 0
Case #3: 2668667000
Case #4: 3481312864224
Case #5: 7170622352475668
Case #6: 15318219825142720
Case #7: 1532830126493028050
Case #8: 3551576938263084184
Case #9: 7693454823803659554
Case #10: 15471446092771136240

result:

ok 10 lines