QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#743074 | #7024. Distance Between Sweethearts | SGColin | AC ✓ | 1079ms | 52980kb | C++17 | 2.4kb | 2024-11-13 18:09:39 | 2024-11-13 18:09:40 |
Judging History
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,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
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