工具

代码基本框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long LL;

void get_char_array(char *s){
    static char st[N];
    cin >> st;
    memcpy(s + 1, st, sizeof(char) * (strlen(st) + 1));
}

int main(){
    // cin.sync_with_stdio(false);
    // cin.tie(0);
    
    return 0;
}

makefile

Windows：

1
2
%: %.cpp
	g++ $< -o $@ -Wextra -Wall -g -Wl,--stack=100000000000 -Wconversion -Wshadow

Linux：

1
2
%: %.cpp
	g++ $< -o $@ -Wextra -Wall -g -Wl,--stack=100000000000 -Wconversion -Wshadow -fsanitize=address -fsanitize=undefined

编译优化

1
2
3
//fast = O3 + ffast‐math + fallow‐store‐data‐races
#pragma GCC optimize("Ofast")
#pragma GCC target("sse2,abm,fma,mmx,avx2,tune=native")

modint

取自后面博客的 tourist 的板子：https://www.cnblogs.com/Cattle-Horse/p/16637943.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
//注：使用这个需要把原来的 debug 注释掉
template <typename T>
T inv(const T& x, const T& y) {
    assert(x != 0);
    T u = 0, v = 1, a = x, m = y, t;
    while (a != 0) {
        t = m / a;
        swap(a, m -= t * a);
        swap(u -= t * v, v);
    }
    assert(m == 1);
    return u;
}

template <typename T>
class Modular {
public:
    using Type = typename decay<decltype(T::value)>::type;

    constexpr Modular() : value() {}
    template <typename U> Modular(const U& x) { value = normalize(x); }

    template <typename U>
    static Type normalize(const U& x) {
        Type v = static_cast<Type>((-mod() <= x && x < mod()) ? x : x % mod());
        if (v < 0) v += mod();
        return v;
    }

    const Type& operator()() const { return value; }
    template <typename U> explicit operator U() const { return static_cast<U>(value); }
    constexpr static Type mod() { return T::value; }

    Modular& operator+=(const Modular& other) {
        if ((value += other.value) >= mod()) value -= mod();
        return *this;
    }
    Modular& operator-=(const Modular& other) {
        if ((value -= other.value) < 0) value += mod();
        return *this;
    }
    template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
    template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
    Modular& operator++() { return *this += 1; }
    Modular& operator--() { return *this -= 1; }
    Modular operator++(int) {
        Modular result(*this);
        *this += 1;
        return result;
    }
    Modular operator--(int) {
        Modular result(*this);
        *this -= 1;
        return result;
    }
    Modular operator-() const { return Modular(-value); }

    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
        uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
        uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
        asm(
            "divl %4; \n\t"
            : "=a"(d), "=d"(m)
            : "d"(xh), "a"(xl), "r"(mod()));
        value = m;
#else
        value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
        return *this;
    }
    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type& operator*=(const Modular& rhs) {
        long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
        value = normalize(value * rhs.value - q * mod());
        return *this;
    }
    template <typename U = T>
    typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
        value = normalize(value * rhs.value);
        return *this;
    }

    Modular& operator/=(const Modular& other) { return *this *= Modular(inv(other.value, mod())); }

    friend const Type& abs(const Modular& x) { return x.value; }
    template <typename U> friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
    template <typename U> friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
    template <typename V, typename U> friend V& operator>>(V& stream, Modular<U>& number);

private:
    Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template <typename T, typename U>
Modular<T> qpow(const Modular<T>& a, const U& b) {
    assert(b >= 0);
    Modular<T> x = a, res = 1;
    for (T p = b; p; x *= x, p >>= 1)
        if (p & 1) res *= x;
    return res;
}

template <typename T> bool IsZero(const Modular<T>& number) { return number() == 0; }
template <typename T> string to_string(const Modular<T>& number) { return to_string(number()); }

// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T> U& operator<<(U& stream, const Modular<T>& number) { return stream << number(); }

// U == std::istream? but done this way because of fastinput
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
    typename common_type<typename Modular<T>::Type, long long>::type x;
    stream >> x;
    number.value = Modular<T>::normalize(x);
    return stream;
}

// using ModType = int;
// struct VarMod { static ModType value; };
// ModType VarMod::value;
// ModType& mod = VarMod::value;// for mod can change
// using Mint = Modular<VarMod>;

constexpr int mod = (int)1e9 + 7; 
using Mint = Modular<std::integral_constant<decay<decltype(mod)>::type, mod>>;

struct Fact {
    vector<Mint> fact, factinv;
    const int n;
    Fact(const int& _n) : n(_n), fact(_n + 1, Mint(1)), factinv(_n + 1) {
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        factinv[n] = inv(fact[n](), mod);
        for (int i = n; i; --i) factinv[i - 1] = factinv[i] * i;
    }
    Mint C(const int& n, const int& k) {
        if (n < 0 || k < 0 || n < k) return 0;
        return fact[n] * factinv[k] * factinv[n - k];
    }
    Mint A(const int& n, const int& k) {
        if (n < 0 || k < 0 || n < k) return 0;
        return fact[n] * factinv[n - k];
    }
};

调试 STL

我目前知道两种方法：

  1. 使用 libstdc++ 的 debug code ，在 https://gcc.gnu.org/onlinedocs/libstdc++/manual/debug_mode_using.html 中有详细介绍，大概意思是会将所用到的容易用能调试的容器替换，然后会在过程中自动检测各种合法性之类的，代价就是会变慢，甚至容器操作的复杂度会变劣。
  2. 写一个函数库，定义各种容器的输出，方便每次直接调用函数输出容器内容。

libstdc++

参考链接：

  1. https://ai2615.fstqwq.pw/debug/runtime/
  2. https://gcc.gnu.org/onlinedocs/libstdc++/manual/debug_mode_using.html
  3. https://gcc.gnu.org/onlinedocs/libstdc++/manual/debug_mode_semantics.html

使用方式：编译时加上 -D_GLIBCXX_DEBUG 。

函数库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#ifndef DEBUG_TEMPLATE_CPP
#define DEBUG_TEMPLATE_CPP
// #define cerr cout
namespace __DEBUG_UTIL__ {
    using namespace std;
    /* Primitive Datatypes Print */
    void print(const char *x) { cerr << x; }
    void print(bool x) { cerr << (x ? "T" : "F"); }
    void print(char x) { cerr << '\'' << x << '\''; }
    void print(signed short int x) { cerr << x; }
    void print(unsigned short int x) { cerr << x; }
    void print(signed int x) { cerr << x; }
    void print(unsigned int x) { cerr << x; }
    void print(signed long int x) { cerr << x; }
    void print(unsigned long int x) { cerr << x; }
    void print(signed long long int x) { cerr << x; }
    void print(unsigned long long int x) { cerr << x; }
    void print(float x) { cerr << x; }
    void print(double x) { cerr << x; }
    void print(long double x) { cerr << x; }
    void print(string x) { cerr << '\"' << x << '\"'; }
    template <size_t N>
    void print(bitset<N> x) { cerr << x; }
    void print(vector<bool> v)
    { /* Overloaded this because stl optimizes vector<bool> by using
          _Bit_reference instead of bool to conserve space. */
        int f = 0;
        cerr << '{';
        for (auto &&i : v)
            cerr << (f++ ? "," : "") << (i ? "T" : "F");
        cerr << "}";
    }
    /* Templates Declarations to support nested datatypes */
    template <typename T>
    void print(T &&x);
    template <typename T>
    void print(vector<vector<T>> mat);
    template <typename T, size_t N, size_t M>
    void print(T (&mat)[N][M]);
    template <typename F, typename S>
    void print(pair<F, S> x);
    template <typename T, size_t N>
    struct Tuple;
    template <typename T>
    struct Tuple<T, 1>;
    template <typename... Args>
    void print(tuple<Args...> t);
    template <typename... T>
    void print(priority_queue<T...> pq);
    template <typename T>
    void print(stack<T> st);
    template <typename T>
    void print(queue<T> q);
    /* Template Datatypes Definitions */
    template <typename T>
    void print(T &&x)
    {
        /*  This works for every container that supports range-based loop
            i.e. vector, set, map, oset, omap, dequeue */
        int f = 0;
        cerr << '{';
        for (auto &&i : x)
            cerr << (f++ ? "," : ""), print(i);
        cerr << "}";
    }
    template <typename T>
    void print(vector<vector<T>> mat)
    {
        int f = 0;
        cerr << "\n~~~~~\n";
        for (auto &&i : mat)
        {
            cerr << setw(2) << left << f++, print(i), cerr << "\n";
        }
        cerr << "~~~~~\n";
    }
    template <typename T, size_t N, size_t M>
    void print(T (&mat)[N][M])
    {
        int f = 0;
        cerr << "\n~~~~~\n";
        for (auto &&i : mat)
        {
            cerr << setw(2) << left << f++, print(i), cerr << "\n";
        }
        cerr << "~~~~~\n";
    }
    template <typename F, typename S>
    void print(pair<F, S> x)
    {
        cerr << '(';
        print(x.first);
        cerr << ',';
        print(x.second);
        cerr << ')';
    }
    template <typename T, size_t N>
    struct Tuple
    {
        static void printTuple(T t)
        {
            Tuple<T, N - 1>::printTuple(t);
            cerr << ",", print(get<N - 1>(t));
        }
    };
    template <typename T>
    struct Tuple<T, 1>
    {
        static void printTuple(T t) { print(get<0>(t)); }
    };
    template <typename... Args>
    void print(tuple<Args...> t)
    {
        cerr << "(";
        Tuple<decltype(t), sizeof...(Args)>::printTuple(t);
        cerr << ")";
    }
    template <typename... T>
    void print(priority_queue<T...> pq)
    {
        int f = 0;
        cerr << '{';
        while (!pq.empty())
            cerr << (f++ ? "," : ""), print(pq.top()), pq.pop();
        cerr << "}";
    }
    template <typename T>
    void print(stack<T> st)
    {
        int f = 0;
        cerr << '{';
        while (!st.empty())
            cerr << (f++ ? "," : ""), print(st.top()), st.pop();
        cerr << "}";
    }
    template <typename T>
    void print(queue<T> q)
    {
        int f = 0;
        cerr << '{';
        while (!q.empty())
            cerr << (f++ ? "," : ""), print(q.front()), q.pop();
        cerr << "}";
    }
    /* Printer functions */
    void printer(const char *) {} /* Base Recursive */
    template <typename T, typename... V>
    void printer(const char *names, T &&head, V &&...tail)
    {
        /* Using && to capture both lvalues and rvalues */
        int i = 0;
        for (size_t bracket = 0; names[i] != '\0' and (names[i] != ',' or bracket != 0); i++)
            if (names[i] == '(' or names[i] == '<' or names[i] == '{')
                bracket++;
            else if (names[i] == ')' or names[i] == '>' or names[i] == '}')
                bracket--;
        cerr.write(names, i) << " = ";
        print(head);
        if (sizeof...(tail))
            cerr << " ||", printer(names + i + 1, tail...);
        else
            cerr << "]\n";
    }
    /* PrinterArr */
    void printerArr(const char *) {} /* Base Recursive */
    template <typename T, typename... V>
    void printerArr(const char *names, T arr[], size_t N, V... tail)
    {
        size_t ind = 0;
        for (; names[ind] and names[ind] != ','; ind++)
            cerr << names[ind];
        for (ind++; names[ind] and names[ind] != ','; ind++)
            ;
        cerr << " = {";
        for (size_t i = 0; i < N; i++)
            cerr << (i ? "," : ""), print(arr[i]);
        cerr << "}";
        if (sizeof...(tail))
            cerr << " ||", printerArr(names + ind + 1, tail...);
        else
            cerr << "]\n";
    }
}

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << __LINE__ << ": [", __DEBUG_UTIL__::printer(#__VA_ARGS__, __VA_ARGS__)
#define debugArr(...) std::cerr << __LINE__ << ": [", __DEBUG_UTIL__::printerArr(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...)
#define debugArr(...)
#endif

#endif
using namespace __DEBUG_UTIL__;

小工具

1
2
3
4
5
6
7
//用来输出 __int128_t 之类的东西。
void autoprint(auto x){
    string ans;
    while(x) ans += (x % 10) + '0', x /= 10;
    reverse(ans.begin(), ans.end());
    cout << ans;
}

对拍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import os
import random
Case = 0
random.seed(999)
while True :
    Case = Case + 1
    print(f"{Case}")
    # T = 3
    with open("std.in","w") as f :
        # 数据生成
        # print(f"{T}", file = f)
        # for i in range(T) :
        #     n = random.randint(1, 5)
        #     k = random.randint(1, 3)
        #     print(f"{n} {k}", file = f)
        #     for j in range(n) :
        #         print(f"{random.randint(1, n)}",end = " ", file = f)
        #     print("", file = f)
        #     for j in range(n) :
        #         print(f"{random.randint(1, j + 1)}",end = " ", file = f)
        #     print("", file = f)
    os.system("std < std.in > vio.out")
    os.system("vio < std.in > std.out")
    if os.system("fc std.out vio.out") != 0 :
        break

数论

简单矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct Matrix{
    int n, m;
    LL a[3][3];
    Matrix(){memset(a, 0, sizeof(a)); n = m = 0;}
    LL* operator[](int x){return a[x];}
};
Matrix operator+(Matrix x, Matrix y){
    assert(x.n == y.n && x.m == y.m);
    Matrix z;
    z.n = x.n;
    z.m = x.m;
    for(int i = 1; i <= z.n; i++){
        for(int j = 1; j <= z.m; j++) z[i][j] = (x[i][j] + y[i][j]) % mod;
    }
    return z;
}
Matrix operator*(Matrix x, Matrix y){
    assert(x.m == y.n);
    Matrix z;
    z.n = x.n;
    z.m = y.m;
    for(int i = 1; i <= z.n; i++){
        for(int j = 1; j <= z.m; j++){
            for(int k = 1; k <= x.m; k++){
                z[i][j] = (z[i][j] + x[i][k] * y[k][j]) % mod;
            }
        }
    }
    return z;
}
Matrix unit(int n){
    Matrix a; a.n = a.m = n;
    for(int i = 1; i <= n; i++) a[i][i] = 1;
    return a;
}

字符串

Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//记得调用 hash_init
//typedef long long LL;
typedef unsigned __int128 U128;
typedef __int128_t I128;
const LL P = 992345234523451717, A = 311;
LL fA[N];
static constexpr U128 inv = []() {
	U128 ret = P;
	for (int i = 0; i < 6; i++) ret *= 2 - ret * P;
	return ret; }();
constexpr U128 chk = U128(-1) / P;
bool check(I128 a, I128 b) {
	if (a < b) swap(a, b);
	return (a - b) * inv <= chk; }
void hash_init(int len){
    fA[0] = 1ll;
    for(int i = 1; i <= len; i++) fA[i] = (I128) fA[i - 1] * A % P;
}
struct Hash{
    vector<LL> h;
    void init(char *tmp, int len){
        h.push_back(0ll);
        for(int i = 1; i <= len; i++) h.push_back(((I128) h.back() * A + tmp[i]) % P);
    }
    void init(const string &tmp){
        h.push_back(0ll);
        for(int i = 1; i <= tmp.length(); i++) h.push_back(((I128) h.back() * A + tmp[i - 1]) % P);
    }
    I128 query(int l, int r){
        assert(l <= r && l >= 1 && r < h.size());
        return h[r] - (I128) h[l - 1] * fA[r - l + 1];
    }
};

Trie

1
2
3
4
5
6
7
8
9
10
11
12
template <int V> struct Trie {
    int tot, tr[V][26];
    Trie() { tot = 1; }
    void insert(char *ch, int slen) {
        int now = 1;
        for (int i = 1; i <= slen; i++) {
            int x = ch[i] - 'a';
            if (!tr[now][x]) tr[now][x] = ++tot;
            now = tr[now][x];
        }
    }
};

ACAM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
namespace ACAM{
    const int V = 26;
    /*如果题目给的是多个字符串而不是一个现成的Trie。
    那么last树的深度至多根号。*/
    int tr[N][V], last[N], fail[N], tot;
    bool v[N];
    int ins(char *st, int len){
        int now = 0;
        for(int i = 1; i <= len; i++){
            int x = st[i] -'a';
            if (!tr[now][x]) tr[now][x] = ++tot;
            now = tr[now][x];
        }
        v[now] = 1;
        return now;
    }
    // lis还可以作为ACAM中任意一棵树的拓扑序。
    // 不过这个拓扑序里面没有0号点，也就是根。
    int lis[N], head, tail;
    void bfs(){
        head = 1;
        for(int i = 0; i < V; i++){
            if (tr[0][i])
                lis[++tail] = tr[0][i];
        }
        while(head <= tail){
            int x = lis[head++];
            if(!v[fail[x]]) last[x] = last[fail[x]];
            else last[x] = fail[x];
            for(int i = 0; i < V; i++){
                int y = tr[x][i];
                if (!y) tr[x][i] = tr[fail[x]][i];
                else fail[y] = tr[fail[x]][i], lis[++tail] = y;
            }
        }
    }
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class T>
void kmp(T *s, int *fail, int n) { // 1-based
	fail[0] = -1; fail[1] = 0;
    int j = 0;
	for (int i = 2; i <= n; i++) {
		while (j != -1 && s[i] != s[j + 1]) j = fail[j];
		fail[i] = ++j;
    }
}
template<class T>
void kmp_match(T *s1, int *fail, int n, T *s2, int *ans, int m){
    ans[0] = 0;
    int j = 0;
	for (int i = 1; i <= m; i++) {
		while (j == n || (j != -1 && s1[j + 1] != s2[i])) j = fail[j];
		ans[i] = ++j;
    }
}

EXKMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template<class T>
void exkmp(T *s, int *fail, int n) { // 1-based
	fail[0] = 0; fail[1] = n;
    int l = 0, r = 0;
	for (int i = 2; i <= n; i++) {
		fail[i] = i > r ? 0 : min(r - i + 1, fail[i - l + 1]);
		while (i + fail[i] <= n && s[1 + fail[i]] == s[i + fail[i]]) fail[i]++;
		if (i + fail[i] - 1 > r) l = i, r = i + fail[i] - 1;
    }
}
template<class T>
void exkmp_match(T *s1, int *fail, int n, T *s2, int *ans, int m){
    ans[0] = 0;
    int l = 0, r = 0;
    for(int i = 1; i <= m; i++){
        ans[i] = i > r ? 0 : min(r - i + 1, fail[i - l + 1]);
		while (1 + ans[i] <= n && i + ans[i] <= m && s1[1 + ans[i]] == s2[i + ans[i]]) ans[i]++;
		if (i + ans[i] - 1 > r) l = i, r = i + ans[i] - 1;
    }
}

Manacher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
void manachar(T *s1, T *s2, int *fail, int n){
	//	need clear : none
	int nn = n + n + 1;
	for (int i = n; i >= 1; i--) s2[i << 1] = s1[i];
	for (int i = 1; i <= n + 1; i++) s2[(i << 1) - 1] = '#';
	int now = 0, p = 0;
	for (int i = 1; i <= nn; i++) {
		if (i <= p) fail[i] = min(p - i + 1, fail[now + now - i]);
		else fail[i] = 1;
		if (i + fail[i] - 1 >= p) {
			while (i + fail[i] <= nn && i - fail[i] >= 1 && s2[i + fail[i]] == s2[i - fail[i]]) fail[i]++;
			now = i; p = i + fail[i] - 1;
		}
	}
}

Lyndon 分解

1
2
3
4
5
6
7
8
9
10
11
12
void lyndon(auto *s, int n){
    int i = 1;
    while(i <= n) {
        int j = i + 1, k = i;
        while(j <= n && s[k] <= s[j]) {
            if(a[k] < a[j]) k = i;
            else k++;
            j++;
        }
        while(i <= k) i += j - k; //[i,i+j-k)即为对应的Lyndon分解 
    }
}

SA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// SA : 需要清空的数组 height,h
char ss[N];
int n;
int cc[N], sa[N], xx[N], yy[N], top, V;
int rk[N], height[N], h[N];
void getsa() {
	V = 26;
	memset(cc + 1, 0, V << 2);
	for (int i = 1; i <= n; i++) cc[xx[i] = ss[i] - 'a' + 1]++;
	for (int i = 1; i <= V; i++) cc[i] += cc[i - 1];
	for (int i = n; i >= 1; i--) sa[cc[xx[i]]--] = i;
	for (int k = 1; k < n; k <<= 1)
	{
		top = 0;
		for (int i = n; i > n - k; i--) yy[++top] = i;
		for (int i = 1; i <= n; i++) {
			if (sa[i] > k) yy[++top] = sa[i] - k;
		}
		memset(cc + 1, 0, V << 2);
		for (int i = 1; i <= n; i++) cc[xx[i]]++;
		for (int i = 1; i <= V; i++) cc[i] += cc[i - 1];
		for (int i = n; i >= 1; i--) sa[cc[xx[yy[i]]]--] = yy[i];
		swap(xx, yy);
		V = xx[sa[1]] = 1;
		for (int i = 2; i <= n; i++) xx[sa[i]] = V += !(sa[i] + k <= n && sa[i - 1] + k <= n && yy[sa[i]] == yy[sa[i - 1]] && yy[sa[i] + k] == yy[sa[i - 1] + k]);
		if (V == n) break;
	}

	for (int i = 1; i <= n; i++) rk[sa[i]] = i;
	int now = 0;
	ss[n + 1] = '\0';
	for (int i = 1; i <= n; i++)
	{
		if (now) now--;
		if (rk[i] == 1) continue;
		while (ss[i + now] == ss[sa[rk[i] - 1] + now]) now++;
		h[i] = now;
		height[rk[i]] = now;
	}
}

PAM

PAM with log dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
#define N 1000011
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
char st[N], ss[N];
namespace PAM {
	int trans[N][26], len[N], fail[N];
	// int dif[N], slink[N];
	int tot, last;
	int getfail(int pos, int x) {
		while (pos - len[x] - 1 < 1 || st[pos - len[x] - 1] != st[pos]) x = fail[x];
		return x;
	}
	void init() {
		tot = last = 1;
		len[1] = -1;
		fail[0] = 1;
	}
	void add(int pos) {
		int x = getfail(pos, last), c = st[pos] - 'a';
		if (!trans[x][c]) {
			tot++;
			len[tot] = len[x] + 2;
			fail[tot] = trans[getfail(pos, fail[x])][c];
			trans[x][c] = tot;
			// dif[tot] = len[tot] - len[fail[tot]];
			// if (dif[tot] == dif[fail[tot]]) slink[tot] = slink[fail[tot]];
			// else slink[tot] = fail[tot];
		}
		last = trans[x][c];
	}
	LL g[N];
}
// using PAM::dif;
// using PAM::fail;
// using PAM::g;
// using PAM::len;
// using PAM::slink;
// int n;
// LL dp[N];
// int main() {
// 	scanf("%s", ss + 1);
// 	n = strlen(ss + 1);
// 	for (int i = 1; i <= n / 2; i++) st[i * 2 - 1] = ss[i], st[i * 2] = ss[n - i + 1];
// 	dp[0] = 1;
// 	PAM::init();
// 	for (int i = 1; i <= n; i++) {
// 		PAM::add(i);
// 		for (int x = PAM::last; x > 1; x = slink[x]) {
// 			g[x] = dp[i - len[slink[x]] - dif[x]];
// 			if (dif[x] == dif[fail[x]]) g[x] = (g[x] + g[fail[x]]) % mod;
// 			if (i % 2 == 0) dp[i] = (dp[i] + g[x]) % mod;
// 		}
// 	}
// 	printf("%lld\n", dp[n]);
// 	return 0;
// }

广义 PAM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
void get_char_array(char *s){
    static char st[N];
    cin >> st;
    memcpy(s + 1, st, sizeof(char) * (strlen(st) + 1));
}
namespace PAM {
    const int V1 = N;
    const int V2 = 26;
    int trans[V1][V2], quick[V1][V2], fail[V1], len[V1], tot;
    int ss[V1], slen;
    void init() {
        slen=0;
        memset(trans[0], 0, sizeof(trans[0])); memset(quick[0], 0, sizeof(quick[0]));
        memset(trans[1], 0, sizeof(trans[1])); memset(quick[1], 0, sizeof(quick[1]));
        tot = 1; len[1] = -1; fail[0] = 1;
        for (int i = 0; i < V2; i++) quick[0][i] = quick[1][i] = 1;
    }
    int getfail(int pos, int x) {
        if (pos - len[x] - 1 >= 1 && ss[pos - len[x] - 1] == ss[pos]) return x;
        else return quick[x][ss[pos]];
    }
    int add(int c, int last) {
        int pos = ++slen;
        ss[slen] = c;
        int x = getfail(pos, last);
        if (!trans[x][c]) {
            tot++;
            memset(trans[tot],0,sizeof(trans[tot]));
            len[tot] = len[x] + 2;
            fail[tot] = trans[quick[x][c]][c];
            memcpy(quick[tot], quick[fail[tot]], sizeof(quick[tot]));
            quick[tot][ss[pos - len[fail[tot]]]] = fail[tot];
            trans[x][c] = tot;
        }
        x = trans[x][c];
        return x;
    }
    void del() { slen--; }
};
namespace Trie {
    const int V1 = N;
    const int V2 = 26;
    int tr[V1][V2], fa[V1], type[V1];
    int last[V1], tot;
    void dfs(int x) {
        int y;
        for (int i = 0; i < V2; i++) {
            if (y = tr[x][i]) {
                last[y] = PAM::add(i, last[x], type[y]);
                dfs(y);
                PAM::del();
            }
        }
    }
    void init() { tot = 1; }
    void build() {
        PAM::init();
        last[1] = 1;
        dfs(1);
    }
    void insert(char *ch, int slen) {
        int now = 1;
        for (int i = 1; i <= slen; i++) {
            int x = ch[i] - 'a';
            if (!tr[now][x]) tr[now][x] = ++tot;
            now = tr[now][x];
        }
    }
};
//Trie::init();
//...
//Trie::build();

前后端插入的 PAM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
namespace PAM{
    int trans[N][26],fail[N],len[N];
    int tot,lastl,lastr;
    int ss[NN],L,R;
    //slen表示前端能够插入的最多字符数量。
    void init(int slen){
        L=slen+1;R=slen;
        tot=lastl=lastr=1;len[1]=-1;fail[0]=1;
    }
    int getfaill(int pos,int x){
        while(pos+len[x]+1>R || ss[pos+len[x]+1]!=ss[pos])x=fail[x];
        return x;
    }
    int getfailr(int pos,int x){
        while(pos-len[x]-1<L || ss[pos-len[x]-1]!=ss[pos])x=fail[x];
        return x;
    }
    void add(int c,int type){//0 插在前面，1插在后面
        int x,pos;
        if(!type)ss[pos=--L]=c,x=getfaill(pos,lastl);
        else ss[pos=++R]=c,x=getfailr(pos,lastr);
        if(!trans[x][c]){
            tot++;
            len[tot]=len[x]+2;
            if(!type)fail[tot]=trans[getfaill(pos,fail[x])][c];
            else fail[tot]=trans[getfailr(pos,fail[x])][c];
            trans[x][c]=tot;
        }
        if(!type){
            lastl=trans[x][c];
            if(len[lastl]==R-L+1)lastr=lastl;
        }
        else{
            lastr=trans[x][c];
            if(len[lastr]==R-L+1)lastl=lastr;
        }
    }
}

SAM

单串SAM with 拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
void get_char_array(char *s){
    static char st[N];
    cin >> st;
    memcpy(s + 1, st, sizeof(char) * (strlen(st) + 1));
}

//记得初始化
template<int V1, int V2> struct SAM {
    /*np就是一个前缀所在的节点，而且一个节点不可能同时包含两个前缀。
    拓扑序可以通过长度桶排得到。*/
    int trans[V1 * 2][V2], mxl[V1 * 2], fail[V1 * 2], tot, last;
    int cnt[V1 * 2];
    void init()
    {
        tot = last = 1;
        memset(trans[1], 0, sizeof(trans[1]));
        cnt[1] = 0;
    }
    void add(int c)
    {
        int p = last, np = last = ++tot;
        
        cnt[np] = 1;
        memset(trans[np], 0, sizeof(trans[np]));
        mxl[np] = mxl[p] + 1;

        for (; p && !trans[p][c]; p = fail[p]) trans[p][c] = np;
        if (!p) fail[np] = 1;
        else {
            int q = trans[p][c];
            if (mxl[q] == mxl[p] + 1) fail[np] = q;
            else {
                int nq = ++tot; // cnt[tot]=0;
                fail[nq] = fail[q];
                fail[q] = nq;
                mxl[nq] = mxl[p] + 1;
                memcpy(trans[nq], trans[q], sizeof(trans[q]));
                fail[np] = nq;
                for (; p && trans[p][c] == q; p = fail[p]) trans[p][c] = nq;
            }
        }
    }
    int cc[V1], qu[V1 * 2];
    void init(int n) {
        LL ans = 0ll;
        memset(cc, 0, (n + 1) << 2);
        for (int i = 1; i <= tot; i++) cc[mxl[i]]++;
        for (int i = 1; i <= n; i++) cc[i] += cc[i - 1];
        for (int i = 1; i <= tot; i++) qu[cc[mxl[i]]--] = i;
        for (int i = tot; i >= 1; i--){
            int x = qu[i];
            assert(fail[i] != i);
            if(x != 1) cnt[fail[x]] += cnt[x];
            // debug("%d %d\n", cnt[x], mxl[x]);
            if(cnt[x] != 1){
                ans = max(1ll * cnt[x] * mxl[x], ans);
            }
        }
        cout << ans << "\n";
    }
};
SAM<N, 26> sam;


char st[N];
int n;
int main(){
    // cin.sync_with_stdio(false);
    // cin.tie(0);
    get_char_array(st); n = strlen(st + 1);
    sam.init();
    for(int i = 1; i <= n; i++) sam.add(st[i] - 'a');
    sam.init(n);
    return 0;
}

在线 BFS 构建广义 SAM

所有广义 SAM 的代码来源均为：https://www.luogu.com.cn/article/pm10t1pc

作了小幅度修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
template <int V1, int V2>
struct SAM
{
    int tot, fail[V1 * 2], maxlen[V1 * 2], trans[V1 * 2][V2];
    SAM() { tot = 1; }
    int insert(int c, int last) {
        if (trans[last][c]) {
            int p = last, q = trans[p][c];
            if (maxlen[p] + 1 == maxlen[q]) return q;
            else {
                int nq = ++tot;
                fail[nq] = fail[q];
                fail[q] = nq;
                maxlen[nq] = maxlen[p] + 1;
                memcpy(trans[nq], trans[q], sizeof(trans[q]));
                for (; p && trans[p][c] == q; p = fail[p]) trans[p][c] = nq;
                // 可以直接复制下面的代码。
                return nq;
            }
        }
        int p = last, np = ++tot;
        maxlen[np] = maxlen[p] + 1;
        for (; p && !trans[p][c]; p = fail[p]) trans[p][c] = np;
        if (!p) fail[np] = 1;
        else {
            int q = trans[p][c];
            if (maxlen[q] == maxlen[p] + 1) fail[np] = q;
            else {
                int nq = ++tot;
                fail[nq] = fail[q];
                fail[q] = nq;
                maxlen[nq] = maxlen[p] + 1;
                memcpy(trans[nq], trans[q], sizeof(trans[q]));
                for (; p && trans[p][c] == q; p = fail[p])
                    trans[p][c] = nq;
                fail[np] = nq;
            }
        }
        return np;
    }
};
// scanf("%s",st+1);int slen=strlen(st+1);
// int last=1;
// for(int j=1;j<=slen;j++)last=sam.insert(st[j]-'a',last);

离线 DFS 构建广义 SAM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
#define M 1100000
using namespace std;
typedef long long LL;
void get_char_array(char *s){
    static char st[M];
    cin >> st;
    memcpy(s + 1, st, sizeof(char) * (strlen(st) + 1));
}

template <int V> struct Trie {
    int tot, tr[V][26];
    Trie() { tot = 1; }
    void insert(char *ch, int slen) {
        int now = 1;
        for (int i = 1; i <= slen; i++) {
            int x = ch[i] - 'a';
            if (!tr[now][x]) tr[now][x] = ++tot;
            now = tr[now][x];
        }
    }
};
Trie <M> trie;
template <int V1, int V2> struct EXSAM {
    int tot, pos[V1], fail[V1 * 2], maxlen[V1 * 2], trans[V1 * 2][V2];
    EXSAM() { tot = 1; }
    int insert(int c, int last) {
        if (trans[last][c]) {
            int p = last, q = trans[p][c];
            if (maxlen[p] + 1 == maxlen[q]) return q;
            else {
                int nq = ++tot;
                fail[nq] = fail[q];
                fail[q] = nq;
                maxlen[nq] = maxlen[p] + 1;
                memcpy(trans[nq], trans[q], sizeof(trans[q]));
                for (; p && trans[p][c] == q; p = fail[p]) trans[p][c] = nq;
                return nq;
            }
        }
        int p = last, np = ++tot;
        maxlen[np] = maxlen[p] + 1;
        for (; p && !trans[p][c]; p = fail[p]) trans[p][c] = np;
        if (!p) fail[np] = 1;
        else {
            int q = trans[p][c];
            if (maxlen[q] == maxlen[p] + 1) fail[np] = q;
            else {
                int nq = ++tot;
                fail[nq] = fail[q];
                fail[q] = nq;
                maxlen[nq] = maxlen[p] + 1;
                memcpy(trans[nq], trans[q], sizeof(trans[q]));
                for (; p && trans[p][c] == q; p = fail[p])
                    trans[p][c] = nq;
                fail[np] = nq;
            }
        }
        return np;
    }
    void dfs(int x) {
        int y;
        for (int i = 0; i < V2; i++) {
            if (y = trie.tr[x][i]) pos[y] = insert(i, pos[x]), dfs(y);
        }
    }
    void build() {
        pos[1] = 1;
        dfs(1);
    }
    LL getans() {
        LL ans = 0;
        for (int i = 2; i <= tot; i++) ans += maxlen[i] - maxlen[fail[i]];
        return ans;
    }
};
int n;
char st[M];
EXSAM <M, 26> sam;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        get_char_array(st);
        trie.insert(st, strlen(st + 1));
    }
    sam.build();
    printf("%lld\n%d\n", sam.getans(), sam.tot);
    return 0;
}

离线 BFS 构建广义 SAM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
#define M 1100000
using namespace std;
typedef long long LL;
void get_char_array(char *s){
    static char st[M];
    cin >> st;
    memcpy(s + 1, st, sizeof(char) * (strlen(st) + 1));
}

template <int V> struct Trie {
    int tot, tr[V][26], fa[V], c[V];
    Trie() { tot = 1; }
    void insert(char *ch, int slen) {
        int now = 1;
        for (int i = 1; i <= slen; i++) {
            int x = ch[i] - 'a';
            if (!tr[now][x]) tr[now][x] = ++tot, c[tot] = x, fa[tot] = now;
            now = tr[now][x];
        }
    }
};
Trie <M> trie;
template <int V1, int V2> struct EXSAM {
    int tot, pos[V1], fail[V1 * 2], maxlen[V1 * 2], trans[V1 * 2][V2];
    queue<int> Q;
    EXSAM() { tot = 1; }
    int insert(int c, int last) {
        int p = last, np = ++tot;
        maxlen[np] = maxlen[p] + 1;
        for (; p && !trans[p][c]; p = fail[p]) trans[p][c] = np;
        if (!p) fail[np] = 1;
        else {
            int q = trans[p][c];
            if (maxlen[q] == maxlen[p] + 1) fail[np] = q;
            else {
                int nq = ++tot;
                fail[nq] = fail[q];
                fail[q] = nq;
                maxlen[nq] = maxlen[p] + 1;
                memcpy(trans[nq], trans[q], sizeof(trans[q]));
                for (; p && trans[p][c] == q; p = fail[p]) trans[p][c] = nq;
                fail[np] = nq;
            }
        }
        return np;
    }
    void build() {
        pos[1] = 1;
        for (int i = 0; i < V2; i++) {
            if (trie.tr[1][i]) Q.push(trie.tr[1][i]);
        }
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            pos[x] = insert(trie.c[x], pos[trie.fa[x]]);
            for (int i = 0; i < V2; i++) {
                if (trie.tr[x][i]) Q.push(trie.tr[x][i]);
            }
        }
    }
    LL getans() {
        LL ans = 0;
        for (int i = 2; i <= tot; i++) ans += maxlen[i] - maxlen[fail[i]];
        return ans;
    }
};
int n;
char st[M];
EXSAM <M, 26> sam;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        get_char_array(st);
        trie.insert(st, strlen(st + 1));
    }
    sam.build();
    printf("%lld\n%d\n", sam.getans(), sam.tot);
    return 0;
}

Runs

Hash 写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
typedef pair<int, int> PII;
const int N = 1e6 + 5;
const LL mod = 998244335, base = 29;
char st[N];
int n;
struct Runs {
    int l, r, p;
};
vector<Runs> run;
bool cmp(Runs x, Runs y) { return x.l != y.l ? x.l < y.l : x.r < y.r; }
bool operator==(Runs x, Runs y) { return x.l == y.l && x.r == y.r; }
LL fc[N], ff[N];
void init()
{
    fc[0] = 1;
    for (int i = 1; i <= n; i++)
        fc[i] = fc[i - 1] * base % mod;
    for (int i = 1; i <= n; i++)
        ff[i] = (ff[i - 1] * base + st[i] - 'A' + 1) % mod;
}
LL gv(int l, int r) { return ((ff[r] - ff[l - 1] * fc[r - l + 1]) % mod + mod) % mod; }
LL gethash(int l, int r) { return gv(l, r); }
int gl(int x, int y)
{
    int ans = 0, l = 1, r = min(x, y);
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (gethash(x - mid + 1, x) == gethash(y - mid + 1, y))
            ans = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    return ans;
}
int gr(int x, int y)
{
    int ans = 0, l = 1, r = min(n - x + 1, n - y + 1);
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (gethash(x, x + mid - 1) == gethash(y, y + mid - 1))
            ans = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    return ans;
}

bool getcmp(int x, int y)
{
    int len = gr(x, y);
    return st[x + len] < st[y + len];
}
int ly[N];
void lyndon(bool type)
{
    stack<PII> stk;
    stk.push({n, n});
    ly[n] = n;
    for (int i = n - 1; i >= 1; i--)
    {
        int now = i;
        while (!stk.empty() && getcmp(i, stk.top().first) != type)
            now = stk.top().second, stk.pop();
        ly[i] = now;
        stk.push({i, now});
    }
}
void getrun()
{
    for (int l = 1; l <= n; l++)
    {
        int r = ly[l], ll = l, rr = r;
        if (l != 1)
            ll -= gl(l - 1, r);
        if (r != n)
            rr += gr(l, r + 1);
        if (rr - ll + 1 >= 2 * (r - l + 1))
            run.push_back({ll, rr, r - l + 1});
    }
}
int main()
{
    scanf("%s", st + 1);
    n = strlen(st + 1);
    init();
    for (int op = 0; op <= 1; op++) {
        lyndon(op);
        getrun();
    }
    sort(run.begin(),run.end(),[](Runs x, Runs y) {
        return x == y ? x.p < y.p : (x.l != y.l ? x.l < y.l : x.r < y.r);});
    run.erase(unique(run.begin(), run.end()), run.end());
    printf("%d\n", run.size());
    for (auto [l, r, p] : run)
        printf("%d %d %d\n", l, r, p);
    return 0;
}

SA 写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+5;
int n;
struct Runs{
    int l,r,p;
};vector<Runs> run;
bool operator==(Runs x,Runs y){return x.l==y.l && x.r==y.r;}
struct SA{
    char ss[N];
    int cc[N],sa[N],xx[N],yy[N],top,V;
    int rk[N],height[N],h[N],rmq[20][N];
    int getlcp(int x,int y){
        x=rk[x];y=rk[y];
        if(x>y)swap(x,y);
        x++;int k=__lg(y-x+1);
        return min(rmq[k][x],rmq[k][y-(1<<k)+1]);
    }
    int getcmp(int x,int y){//x<y
        int t=getlcp(x,y);
        return ss[x+t]<ss[y+t];
    }
    void getsa(){
        V=256;memset(cc+1,0,V<<2);
        for(int i=1;i<=n;i++)cc[xx[i]=ss[i]]++;
        for(int i=1;i<=V;i++)cc[i]+=cc[i-1];
        for(int i=n;i>=1;i--)sa[cc[xx[i]]--]=i;
        for(int k=1;k<n;k<<=1){
            top=0;for(int i=n;i>n-k;i--)yy[++top]=i;
            for(int i=1;i<=n;i++){
                if(sa[i]>k)yy[++top]=sa[i]-k;
            }
            memset(cc+1,0,V<<2);
            for(int i=1;i<=n;i++)cc[xx[i]]++;
            for(int i=1;i<=V;i++)cc[i]+=cc[i-1];
            for(int i=n;i>=1;i--)sa[cc[xx[yy[i]]]--]=yy[i];
            swap(xx,yy);
            V=xx[sa[1]]=1;for(int i=2;i<=n;i++)xx[sa[i]]=V+=!(sa[i]+k<=n && sa[i-1]+k<=n && yy[sa[i]]==yy[sa[i-1]] && yy[sa[i]+k]==yy[sa[i-1]+k]);
            if(V==n)break;
        }
        for(int i=1;i<=n;i++)rk[sa[i]]=i;
        int now=0;
        for(int i=1;i<=n;i++){
            if(now)now--;
            if(rk[i]==1)continue;
            while(ss[i+now]==ss[sa[rk[i]-1]+now])now++;
            h[i]=now;height[rk[i]]=now;
        }
        for(int i=1;i<=n;i++)rmq[0][i]=height[i];
        for(int i=1;i<=__lg(n);i++){
            for(int j=n-(1<<i)+1;j>=1;j--)rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
        }
    }
}s0,s1;
char st[N];
int ly[N];
void lyndon(bool op){
    stack<PII> stk;stk.push({n,n});ly[n]=n;
    for(int i=n-1;i>=1;i--){
        int now=i;
        while(!stk.empty() && s0.getcmp(i,stk.top().first)!=op)now=stk.top().second,stk.pop();
        ly[i]=now;
        stk.push({i,now});
    }
}
void getrun(){
    for(int l=1;l<=n;l++){
        int r=ly[l],ll=l,rr=r;
        if(l!=1)ll-=s1.getlcp(n-r+1,n-(l-1)+1);
        if(r!=n)rr+=s0.getlcp(l,r+1);
        if(rr-ll+1>=2*(r-l+1))run.push_back({ll,rr,r-l+1});
    }
}
int main(){
    scanf("%s",st+1);n=strlen(st+1);
    // printf("%d %d %d\n",__lg(2),__lg(4),__lg(5));
    for(int i=1;i<=n;i++)s0.ss[i]=s1.ss[n-i+1]=st[i];
    st[n+1]=s0.ss[n+1]=s1.ss[n+1]='\0';
    s0.getsa();s1.getsa();
    for(int op=0;op<=1;op++){
        lyndon(op);
        getrun();
    }
    sort(run.begin(),run.end(),[](Runs x, Runs y) {
        return x == y ? x.p < y.p : (x.l != y.l ? x.l < y.l : x.r < y.r);});
    run.erase(unique(run.begin(),run.end()),run.end());
    printf("%d\n",run.size());
    for(auto [l,r,p]:run){
        printf("%d %d %d\n",l,r,p);
    }
    return 0;
}

数据结构

简单线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
struct node{
    int lc, rc;
    int val, lazy;
}tr[N * 2]; int cnt;
void update(int x){
    assert(tr[x].lc);
}
void pushlazy(int x, int k){
    
}
void pushdown(int x){
    assert(tr[x].lc);
    pushlazy(tr[x].lc, tr[x].lazy);
    pushlazy(tr[x].rc, tr[x].lazy);
}
int bt(int l, int r){
    int x = ++cnt;
    tr[x].lc = tr[x].rc = tr[x].val = tr[x].lazy = 0;
    if(l < r){
        int mid = l + (r - l) / 2;
        tr[x].lc = bt(l, mid);
        tr[x].rc = bt(mid + 1, r);
        update(x);
    }
    else{
        
    }
    return x;
}
void change(int x, int l, int r, int ll, int rr){
    if(rr < l || ll > r || ll > rr) return ;
    if(ll <= l && r <= rr){
        
        return ;
    }
    pushdown(x);
    int mid = l + (r - l) / 2;
    change(tr[x].l, l, mid, ll, rr);
    change(tr[x].r, mid + 1, r, ll, rr);
    update(x);
}

简单树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lowbit(int x){return x & -x;}
int bst[N];
void change(int x, int k){
    while(x <= n){
        bst[x] += k;
        x += lowbit(x);
    }
}
int findans(int x){
    int ans = 0;
    while(x){
        ans += bst[x];
        x -= lowbit(x);
    }
    return ans;
}

图论

LCA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n, m;
int fa[N][SN], dep[N];
vector<int> e[N];
void dfs(int x) {
	for (int i = 1; i <= 18; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
	for (auto y : e[x]) {
		if (y == fa[x][0]) continue;
		dep[y] = dep[x] + 1;
		fa[y][0] = x;
		dfs(y);
	}
}
int findlca(int x, int y) {
	if (dep[x] > dep[y]) swap(x, y);
	for (int i = 18; i >= 0; i--) {
		if (dep[fa[y][i]] >= dep[x]) y = fa[y][i];
	}
	if (x == y) return x;
	for (int i = 18; i >= 0; i--) {
		if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	}
	return fa[x][0];
}

简单树链剖分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> e[N];
int siz[N], zs[N], fa[N];
void findzs(int x){
    siz[x] = 1; zs[x] = 0;
    for(auto y : e[x]){
        if(y == fa[x]) continue;
        fa[y] = x;
        findzs(y);
        siz[x] += siz[y];
        if(siz[y] > siz[zs[x]]) zs[x] = y;
    }
}
int lt[N], dfn[N], ti, stk[N], dl[N], dr[N];
void getl(int x, int f){
    lt[x] = f;
    stk[dfn[x] = ++ti] = x;
    dl[x] = ti;
    if(zs[x]) getl(zs[x], f);
    for(auto [y, c] : e[x]){
        if(y == fa[x] || y == zs[x]) continue;
        getl(y, y);
    }
    dr[x] = ti;
}

多项式

NTT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using poly = vector<int>;
poly omega[25]; // 单位根
// n 是 DFT 的最大长度，例如如果最多有两个长为 m 的多项式相乘，
// 或者求逆的长度为 m，那么 n 需要 >= 2m
void ntt_init(int n) { // n = 2^k
	for (int k = 2, d = 0; k <= n; k *= 2, d++) {
		omega[d].resize(k + 1);
		int wn = ksm(3, (mod - 1) / k), tmp = 1;
		for (int i = 0; i <= k; i++) { omega[d][i] = tmp;
			tmp = (LL)tmp * wn % mod; } } }
// 传入的数必须是 [0, mod) 范围内，不能有负的
// 否则把 d == 16 改成 d % 8 == 0 之类，多取几次模
void ntt(int *c, int n, int tp) {
    assert(n <= (1 << 16));
	static ULL a[N];
	for (int i = 0; i < n; i++) a[i] = c[i];
	for (int i = 1, j = 0; i < n - 1; i++) {
		int k = n; do j ^= (k >>= 1); while (j < k);
		if (i < j) swap(a[i], a[j]); }
	for (int k = 1, d = 0; k < n; k *= 2, d++) {
		if (d == 16) for (int i = 0; i < n; i++) a[i] %= mod;
		for (int i = 0; i < n; i += k * 2)
			for (int j = 0; j < k; j++) {
				int w = omega[d][tp > 0 ? j : k * 2 - j];
				ULL u = a[i + j], v = w * a[i + j + k] % mod;
				a[i + j] = u + v;
				a[i + j + k] = u - v + mod; } }
	if (tp>0) {for (int i = 0; i < n; i++) c[i] = a[i] % mod;}
	else { int inv = ksm(n, mod - 2);
		for (int i = 0; i < n; i++) c[i] = a[i] * inv % mod;}}
poly poly_auto_mul(poly a, poly b) { // 自动判断长度的乘法
    if(a.size() < b.size()) swap(a, b);
    if(b.size() <= 100){
        poly c(a.size() + b.size() - 1);
        for(int i = 0; i < a.size(); i++){
            for(int j = 0; j < b.size(); j++){
                c[i + j] = (c[i + j] + 1ll * a[i] * b[j]) % mod;
            }
        }
        return c;
    }
    int res_len = (int)a.size() + (int)b.size() - 1;
    int ntt_n = 1; while (ntt_n < res_len) ntt_n *= 2;
    a.resize(ntt_n); b.resize(ntt_n);
    ntt(a.data(), ntt_n, 1); ntt(b.data(), ntt_n, 1);
    for (int i = 0; i < ntt_n; i++)
        a[i] = (LL)a[i] * b[i] % mod;
    ntt(a.data(), ntt_n, -1); a.resize(res_len); return a; }

半在线卷积 NTT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using poly = vector<int>;
poly omega[25]; // 单位根
// n 是 DFT 的最大长度，例如如果最多有两个长为 m 的多项式相乘，
// 或者求逆的长度为 m，那么 n 需要 >= 2m
void ntt_init(int n) { // n = 2^k
	for (int k = 2, d = 0; k <= n; k *= 2, d++) {
		omega[d].resize(k + 1);
		int wn = ksm(3, (mod - 1) / k), tmp = 1;
		for (int i = 0; i <= k; i++) { omega[d][i] = tmp;
			tmp = (LL)tmp * wn % mod; } } }
// 传入的数必须是 [0, mod) 范围内，不能有负的
// 否则把 d == 16 改成 d % 8 == 0 之类，多取几次模
void ntt(int *c, int n, int tp) {
    assert(n <= (1 << 16));
	static ULL a[N];
	for (int i = 0; i < n; i++) a[i] = c[i];
	for (int i = 1, j = 0; i < n - 1; i++) {
		int k = n; do j ^= (k >>= 1); while (j < k);
		if (i < j) swap(a[i], a[j]); }
	for (int k = 1, d = 0; k < n; k *= 2, d++) {
		if (d == 16) for (int i = 0; i < n; i++) a[i] %= mod;
		for (int i = 0; i < n; i += k * 2)
			for (int j = 0; j < k; j++) {
				int w = omega[d][tp > 0 ? j : k * 2 - j];
				ULL u = a[i + j], v = w * a[i + j + k] % mod;
				a[i + j] = u + v;
				a[i + j + k] = u - v + mod; } }
	if (tp>0) {for (int i = 0; i < n; i++) c[i] = a[i] % mod;}
	else { int inv = ksm(n, mod - 2);
		for (int i = 0; i < n; i++) c[i] = a[i] * inv % mod;}}
poly poly_auto_mul(poly a, poly b) { // 自动判断长度的乘法
    if(a.size() < b.size()) swap(a, b);
    if(b.size() <= 100){
        poly c(a.size() + b.size() - 1);
        for(int i = 0; i < a.size(); i++){
            for(int j = 0; j < b.size(); j++){
                c[i + j] = (c[i + j] + 1ll * a[i] * b[j]) % mod;
            }
        }
        return c;
    }
    int res_len = (int)a.size() + (int)b.size() - 1;
    int ntt_n = 1; while (ntt_n < res_len) ntt_n *= 2;
    a.resize(ntt_n); b.resize(ntt_n);
    ntt(a.data(), ntt_n, 1); ntt(b.data(), ntt_n, 1);
    for (int i = 0; i < ntt_n; i++)
        a[i] = (LL)a[i] * b[i] % mod;
    ntt(a.data(), ntt_n, -1); a.resize(res_len); return a; }
void solveg(int l, int r){
    if(l == r) return ;
    int mid = (l + r) >> 1;
    solveg(l, mid);
    {
        poly lg, rg;
        for(int i = l; i <= mid; i++) lg.push_back(g[i]);
        for(int i = 1; i <= r - l; i++) rg.push_back(fc[i]);
        poly ans = poly_auto_mul(lg, rg);
        for(int i = mid + 1; i <= r; i++) g[i] = (g[i] - ans[i - (l + 1)] + mod) % mod;
    }
    solveg(mid + 1, r);
}

FWT

图论

带花树（一般图最大匹配）

代码来源：https://uoj.ac/submission/412225

但我小改了一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
using namespace std;
template<int V> struct blossom_tree{
    vector<vector<int> > e;
    int pre[V], tim;
    int h[V], tot;
    int match[V], f[V], tp[V], tic[V];
    queue<int> que;
    blossom_tree(){
        e.resize(V);
        tim = tot = 0;
        memset(pre, 0, sizeof(pre));
        memset(h, 0, sizeof(h));
        memset(match, 0, sizeof(match));
        memset(f, 0, sizeof(f));
        memset(tp, 0, sizeof(tp));
        memset(tic, 0, sizeof(tic));
    }
    int find(int x) {
        return f[x] == x ? f[x] : f[x] = find(f[x]);
    }
    void add(int u, int v) {
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int lca(int x, int y) {
        for (++tim;; swap(x, y)) {
            if (x) {
                x = find(x);
                if (tic[x] == tim) return x;
                else tic[x] = tim, x = pre[match[x]];
            }
        }
    }
    void shrink(int x, int y, int p) {
        while (find(x) != p) {
            pre[x] = y, y = match[x];
            if (tp[y] == 2) tp[y] = 1, que.push(y);
            if (find(x) == x) f[x] = p;
            if (find(y) == y) f[y] = p;
            x = pre[y];
        }
    }
    bool aug(int s, int n) {
        for (int i = 1; i <= n; ++i) f[i] = i;
        memset(tp, 0, sizeof(tp)), memset(pre, 0, sizeof(pre));
        while(!que.empty()) que.pop();
        que.push(s);
        tp[s] = 1; // 1: type A ; 2: type B
        while (!que.empty()) {
            int x = que.front(); que.pop();
            for (auto v : e[x]) {
                if (find(v) == find(x) || tp[v] == 2) continue;
                if (!tp[v]) {
                    tp[v] = 2, pre[v] = x;
                    if (!match[v]) {
                        for (int now = v, last, tmp; now; now = last) {
                            last = match[tmp = pre[now]];
                            match[now] = tmp, match[tmp] = now;
                        }
                        return true;
                    }
                    tp[match[v]] = 1, que.push(match[v]);
                }
                else if (tp[v] == 1) {
                    int l = lca(x, v);
                    shrink(x, v, l);
                    shrink(v, x, l);
                }
            }
        }
        return false;
    }
    int solve(int n){
        int ans = 0;
        for (int i = 1; i <= n; ++i) ans += (!match[i] && aug(i, n));
        return ans;
    }
};
const int N = 5e2 + 5;
int main()
{
    int n, m;
    cin >> n >> m;
    blossom_tree<N> b;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;
        b.add(x, y);
    }
    cout << b.solve(n) << "\n";
    for (int i = 1; i <= n; ++i) cout << b.match[i] << " ";
    cout << "\n";
    return 0;
}

带权带花树（一般图最大权匹配）

代码来源：https://uoj.ac/submission/540763

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
#include <bits/stdc++.h>
using namespace std;

template <class T, int V> struct weighted_blossom_tree
{
	enum { N = V * 2 };
	static const T inf = numeric_limits<T>::max() >> 1;
	struct Q
	{
		int u, v;
		T w;
	} e[N][N];
	T lab[N];

	inline T d(const Q &x) { return lab[x.u] + lab[x.v] - e[x.u][x.v].w * 2; }

	int n, m, id, h, t;
	int lk[N], sl[N], st[N], f[N], b[N][N], s[N], ed[N], q[N];
	vector<int> p[N];
	void upd(int u, int v)
	{
		if (!sl[v] || d(e[u][v]) < d(e[sl[v]][v]))
			sl[v] = u;
	}
	void ss(int v)
	{
		sl[v] = 0;
		for (int u = 1; u <= n; u++)
			if (e[u][v].w > 0 && st[u] != v && !s[st[u]])
				upd(u, v);
	}
	void ins(int u)
	{
		if (u <= n)
			q[++t] = u;
		else
			for (int v : p[u])
				ins(v);
	}
	void mdf(int u, int w)
	{
		st[u] = w;
		if (u > n)
			for (int v : p[u])
				mdf(v, w);
	}
	int gr(int u, int v)
	{
		v = find(p[u].begin(), p[u].end(), v) - p[u].begin();
		if (v & 1) {
			reverse(p[u].begin() + 1, p[u].end());
			return (int)p[u].size() - v;
		}
		return v;
	}
	void stm(int u, int v)
	{
		lk[u] = e[u][v].v;
		if (u <= n)
			return;
		Q w = e[u][v];
		int x = b[u][w.u], y = gr(u, x);
		for (int i = 0; i < y; i++)
			stm(p[u][i], p[u][i ^ 1]);
		stm(x, v);
		rotate(p[u].begin(), p[u].begin() + y, p[u].end());
	}
	void aug(int u, int v)
	{
		int w = st[lk[u]];
		stm(u, v);
		if (!w)
			return;
		stm(w, st[f[w]]);
		aug(st[f[w]], w);
	}
	int lca(int u, int v)
	{
		for (++id; u || v; swap(u, v)) {
			if (!u)
				continue;
			if (ed[u] == id)
				return u;
			ed[u] = id;
			if (u = st[lk[u]])
				u = st[f[u]];
		}
		return 0;
	}
	void add(int u, int a, int v)
	{
		int x = n + 1, i, j;
		while (x <= m && st[x])
			++x;
		if (x > m)
			++m;
		lab[x] = s[x] = st[x] = 0;
		lk[x] = lk[a];
		p[x].clear();
		p[x].push_back(a);
		for (i = u; i != a; i = st[f[j]]) {
			p[x].push_back(i);
			j = st[lk[i]];
			p[x].push_back(j);
			ins(j);
		}
		reverse(p[x].begin() + 1, p[x].end());
		for (i = v; i != a; i = st[f[j]]) {
			p[x].push_back(i);
			j = st[lk[i]];
			p[x].push_back(j);
			ins(j);
		}
		mdf(x, x);
		for (i = 1; i <= m; i++)
			e[x][i].w = e[i][x].w = 0;
		memset(b[x] + 1, 0, n * sizeof b[0][0]);
		for (int u : p[x]) {
			for (v = 1; v <= m; v++)
				if (!e[x][v].w || d(e[u][v]) < d(e[x][v])) {
					e[x][v] = e[u][v];
					e[v][x] = e[v][u];
				}
			for (v = 1; v <= n; v++)
				if (b[u][v])
					b[x][v] = u;
		}
		ss(x);
	}
	void ex(int u)
	{
		assert(s[u] == 1);
		for (int x : p[u])
			mdf(x, x);
		int a = b[u][e[u][f[u]].u];
		int r = gr(u, a);
		for (int i = 0; i < r; i += 2) {
			int x = p[u][i], y = p[u][i + 1];
			f[x] = e[y][x].u;
			s[x] = 1;
			s[y] = 0;
			sl[x] = 0;
			ss(y);
			ins(y);
		}
		s[a] = 1;
		f[a] = f[u];
		for (int i = r + 1; i < p[u].size(); i++) {
			s[p[u][i]] = -1;
			ss(p[u][i]);
		}
		st[u] = 0;
	}
	bool on(const Q &e)
	{
		int u = st[e.u], v = st[e.v], a;
		if (s[v] == -1) {
			f[v] = e.u;
			s[v] = 1;
			a = st[lk[v]];
			sl[v] = sl[a] = s[a] = 0;
			ins(a);
		} else if (!s[v]) {
			a = lca(u, v);
			if (!a) {
				aug(u, v);
				aug(v, u);
				return true;
			} else
				add(u, a, v);
		}
		return false;
	}
	bool bfs()
	{
		fill(s + 1, s + 1 + m, -1);
		fill(sl + 1, sl + 1 + m, 0);
		h = 1;
		t = 0;
		int i, j;
		for (i = 1; i <= m; i++)
			if (st[i] == i && !lk[i]) {
				f[i] = s[i] = 0;
				ins(i);
			}
		if (h > t)
			return 0;
		while (1) {
			while (h <= t) {
				int u = q[h++], v;
				if (s[st[u]] != 1)
					for (v = 1; v <= n; v++)
						if (e[u][v].w > 0 && st[u] != st[v]) {
							if (d(e[u][v]))
								upd(u, st[v]);
							else if (on(e[u][v]))
								return true;
						}
			}
			T x = inf;
			for (i = n + 1; i <= m; i++)
				if (st[i] == i && s[i] == 1)
					x = min(x, lab[i] >> 1);
			for (i = 1; i <= m; i++)
				if (st[i] == i && sl[i] && s[i] != 1)
					x = min(x, d(e[sl[i]][i]) >> s[i] + 1);
			for (i = 1; i <= n; i++)
				if (s[st[i]] != -1)
					if ((lab[i] += (s[st[i]] * 2 - 1) * x) <= 0)
						return false;
			for (i = n + 1; i <= m; i++)
				if (st[i] == i && s[st[i]] != -1)
					lab[i] += (2 - s[st[i]] * 4) * x;
			h = 1;
			t = 0;
			for (i = 1; i <= m; i++)
				if (st[i] == i && sl[i] && st[sl[i]] != i && !d(e[sl[i]][i]) &&
				    on(e[sl[i]][i]))
					return true;
			for (i = n + 1; i <= m; i++)
				if (st[i] == i && s[i] == 1 && !lab[i])
					ex(i);
		}
		return false;
	}

	typedef tuple<int, int, T> E;
	T max_weighted_general_match(int x, const vector<E> &edges)
	{
		n = m = x;
		memset(ed + 1, 0, m * sizeof ed[0]);
		memset(lk + 1, 0, m * sizeof lk[0]);
		id = 0;
		iota(st + 1, st + n + 1, 1);
		int i, j;
		T wm = 0;
		T r = 0;
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				e[i][j] = {i, j, 0};
		for (auto [u, v, w] : edges) {
			e[v][u].w = e[u][v].w = max(e[u][v].w, w);
			wm = max(wm, w);
		}
		for (i = 1; i <= n; i++)
			p[i].clear();
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				b[i][j] = i * (i == j);
		fill_n(lab + 1, n, wm);
		while (bfs())
			;
		for (i = 1; i <= n; i++)
			if (lk[i])
				r += e[i][lk[i]].w;
		return r / 2;
	}
};

weighted_blossom_tree<long long, 400> wbt;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<tuple<int, int, long long>> edges(m);
	for (auto &[u, v, w] : edges)
		cin >> u >> v >> w;
	cout << wbt.max_weighted_general_match(n, edges) << '\n';
	for (int i = 1; i <= n; i++)
		cout << wbt.lk[i] << " \n"[i == n]; // 匹配
}