結果
| 問題 | No.2507 Yet Another Subgraph Counting |
| ユーザー |
👑  emthrm
|
| 提出日時 | 2023-08-27 17:05:58 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,227 bytes |
| コンパイル時間 | 2,304 ms |
| コンパイル使用メモリ | 121,356 KB |
| 実行使用メモリ | 8,944 KB |
| 最終ジャッジ日時 | 2023-08-27 17:06:14 |
| 合計ジャッジ時間 | 9,076 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
8,888 KB |
| testcase_01 | AC | 2 ms
4,380 KB |
| testcase_02 | AC | 1 ms
4,376 KB |
| testcase_03 | AC | 2 ms
4,376 KB |
| testcase_04 | AC | 2 ms
4,376 KB |
| testcase_05 | AC | 2 ms
4,380 KB |
| testcase_06 | AC | 1 ms
4,380 KB |
| testcase_07 | AC | 2 ms
4,376 KB |
| testcase_08 | AC | 1 ms
4,380 KB |
| testcase_09 | AC | 2 ms
4,376 KB |
| testcase_10 | AC | 2 ms
4,380 KB |
| testcase_11 | AC | 3 ms
4,376 KB |
| testcase_12 | AC | 2 ms
4,376 KB |
| testcase_13 | AC | 2 ms
4,384 KB |
| testcase_14 | AC | 4 ms
4,380 KB |
| testcase_15 | AC | 1 ms
4,380 KB |
| testcase_16 | AC | 2 ms
4,380 KB |
| testcase_17 | AC | 3 ms
4,380 KB |
| testcase_18 | AC | 2 ms
4,376 KB |
| testcase_19 | AC | 2 ms
4,384 KB |
| testcase_20 | AC | 1 ms
4,376 KB |
| testcase_21 | AC | 2 ms
4,380 KB |
| testcase_22 | AC | 2 ms
4,380 KB |
| testcase_23 | AC | 15 ms
4,376 KB |
| testcase_24 | AC | 2 ms
4,384 KB |
| testcase_25 | AC | 3 ms
4,376 KB |
| testcase_26 | AC | 4 ms
4,380 KB |
| testcase_27 | AC | 2 ms
4,376 KB |
| testcase_28 | AC | 2 ms
4,380 KB |
| testcase_29 | AC | 12 ms
5,516 KB |
| testcase_30 | AC | 2 ms
4,380 KB |
| testcase_31 | AC | 2 ms
4,376 KB |
| testcase_32 | AC | 24 ms
5,512 KB |
| testcase_33 | AC | 2 ms
4,376 KB |
| testcase_34 | AC | 2 ms
4,376 KB |
| testcase_35 | AC | 2 ms
4,376 KB |
| testcase_36 | AC | 2 ms
4,376 KB |
| testcase_37 | AC | 2 ms
4,380 KB |
| testcase_38 | AC | 1,111 ms
5,396 KB |
| testcase_39 | TLE | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
ソースコード
#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <concepts>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <utility>
#include <vector>
namespace emthrm {
template <int MaxN, typename T>
std::vector<T> subset_convolution(
const std::vector<T>& f, const std::vector<T>& g) {
using Polynomial = std::array<T, MaxN + 1>;
assert(std::has_single_bit(f.size()) && f.size() == g.size());
const int n = std::countr_zero(f.size());
assert(n <= MaxN);
const int domain_size = 1 << n;
const auto ranked_zeta_transform =
[n, domain_size](const std::vector<T>& f) -> std::vector<Polynomial> {
std::vector a(domain_size, Polynomial{});
for (int i = 0; i < domain_size; ++i) {
a[i][std::popcount(static_cast<unsigned int>(i))] = f[i];
}
for (int bit = 1; bit < domain_size; bit <<= 1) {
for (int i = 0; i < domain_size; ++i) {
if ((i & bit) == 0) {
for (int degree = 0; degree <= n; ++degree) {
a[i | bit][degree] += a[i][degree];
}
}
}
}
return a;
};
std::vector<Polynomial> a = ranked_zeta_transform(f);
const std::vector<Polynomial> b = ranked_zeta_transform(g);
for (int i = 0; i < domain_size; ++i) {
// Hadamard product
for (int degree_of_a = n; degree_of_a >= 0; --degree_of_a) {
const T tmp = std::exchange(a[i][degree_of_a], T{});
for (int degree_of_b = 0; degree_of_a + degree_of_b <= n; ++degree_of_b) {
a[i][degree_of_a + degree_of_b] += tmp * b[i][degree_of_b];
}
}
}
for (int bit = 1; bit < domain_size; bit <<= 1) {
for (int i = 0; i < domain_size; ++i) {
if ((i & bit) == 0) {
for (int degree = 0; degree <= n; ++degree) {
a[i | bit][degree] -= a[i][degree];
}
}
}
}
std::vector<T> c(domain_size);
for (int i = 0; i < domain_size; ++i) {
c[i] = a[i][std::popcount(static_cast<unsigned int>(i))];
}
return c;
}
template <int MaxN, typename T>
std::vector<T> exp_of_set_power_series(const std::vector<T>& f) {
assert(std::has_single_bit(f.size()) && f[0] == 0);
const int n = std::countr_zero(f.size());
assert(n <= MaxN);
std::vector<T> exponential{1};
exponential.reserve(1 << n);
for (int i = 0; i < n; ++i) {
std::ranges::copy(subset_convolution<MaxN>(
exponential,
std::vector(std::next(f.begin(), 1 << i),
std::next(f.begin(), 1 << (i + 1)))),
std::back_inserter(exponential));
}
return exponential;
}
} // namespace emthrm
bool KthBit(const std::unsigned_integral auto bit_field, const int k) {
return std::cmp_equal(bit_field >> k & 1, 1);
}
// <TLE>
// 閉路集合（頂点のみ）を固定し、縮約したグラフで森を数える。
int main() {
constexpr int kMaxN = 13;
int n, m;
std::cin >> n >> m;
assert(2 <= n && n <= kMaxN && 1 <= m && m <= n * (n - 1) / 2);
std::vector<int> u(m), v(m);
for (int i = 0; i < m; ++i) {
std::cin >> u[i] >> v[i];
assert(1 <= u[i] && u[i] < v[i] && v[i] <= n);
--u[i]; --v[i];
}
std::vector<std::vector<int>> graph(n);
for (int i = 0; i < m; ++i) {
graph[u[i]].emplace_back(v[i]);
graph[v[i]].emplace_back(u[i]);
}
std::vector num_of_paths(1 << n, std::vector(n, INT64_C(0)));
for (int start = 0; start < n; ++start) {
num_of_paths[1 << start][start] = 1;
}
for (std::uint32_t bit = 1; bit < (UINT32_C(1) << n); ++bit) {
const int start = std::countr_zero(bit);
for (int current_vertex = start; current_vertex < n; ++current_vertex) {
for (const int next_vertex : graph[current_vertex]) {
if (next_vertex > start && !KthBit(bit, next_vertex)) {
num_of_paths[bit | (1 << next_vertex)][next_vertex] +=
num_of_paths[bit][current_vertex];
}
}
}
}
std::vector<std::int64_t> num_of_cycles(1 << n, 0);
for (int vertex = 0; vertex < n; ++vertex) {
num_of_cycles[1 << vertex] = 1;
}
for (std::uint32_t bit = 7; bit < (UINT32_C(1) << n); ++bit) {
if (std::popcount(bit) < 3) continue;
const int start = std::countr_zero(bit);
for (const int last : graph[start]) {
if (KthBit(bit, last)) num_of_cycles[bit] += num_of_paths[bit][last];
}
num_of_cycles[bit] /= 2;
}
const auto Solve = [n, m, &graph, &num_of_cycles](
auto Solve, const int vertex, std::uint32_t not_decided,
const int num_of_vertices, std::vector<int>* id,
std::vector<std::vector<int>>* new_graph) -> std::int64_t {
if (vertex == n) {
// ref. https://atcoder.jp/contests/abc253/editorial/4028
std::vector<std::uint64_t> num_of_trees{0, 1};
num_of_trees.reserve(1 << num_of_vertices);
for (int i = 1; i < num_of_vertices; ++i) {
std::vector<std::uint64_t> tmp = num_of_trees;
for (std::uint32_t bit_field = 0; bit_field < (1 << i); ++bit_field) {
int degree = 0;
for (int j = 0; j < i; ++j) {
if (KthBit(bit_field, j)) degree += (*new_graph)[i][j];
}
tmp[bit_field] *= degree;
}
std::ranges::copy(emthrm::exp_of_set_power_series<kMaxN>(tmp),
std::back_inserter(num_of_trees));
}
// https://atcoder.jp/contests/abc236/editorial/3910 で高速化できるらしい
return emthrm::exp_of_set_power_series<kMaxN>(num_of_trees).back();
}
if ((*id)[vertex] != -1) {
return Solve(
Solve, vertex + 1, not_decided, num_of_vertices, id, new_graph);
}
not_decided ^= UINT32_C(1) << vertex;
std::int64_t ans = 0;
for (std::uint32_t cycle = not_decided; ;
cycle = (cycle - 1) & not_decided) {
if (num_of_cycles[cycle | (UINT32_C(1) << vertex)] > 0) {
std::vector<int> on_cycle{vertex};
on_cycle.reserve(std::popcount(cycle) + 1);
for (int i = vertex + 1; i < n; ++i) {
if (KthBit(cycle, i)) on_cycle.emplace_back(i);
}
for (const int v : on_cycle) (*id)[v] = num_of_vertices;
for (const int v : on_cycle) {
for (const int adj : graph[v]) {
if ((*id)[adj] != -1 && (*id)[adj] != num_of_vertices) {
++(*new_graph)[(*id)[adj]][num_of_vertices];
++(*new_graph)[num_of_vertices][(*id)[adj]];
}
}
}
ans += num_of_cycles[cycle | (UINT32_C(1) << vertex)]
* Solve(Solve, vertex + 1, not_decided ^ cycle,
num_of_vertices + 1, id, new_graph);
for (const int v : on_cycle) {
for (const int adj : graph[v]) {
if ((*id)[adj] != -1 && (*id)[adj] != num_of_vertices) {
--(*new_graph)[(*id)[adj]][num_of_vertices];
--(*new_graph)[num_of_vertices][(*id)[adj]];
}
}
}
for (const int v : on_cycle) (*id)[v] = -1;
}
if (cycle == 0) break;
}
return ans;
};
std::vector<int> id(n, -1);
std::vector new_graph(n, std::vector(n, 0));
std::cout << Solve(Solve, 0, (UINT32_C(1) << n) - 1, 0, &id, &new_graph)
<< '\n';
return 0;
}