QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#323410 | #7302. Walk of Length 6 | ckiseki | AC ✓ | 19ms | 12408kb | C++20 | 4.0kb | 2024-02-09 17:30:24 | 2024-02-09 17:30:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
#include <experimental/iterator>
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
int64_t comb(int64_t a, int64_t b) {
if (a < b)
return 0;
b = min(b, a - b);
int64_t ans = 1;
for (int i = 0; i < b; ++i)
ans *= a - i;
for (int i = 1; i <= b; ++i)
ans /= i;
return ans;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
while (cin >> n) {
vector<string> a(n);
for (auto &ai : a)
cin >> ai;
vector<bitset<1000>> g(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
g[i][j] = a[i][j] - '0';
}
}
vector<int64_t> d(n);
for (int i = 0; i < n; ++i)
d[i] = int(g[i].count());
vector<vector<int64_t>> intersect(n, vector<int64_t>(n, 0));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
intersect[i][j] = (g[i] & g[j]).count();
auto Count1 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (not g[i][j])
continue;
ans += (d[i] - 1) * (d[j] - 1);
ans -= intersect[i][j];
}
}
return ans;
};
auto Count2 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i)
ans += comb(d[i], 2);
return ans;
};
auto Count3 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i)
ans += d[i];
assert(ans % 2 == 0);
return ans / 2;
};
auto Count4 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i)
ans += comb(d[i], 3);
return ans;
};
auto Count5 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (g[i][j])
ans += intersect[i][j];
assert(ans % 3 == 0);
return ans / 3;
};
auto Count7 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (not g[i][j])
continue;
ans += comb(intersect[i][j], 2);
}
}
return ans;
};
auto Count6 = [&] {
int64_t ans = 0;
vector<int64_t> count(n);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (not g[i][j])
continue;
count[i] += intersect[i][j];
count[j] += intersect[i][j];
}
}
for (int i = 0; i < n; ++i)
ans += comb(count[i] / 2, 2);
return ans - Count7() * 2;
};
auto Count8 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
ans += comb(intersect[i][j], 2);
assert(ans % 2 == 0);
return ans / 2;
};
auto Count9 = [&] {
int64_t ans = 0;
for (int i = 0; i < n; ++i) {
if (d[i] < 3)
continue;
for (int j = 0; j < n; ++j) {
if (i == j)
continue;
int64_t cur = comb(intersect[i][j], 2);
ans += cur * (d[i] - 2 - g[i][j]);
}
}
return ans;
};
int64_t ans = 0;
ans += 6 * Count1();
ans += 12 * Count2();
ans += 2 * Count3();
ans += 12 * Count4();
ans += 24 * Count5();
ans += 24 * Count6();
ans += 36 * Count7();
ans += 48 * Count8();
ans += 12 * Count9();
cout << ans << '\n';
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
input:
3 011 101 110 4 0101 1010 0101 1010 6 011111 101111 110111 111011 111101 111110
output:
66 128 14910
result:
ok 3 number(s): "66 128 14910"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
1 0 2 01 10 3 011 100 100 3 011 101 110 4 0001 0001 0001 1110 4 0101 1001 0001 1110 4 0100 1001 0001 0110 4 0101 1011 0101 1110 4 0110 1001 1001 0110 4 0111 1011 1101 1110 5 01000 10111 01000 01000 01000 5 01111 10001 10000 10000 11000 5 01100 10110 11011 01100 00100 5 01111 10110 11010 11100 10000 ...
output:
0 2 16 66 54 116 36 298 128 732 128 202 408 878 80 172 794 1372 56 372 668 190 2370 142 300 300 100 650 1216 432 4100 250 336 566 1072 988 1602 850 2648 446 1434 4438 160 264 524 1030 130 802 258 362 1380 518 1650 2372 3538 5460 488 106 234 892 1542 482 362 790 1326 2186 288 1176 1784 808 5232 7358 ...
result:
ok 143 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
20 01110111111111111111 10111111111011111111 11011111101111101111 11101110111011111111 01110111111011011011 11111011101111011110 11111101111111101111 11101110111111111111 11111111011111111111 11011011101111101111 11111111110111010111 10100111111011111111 11111111111101111110 11111111111110111111 111...
output:
11368772 12823048 16678042 17149212 18099376 18616410 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 19138700 191...
result:
ok 50 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
50 01111111111101010111111110111111111111001110111111 10111111011010111101111111011111111111111111011111 11010101111111111110011110001111111111111111111111 11101111110101111110101111111111111111111101111111 11010111111101101111011111111101111111101111111110 111110111011111111111111111111111111111101...
output:
1250940348 1590514050 1984065786 2169894880 2338139630 2348971408 2399983250 2399983250 2389639440 2389639440 2399983250 2399983250 2399983250 2399983250 2399983250 2399983250 2399983250 2399983250 2399983250 2399983250
result:
ok 20 numbers
Test #5:
score: 0
Accepted
time: 19ms
memory: 12328kb
input:
1000 0110000100111110011111111011111111111111111010111011111111110111111111110111110011101111110111111110110111111111111011111100101111000111011011101111110011111101110110111011100111111101101110101111001011011101011101111101111111111111000110011011010111111111111111111010111011011110010111011111101...
output:
1943182464425962
result:
ok 1 number(s): "1943182464425962"
Test #6:
score: 0
Accepted
time: 15ms
memory: 12304kb
input:
1000 0111101111111111110111111111110011101111111101111011110111111110111011011101111110111111111111111111111111111110111110111110111101110110111111101111111111101101111111011011111111111111011111111111111111111011111111111111111110111111111111101111111101111011111111111111111111111111111000111111111...
output:
4406302098164568
result:
ok 1 number(s): "4406302098164568"
Test #7:
score: 0
Accepted
time: 14ms
memory: 12408kb
input:
1000 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111011111111111111111...
output:
7524709536316820
result:
ok 1 number(s): "7524709536316820"
Test #8:
score: 0
Accepted
time: 10ms
memory: 12408kb
input:
1000 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
8841456311725232
result:
ok 1 number(s): "8841456311725232"
Test #9:
score: 0
Accepted
time: 17ms
memory: 12336kb
input:
1000 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
8930014130020796
result:
ok 1 number(s): "8930014130020796"
Test #10:
score: 0
Accepted
time: 13ms
memory: 12288kb
input:
1000 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
8930204741115000
result:
ok 1 number(s): "8930204741115000"
Test #11:
score: 0
Accepted
time: 9ms
memory: 12340kb
input:
1000 0000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
55816
result:
ok 1 number(s): "55816"
Test #12:
score: 0
Accepted
time: 7ms
memory: 12264kb
input:
1000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0
result:
ok 1 number(s): "0"
Extra Test:
score: 0
Extra Test Passed