結果

問題 No.1774 Love Triangle (Hard)
ユーザー 👑 hitonanodehitonanode
提出日時 2021-10-12 21:47:45
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 7,743 ms / 8,000 ms
コード長 5,184 bytes
コンパイル時間 5,094 ms
コンパイル使用メモリ 138,352 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-17 11:04:08
合計ジャッジ時間 450,722 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 3 ms
4,348 KB
testcase_03 AC 46 ms
4,348 KB
testcase_04 AC 3 ms
4,348 KB
testcase_05 AC 13 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 123 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 1 ms
4,348 KB
testcase_10 AC 1 ms
4,348 KB
testcase_11 AC 72 ms
4,348 KB
testcase_12 AC 2,404 ms
4,348 KB
testcase_13 AC 588 ms
4,348 KB
testcase_14 AC 175 ms
4,348 KB
testcase_15 AC 623 ms
4,348 KB
testcase_16 AC 925 ms
4,348 KB
testcase_17 AC 4 ms
4,348 KB
testcase_18 AC 648 ms
4,348 KB
testcase_19 AC 6 ms
4,348 KB
testcase_20 AC 51 ms
4,348 KB
testcase_21 AC 30 ms
4,348 KB
testcase_22 AC 6,020 ms
4,348 KB
testcase_23 AC 6,029 ms
4,348 KB
testcase_24 AC 6,126 ms
4,348 KB
testcase_25 AC 6,001 ms
4,348 KB
testcase_26 AC 6,075 ms
4,348 KB
testcase_27 AC 6,112 ms
4,348 KB
testcase_28 AC 6,089 ms
4,348 KB
testcase_29 AC 6,237 ms
4,348 KB
testcase_30 AC 6,108 ms
4,348 KB
testcase_31 AC 6,094 ms
4,348 KB
testcase_32 AC 6,062 ms
4,348 KB
testcase_33 AC 6,110 ms
4,348 KB
testcase_34 AC 6,163 ms
4,348 KB
testcase_35 AC 6,095 ms
4,348 KB
testcase_36 AC 5,987 ms
4,348 KB
testcase_37 AC 6,184 ms
4,348 KB
testcase_38 AC 5,983 ms
4,348 KB
testcase_39 AC 6,082 ms
4,348 KB
testcase_40 AC 6,061 ms
4,348 KB
testcase_41 AC 6,166 ms
4,348 KB
testcase_42 AC 6,239 ms
4,348 KB
testcase_43 AC 6,212 ms
4,348 KB
testcase_44 AC 6,208 ms
4,348 KB
testcase_45 AC 6,178 ms
4,348 KB
testcase_46 AC 6,180 ms
4,348 KB
testcase_47 AC 6,112 ms
4,348 KB
testcase_48 AC 6,172 ms
4,348 KB
testcase_49 AC 6,189 ms
4,348 KB
testcase_50 AC 6,198 ms
4,348 KB
testcase_51 AC 6,352 ms
4,348 KB
testcase_52 AC 7,743 ms
4,348 KB
testcase_53 AC 6,234 ms
4,348 KB
testcase_54 AC 6,229 ms
4,348 KB
testcase_55 AC 6,101 ms
4,348 KB
testcase_56 AC 6,194 ms
4,348 KB
testcase_57 AC 6,210 ms
4,348 KB
testcase_58 AC 6,164 ms
4,348 KB
testcase_59 AC 6,222 ms
4,348 KB
testcase_60 AC 6,200 ms
4,348 KB
testcase_61 AC 6,191 ms
4,348 KB
testcase_62 AC 6,482 ms
4,348 KB
testcase_63 AC 6,422 ms
4,348 KB
testcase_64 AC 6,263 ms
4,348 KB
testcase_65 AC 6,356 ms
4,348 KB
testcase_66 AC 6,395 ms
4,348 KB
testcase_67 AC 6,209 ms
4,348 KB
testcase_68 AC 6,392 ms
4,348 KB
testcase_69 AC 6,436 ms
4,348 KB
testcase_70 AC 6,213 ms
4,348 KB
testcase_71 AC 6,462 ms
4,348 KB
testcase_72 AC 6,379 ms
4,348 KB
testcase_73 AC 6,369 ms
4,348 KB
testcase_74 AC 6,420 ms
4,348 KB
testcase_75 AC 6,415 ms
4,348 KB
testcase_76 AC 6,283 ms
4,348 KB
testcase_77 AC 6,446 ms
4,348 KB
testcase_78 AC 6,382 ms
4,348 KB
testcase_79 AC 6,161 ms
4,348 KB
testcase_80 AC 6,404 ms
4,348 KB
testcase_81 AC 6,435 ms
4,348 KB
testcase_82 AC 5,945 ms
4,348 KB
testcase_83 AC 5,971 ms
4,348 KB
testcase_84 AC 5,955 ms
4,348 KB
testcase_85 AC 5,916 ms
4,348 KB
testcase_86 AC 6,012 ms
4,348 KB
testcase_87 AC 5,746 ms
4,348 KB
testcase_88 AC 5,639 ms
4,348 KB
testcase_89 AC 5,656 ms
4,348 KB
testcase_90 AC 5,167 ms
4,348 KB
testcase_91 AC 4,888 ms
4,348 KB
testcase_92 AC 5,109 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

mt19937 mt(1967176539);

// 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::static_modint<(1 << 30) + 3>;


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

vector<int> solve(int r, const vector<tuple<int, int, int>> &uvws) {
    const int m = uvws.size();
    vector<int> ret(m);
    ret[0] = 1;
    {
        sparse_matrix<mint> mat(r, r);
        for (int i = 0; i < m; ++i) {
            auto [u, v, w] = uvws[i];
            mint x = rndgen(mt);
            mat.add_element(u, v, x);
            mat.add_element(v, w, x);
            mat.add_element(w, u, x);

            mat.add_element(v, u, -x);
            mat.add_element(w, v, -x);
            mat.add_element(u, w, -x);
            if (ret[i] or ret[i - 1]) continue;
            int rank = blackbox_rank<sparse_matrix<mint>, mint>(mat);
            ret[i] = rank / 2;
        }
    }
    {
        sparse_matrix<mint> mat(r, r);
        for (int i = 0; i < m; ++i) {
            auto [u, v, w] = uvws[i];
            mint x = rndgen(mt);
            mat.add_element(u, v, x);
            mat.add_element(v, w, x);
            mat.add_element(w, u, x);

            mat.add_element(v, u, -x);
            mat.add_element(w, v, -x);
            mat.add_element(u, w, -x);
            if (ret[i]) continue;
            if (ret[i - 1] + 2 == ret[i + 1]) ret[i] = ret[i - 1] + 1;
            if (ret[i - 1] == ret[i + 1]) ret[i] = ret[i - 1];
            if (ret[i]) continue;
            int rank = blackbox_rank<sparse_matrix<mint>, mint>(mat);
            ret[i] = rank / 2;
        }
    }
    return ret;
}

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);
    }
    auto ret = solve(N, uvws);
    for (auto x : ret) cout << x << '\n';
}
0