結果
| 問題 | No.1502 Many Simple Additions |
| ユーザー |
 KoD
|
| 提出日時 | 2021-05-07 21:41:35 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 115 ms / 2,000 ms |
| コード長 | 7,956 bytes |
| コンパイル時間 | 2,210 ms |
| コンパイル使用メモリ | 211,212 KB |
| 最終ジャッジ日時 | 2025-01-21 08:04:59 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 39 |
ソースコード
#include <bits/stdc++.h>using i32 = std::int32_t;using u32 = std::uint32_t;using i64 = std::int64_t;using u64 = std::uint64_t;using i128 = __int128_t;using u128 = __uint128_t;using isize = std::ptrdiff_t;using usize = std::size_t;class rep {struct Iter {usize itr;constexpr Iter(const usize pos) noexcept : itr(pos) {}constexpr void operator++() noexcept { ++itr; }constexpr bool operator!=(const Iter& other) const noexcept {return itr != other.itr;}constexpr usize operator*() const noexcept { return itr; }};const Iter first, last;public:explicit constexpr rep(const usize first, const usize last) noexcept: first(first), last(std::max(first, last)) {}constexpr Iter begin() const noexcept { return first; }constexpr Iter end() const noexcept { return last; }};template <class F> struct RecLambda : private F {template <class G>explicit constexpr RecLambda(G&& g) : F(std::forward<G>(g)) {}template <class... Args>constexpr decltype(auto) operator()(Args&&... args) const {return F::operator()(*this, std::forward<Args>(args)...);}};template <class G> explicit RecLambda(G&&) -> RecLambda<std::decay_t<G>>;template <class T> bool setmin(T& lhs, const T& rhs) {if (lhs > rhs) {lhs = rhs;return true;}return false;}template <class T> bool setmax(T& lhs, const T& rhs) {if (lhs < rhs) {lhs = rhs;return true;}return false;}template <class T> constexpr T totient(T x) {T ret = x;for (T i = 2; i * i <= x; ++i) {if (x % i == 0) {ret /= i;ret *= i - 1;while (x % i == 0) x /= i;}}if (x > 1) {ret /= x;ret *= x - 1;}return ret;}template <class T> constexpr T rem_euclid(T value, const T& mod) {return (value %= mod) >= 0 ? value : value + mod;}template <u32 MOD,std::enable_if_t<((u32)1 <= MOD and MOD <= ((u32)1 << 31))>* =nullptr>class StaticModint {using Mint = StaticModint;static inline constexpr u32 PHI = totient(MOD);u32 v;public:static constexpr u32 mod() noexcept { return MOD; }template <class T,std::enable_if_t<std::is_signed_v<T> and std::is_integral_v<T>>* =nullptr>static constexpr T normalize(const T x) noexcept {return rem_euclid<std::common_type_t<T, i64>>(x, MOD);}template <class T,std::enable_if_t<std::is_unsigned_v<T> andstd::is_integral_v<T>>* = nullptr>static constexpr T normalize(const T x) noexcept {return x % MOD;}constexpr StaticModint() noexcept : v(0) {}template <class T>constexpr StaticModint(const T x) noexcept : v(normalize(x)) {}template <class T> static constexpr Mint raw(const T x) noexcept {Mint ret;ret.v = x;return ret;}constexpr u32 get() const noexcept { return v; }constexpr Mint neg() const noexcept { return raw(v == 0 ? 0 : MOD - v); }constexpr Mint inv() const noexcept { return pow(PHI - 1); }constexpr Mint pow(u64 exp) const noexcept {Mint ret(1), mult(*this);for (; exp > 0; exp >>= 1) {if (exp & 1) ret *= mult;mult *= mult;}return ret;}constexpr Mint operator-() const noexcept { return neg(); }constexpr Mint operator~() const noexcept { return inv(); }constexpr Mint operator+(const Mint& rhs) const noexcept {return Mint(*this) += rhs;}constexpr Mint& operator+=(const Mint& rhs) noexcept {if ((v += rhs.v) >= MOD) v -= MOD;return *this;}constexpr Mint operator-(const Mint& rhs) const noexcept {return Mint(*this) -= rhs;}constexpr Mint& operator-=(const Mint& rhs) noexcept {if (v < rhs.v) v += MOD;v -= rhs.v;return *this;}constexpr Mint operator*(const Mint& rhs) const noexcept {return Mint(*this) *= rhs;}constexpr Mint& operator*=(const Mint& rhs) noexcept {v = (u64)v * rhs.v % MOD;return *this;}constexpr Mint operator/(const Mint& rhs) const noexcept {return Mint(*this) /= rhs;}constexpr Mint& operator/=(const Mint& rhs) noexcept {return *this *= rhs.inv();}constexpr bool operator==(const Mint& rhs) const noexcept {return v == rhs.v;}constexpr bool operator!=(const Mint& rhs) const noexcept {return v != rhs.v;}friend std::ostream& operator<<(std::ostream& stream, const Mint& rhs) {return stream << rhs.v;}};using Modint1000000007 = StaticModint<1000000007>;using Modint998244353 = StaticModint<998244353>;template <class T> using Vec = std::vector<T>;using Fp = Modint1000000007;void D_main() {usize N, M;i64 K;std::cin >> N >> M >> K;Vec<Vec<std::pair<usize, i64>>> graph(N);for (const auto i : rep(0, M)) {usize x, y;i64 z;std::cin >> x >> y >> z;x -= 1;y -= 1;graph[x].emplace_back(y, z);graph[y].emplace_back(x, z);}const auto solve = [&](const i64 Max) {Vec<i64> A(N), B(N); // A[i] * x + B[i]Vec<usize> seen;Vec<std::tuple<usize, usize, i64>> edge;seen.reserve(N);edge.reserve(M);const auto dfs = RecLambda([&](auto&& dfs, const usize u) -> void {seen.push_back(u);for (const auto [v, s] : graph[u]) {edge.emplace_back(u, v, s);if (A[v] == 0) {A[v] = -A[u];B[v] = s - B[u];dfs(v);}}});Fp ret = 1;for (const auto src : rep(0, N)) {if (A[src] != 0) {continue;}A[src] = 1;dfs(src);ret *= [&] {std::optional<i64> val;for (const auto [u, v, s] : edge) {if (A[u] == A[v]) {if ((s - B[u] - B[v]) % 2 != 0) {return Fp(0);}val = (s - B[u] - B[v]) / (A[u] + A[v]);} else {if (B[u] + B[v] != s) {return Fp(0);}}}if (val) {const auto x = val.value();for (const auto u : seen) {const auto y = A[u] * x + B[u];if (!(1 <= y and y <= Max)) {return Fp(0);}}for (const auto [u, v, s] : edge) {if (A[u] * x + B[u] + A[v] * x + B[v] != s) {return Fp(0);}}return Fp(1);}i64 low = 1, high = Max;for (const auto u : seen) {if (A[u] == 1) {setmin(high, Max - B[u]);setmax(low, 1 - B[u]);} else {setmin(high, -(1 - B[u]));setmax(low, -(Max - B[u]));}}return Fp(std::max<i64>(high - low + 1, 0));}();seen.clear();edge.clear();}return ret;};std::cout << solve(K) - solve(K - 1) << '\n';}int main() {std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr);D_main();return 0;}