#706914 (C++17) No.1773 Love Triangle

• 問題: No.1773 Love Triangle
• ユーザー: 👑 hitonanode
• 提出日時: 2021-10-12 20:55:40
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 440 ms / 2,000 ms
• コード長: 4,610 bytes
• コンパイル時間: 1,441 ms
• コンパイル使用メモリ: 123,644 KB
• 実行使用メモリ: 4,500 KB
• 最終ジャッジ日時: 2023-09-16 22:03:20
• 合計ジャッジ時間: 26,188 ms
• ジャッジサーバーID （参考情報）: judge13 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,380 KB
testcase_01	AC	2 ms; 4,376 KB
testcase_02	AC	2 ms; 4,376 KB
testcase_03	AC	246 ms; 4,376 KB
testcase_04	AC	3 ms; 4,384 KB
testcase_05	AC	87 ms; 4,380 KB
testcase_06	AC	2 ms; 4,380 KB
testcase_07	AC	7 ms; 4,380 KB
testcase_08	AC	2 ms; 4,376 KB
testcase_09	AC	9 ms; 4,380 KB
testcase_10	AC	3 ms; 4,380 KB
testcase_11	AC	212 ms; 4,376 KB
testcase_12	AC	3 ms; 4,380 KB
testcase_13	AC	2 ms; 4,376 KB
testcase_14	AC	2 ms; 4,376 KB
testcase_15	AC	99 ms; 4,376 KB
testcase_16	AC	2 ms; 4,376 KB
testcase_17	AC	201 ms; 4,380 KB
testcase_18	AC	181 ms; 4,380 KB
testcase_19	AC	6 ms; 4,376 KB
testcase_20	AC	233 ms; 4,380 KB
testcase_21	AC	2 ms; 4,380 KB
testcase_22	AC	318 ms; 4,384 KB
testcase_23	AC	13 ms; 4,380 KB
testcase_24	AC	22 ms; 4,380 KB
testcase_25	AC	34 ms; 4,376 KB
testcase_26	AC	2 ms; 4,376 KB
testcase_27	AC	3 ms; 4,376 KB
testcase_28	AC	121 ms; 4,376 KB
testcase_29	AC	2 ms; 4,376 KB
testcase_30	AC	156 ms; 4,380 KB
testcase_31	AC	26 ms; 4,380 KB
testcase_32	AC	14 ms; 4,376 KB
testcase_33	AC	6 ms; 4,376 KB
testcase_34	AC	117 ms; 4,376 KB
testcase_35	AC	4 ms; 4,376 KB
testcase_36	AC	302 ms; 4,380 KB
testcase_37	AC	2 ms; 4,380 KB
testcase_38	AC	432 ms; 4,376 KB
testcase_39	AC	430 ms; 4,380 KB
testcase_40	AC	436 ms; 4,376 KB
testcase_41	AC	430 ms; 4,376 KB
testcase_42	AC	432 ms; 4,376 KB
testcase_43	AC	432 ms; 4,380 KB
testcase_44	AC	435 ms; 4,376 KB
testcase_45	AC	429 ms; 4,380 KB
testcase_46	AC	434 ms; 4,376 KB
testcase_47	AC	430 ms; 4,380 KB
testcase_48	AC	435 ms; 4,380 KB
testcase_49	AC	435 ms; 4,376 KB
testcase_50	AC	431 ms; 4,380 KB
testcase_51	AC	435 ms; 4,380 KB
testcase_52	AC	433 ms; 4,376 KB
testcase_53	AC	434 ms; 4,380 KB
testcase_54	AC	431 ms; 4,376 KB
testcase_55	AC	434 ms; 4,376 KB
testcase_56	AC	431 ms; 4,376 KB
testcase_57	AC	432 ms; 4,380 KB
testcase_58	AC	434 ms; 4,380 KB
testcase_59	AC	435 ms; 4,380 KB
testcase_60	AC	435 ms; 4,376 KB
testcase_61	AC	434 ms; 4,376 KB
testcase_62	AC	436 ms; 4,376 KB
testcase_63	AC	435 ms; 4,376 KB
testcase_64	AC	436 ms; 4,376 KB
testcase_65	AC	436 ms; 4,380 KB
testcase_66	AC	437 ms; 4,376 KB
testcase_67	AC	435 ms; 4,500 KB
testcase_68	AC	435 ms; 4,376 KB
testcase_69	AC	435 ms; 4,380 KB
testcase_70	AC	437 ms; 4,376 KB
testcase_71	AC	436 ms; 4,380 KB
testcase_72	AC	435 ms; 4,376 KB
testcase_73	AC	435 ms; 4,376 KB
testcase_74	AC	435 ms; 4,376 KB
testcase_75	AC	436 ms; 4,376 KB
testcase_76	AC	435 ms; 4,376 KB
testcase_77	AC	436 ms; 4,380 KB
testcase_78	AC	1 ms; 4,376 KB
testcase_79	AC	6 ms; 4,380 KB
testcase_80	AC	131 ms; 4,380 KB
testcase_81	AC	436 ms; 4,376 KB
testcase_82	AC	440 ms; 4,376 KB
testcase_83	AC	121 ms; 4,376 KB
testcase_84	AC	131 ms; 4,376 KB
testcase_85	AC	144 ms; 4,376 KB
testcase_86	AC	37 ms; 4,376 KB
testcase_87	AC	78 ms; 4,376 KB
testcase_88	AC	19 ms; 4,376 KB
testcase_89	AC	63 ms; 4,380 KB
testcase_90	AC	268 ms; 4,376 KB
testcase_91	AC	184 ms; 4,376 KB
testcase_92	AC	26 ms; 4,376 KB

ソースコード

#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <tuple>
#include <vector>
using namespace std;

mt19937 mt(530629);

// Berlekamp–Massey algorithm
// https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm
// Complexity: O(N^2)
// input: S = sequence from field K
// return: L          = degree of minimal polynomial,
//         C_reversed = monic min. polynomial (size = L + 1, reversed order, C_reversed[0] = 1))
// Formula: convolve(S, C_reversed)[i] = 0 for i >= L
// Example:
// - [1, 2, 4, 8, 16]   -> (1, [1, -2])
// - [1, 1, 2, 3, 5, 8] -> (2, [1, -1, -1])
// - [0, 0, 0, 0, 1]    -> (5, [1, 0, 0, 0, 0, 998244352]) (mod 998244353)
// - []                 -> (0, [1])
// - [0, 0, 0]          -> (0, [1])
// - [-2]               -> (1, [1, 2])
template <typename Tfield> std::pair<int, std::vector<Tfield>> find_linear_recurrence(const std::vector<Tfield> &S) {
    int N = S.size();
    using poly = std::vector<Tfield>;
    poly C_reversed{1}, B{1};
    int L = 0, m = 1;
    Tfield b = 1;

    // adjust: C(x) <- C(x) - (d / b) x^m B(x)
    auto adjust = [](poly C, const poly &B, Tfield d, Tfield b, int m) -> poly {
        C.resize(std::max(C.size(), B.size() + m));
        Tfield a = d / b;
        for (unsigned i = 0; i < B.size(); i++) C[i + m] -= a * B[i];
        return C;
    };

    for (int n = 0; n < N; n++) {
        Tfield d = S[n];
        for (int i = 1; i <= L; i++) d += C_reversed[i] * S[n - i];

        if (d == 0)
            m++;
        else if (2 * L <= n) {
            poly T = C_reversed;
            C_reversed = adjust(C_reversed, B, d, b, m);
            L = n + 1 - L;
            B = T;
            b = d;
            m = 1;
        } else
            C_reversed = adjust(C_reversed, B, d, b, m++);
    }
    return std::make_pair(L, C_reversed);
}


template <typename ModInt> std::vector<ModInt> gen_random_vector(int len) {
    static std::uniform_int_distribution<int> rnd(1, ModInt::mod() - 1);
    std::vector<ModInt> ret(len);
    for (auto &x : ret) x = rnd(mt);
    return ret;
};

// Sparse matrix
template <typename Tp> struct sparse_matrix {
    int H, W;
    std::vector<std::vector<std::pair<int, Tp>>> vals;
    sparse_matrix(int H = 0, int W = 0) : H(H), W(W), vals(H) {}
    int height() const { return H; }
    int width() const { return W; }
    void add_element(int i, int j, Tp val) {
        assert(i >= 0 and i < H);
        assert(j >= 0 and i < W);
        vals[i].emplace_back(j, val);
    }
    std::vector<Tp> prod(const std::vector<Tp> &vec) const {
        assert(W == int(vec.size()));
        std::vector<Tp> ret(H);
        for (int i = 0; i < H; i++) {
            for (const auto &p : vals[i]) ret[i] += p.second * vec[p.first];
        }
        return ret;
    }
};

template <class Matrix, class Tp> int blackbox_rank(const Matrix &M) {
    assert(M.height() == M.width());
    const int N = M.height();
    std::vector<Tp> b = gen_random_vector<Tp>(N), u = gen_random_vector<Tp>(N), D = gen_random_vector<Tp>(N);
    std::vector<Tp> uMDib(2 * N);
    for (int i = 0; i < 2 * N; i++) {
        uMDib[i] = std::inner_product(u.begin(), u.end(), b.begin(), Tp(0));
        for (int j = 0; j < N; j++) b[j] *= D[j];
        b = M.prod(b);
    }
    return find_linear_recurrence<Tp>(uMDib).first - 1;
}


#include <atcoder/modint>
using mint = atcoder::modint1000000007;


uniform_int_distribution<int> rndgen(0, mint::mod());

int solve(int r, const vector<tuple<int, int, int>> &uvws) {
    const int m = uvws.size();
    // Geelen & Iwata (2005)
    sparse_matrix<mint> mat(r + m * 2, r + m * 2);
    for (int i = 0; i < m; ++i) {
        auto [u, v, w] = uvws[i];
        mat.add_element(u, r + i * 2, +1);
        mat.add_element(w, r + i * 2, -1);
        mat.add_element(v, r + i * 2 + 1, +1);
        mat.add_element(w, r + i * 2 + 1, -1);

        mat.add_element(r + i * 2, u, +1);
        mat.add_element(r + i * 2, w, -1);
        mat.add_element(r + i * 2 + 1, v, +1);
        mat.add_element(r + i * 2 + 1, w, -1);
    }
    for (int i = 0; i < m; ++i) {
        int x = rndgen(mt);
        mat.add_element(r + i * 2, r + i * 2 + 1, x);
        mat.add_element(r + i * 2 + 1, r + i * 2, -x);
    }
    int rank = blackbox_rank<sparse_matrix<mint>, mint>(mat);
    return rank / 2 - m;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<tuple<int, int, int>> uvws;
    while (M--) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--, w--;
        uvws.emplace_back(u, v, w);
    }
    cout << max(solve(N, uvws), solve(N, uvws)) << '\n';
}