This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://atcoder.jp/contests/abc213/tasks/abc213_h" #include <iostream> #include <tuple> #include <atcoder/modint> #include <atcoder/convolution> using mint = atcoder::modint998244353; std::istream& operator>>(std::istream& in, mint &a) { long long e; in >> e; a = e; return in; } std::ostream& operator<<(std::ostream& out, const mint &a) { out << a.val(); return out; } #include "library/convolution/semi_relaxed_convolution.hpp" using suisen::SemiRelaxedConvolution; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, t; std::cin >> n >> m >> t; std::vector<std::vector<std::pair<int, SemiRelaxedConvolution<mint>>>> p(n); for (int i = 0; i < m; ++i) { int u, v; std::cin >> u >> v; --u, --v; std::vector<mint> l(t); for (auto &e : l) std::cin >> e; SemiRelaxedConvolution<mint> conv { l, [](const auto &a, const auto &b) { return atcoder::convolution(a, b); } }; p[u].emplace_back(v, conv); p[v].emplace_back(u, conv); } std::vector<std::vector<mint>> f(n, std::vector<mint>(t + 1, 0)); f[0][0] = 1; for (int i = 0; i < t; ++i) { for (int u = 0; u < n; ++u) for (auto &[v, conv] : p[u]) { f[u][i + 1] += conv.append(f[v][i]); } } std::cout << f[0][t].val() << std::endl; return 0; }
#line 1 "test/src/convolution/semi_relaxed_convolution/abc213_h.test.cpp" #define PROBLEM "https://atcoder.jp/contests/abc213/tasks/abc213_h" #include <iostream> #include <tuple> #include <atcoder/modint> #include <atcoder/convolution> using mint = atcoder::modint998244353; std::istream& operator>>(std::istream& in, mint &a) { long long e; in >> e; a = e; return in; } std::ostream& operator<<(std::ostream& out, const mint &a) { out << a.val(); return out; } #line 1 "library/convolution/semi_relaxed_convolution.hpp" #include <vector> namespace suisen { // reference: https://qiita.com/Kiri8128/items/1738d5403764a0e26b4c template <typename T> struct SemiRelaxedConvolution { using value_type = T; using polynomial_type = std::vector<value_type>; using convolution_type = polynomial_type(*)(const polynomial_type&, const polynomial_type&); SemiRelaxedConvolution() = default; SemiRelaxedConvolution(const polynomial_type &f) : _n(0), _f(f) {} SemiRelaxedConvolution(const polynomial_type &f, const convolution_type &convolve) : _convolve(convolve), _n(0), _f(f), _g{}, _h{} {} void set_convolve_function(const convolution_type &convolve) { _convolve = convolve; } value_type append(const value_type &gi) { ++_n; _g.push_back(gi); for (int p = 1;; p <<= 1) { int l1 = p - 1, r1 = l1 + p, l2 = _n - p, r2 = _n; add(l1 + l2, range_convolve(l1, r1, l2, r2)); if (p == (-_n & _n)) break; } return _h[_n - 1]; } const value_type& operator[](int i) const { return _h[i]; } polynomial_type get() const { return _h; } private: convolution_type _convolve = [](const polynomial_type&, const polynomial_type&) -> polynomial_type { assert(false); }; int _n; polynomial_type _f, _g, _h; polynomial_type range_convolve(int l1, int r1, int l2, int r2) { r1 = std::min(r1, int(_f.size())), l1 = std::min(l1, r1); return _convolve(polynomial_type(_f.begin() + l1, _f.begin() + r1), polynomial_type(_g.begin() + l2, _g.begin() + r2)); } void add(std::size_t bias, const polynomial_type &h) { if (_h.size() < bias + h.size()) _h.resize(bias + h.size()); for (std::size_t i = 0; i < h.size(); ++i) _h[bias + i] += h[i]; } }; } // namespace suisen #line 22 "test/src/convolution/semi_relaxed_convolution/abc213_h.test.cpp" using suisen::SemiRelaxedConvolution; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, t; std::cin >> n >> m >> t; std::vector<std::vector<std::pair<int, SemiRelaxedConvolution<mint>>>> p(n); for (int i = 0; i < m; ++i) { int u, v; std::cin >> u >> v; --u, --v; std::vector<mint> l(t); for (auto &e : l) std::cin >> e; SemiRelaxedConvolution<mint> conv { l, [](const auto &a, const auto &b) { return atcoder::convolution(a, b); } }; p[u].emplace_back(v, conv); p[v].emplace_back(u, conv); } std::vector<std::vector<mint>> f(n, std::vector<mint>(t + 1, 0)); f[0][0] = 1; for (int i = 0; i < t; ++i) { for (int u = 0; u < n; ++u) for (auto &[v, conv] : p[u]) { f[u][i + 1] += conv.append(f[v][i]); } } std::cout << f[0][t].val() << std::endl; return 0; }