零碎知识点

板子

---

离散化

// T 类型在 unique 函数中需重载 == 运算符
// 在 lower_bound 函数中需重载 < 运算符
struct T {};
bool operator<(const T &a, const T &b);
bool operator==(const T &a, const T &b);
vector<T> sand;
sand.clear();
sort(sand.begin(), sand.end());
sand.erase(unique(sand.begin(), sand.end()), sand.end());
x = lower_bound(sand.begin(), sand.end(), T()) - sand.begin();

输出 __int128

ostream& operator<<(ostream &out, LL x) {
    if (x == 0) {
        return out << "0";
    }
    if(x < 0) {
        out << "-";
        x = -x;
    }
    static int sta[100];
    int top = 0;
    memset(sta, 0, sizeof(sta));
    while(x != 0) {
        sta[top++] = x % 10;
        x /= 10;
    }
    for(int i = top - 1; i >= 0; --i) {
        out << sta[i];
    }
    return out;
}

bitset 用法

函数	功能
b.any()	b 中是否存在1
b.count()	b 中1的个数
b.size()	b 的二进制位个数
b[pos]	b 在pos 处的二进制位（从低到高）
b.reset()	b 的所有二进制位都置零
b.to_ulong()	返回b 的unsigned long 值
~b	b 按位取反
b1 | b2	按位或
b1 & b2	按位与
b << n (b >> n)	b 按位左移（右移）n位

Pólya定理：

$$M=\frac{1}{|n|}\sum_{i=1}^nm^{c(\sigma_i)}$$
n 表示能够循环的个数，m表示需要涂色的点的数量，一般情况下， $c(\sigma_i)=\gcd(i,n)$

Lindstrom Gessel Vienot lemma 定理

对于一张给定的 $DAG$ 图，给定 $n$ 个起点和 $n$ 个终点，如果从起点 $a_i$ 到终点 $b_j$ 的路径数为 $e(a_i,b_j)$，则从任意一个起点到任意一个终点的两条路径不相交的方案数为行列式：

$$\begin{vmatrix} e(a_1,b_1)&e(a_1,b_2)&\cdots&e(a_1,b_n)\\ e(a_2,b_1)&e(a_2,b_2)&\cdots&e(a_2,b_n)\\ \vdots&\vdots&\ddots&\vdots\\ e(a_n,b_1)&e(a_n,b_2)&\cdots&e(a_n,b_n) \end{vmatrix}$$
的值。

分割字符串

void split(string str, string spacer, vector<string> &ret) {
    int pos1, pos2;
    int len = spacer.length();
    pos1 = 0;
    pos2 = str.find(spacer);
    while (pos2 != string::npos) {
        ret.push_back(str.substr(pos1, pos2 - pos1));
        pos1 = pos2 + len;
        pos2 = str.find(spacer, pos1);
    }
    if (pos1 != str.length()) {
        ret.push_back(str.substr(pos1));
    }
}

int 转 string

string intToString(LL x) {
    string str;
    if (x == 0) {
        return "0";
    }
    while (x != 0) {
        str.push_back(x % 10 + '0');
        x /= 10;
    }
    return reverse(str.begin(), str.end());
    return str;
}