笔记汇总

二项式定理是牛顿的早期成就之一，分析的是仅次于单项式的 最简单多项式。

即，$(a+b)^n = \sum_{r=0}^{n}C^r_na^{n-r}b^r$

如果说 $a^{n-r}$ 与 $b^r$ 是不证自明的结论，前面的组合数却让牛顿费了番工夫。

可以比较简单的巧记为在 $n$ 个数对中选 $n-r$ 个第一元素和 $r$ 个第二元素的组合

因为其中一个是相对的补集，可以省略，故为在 $n$ 个数中选 $n-r$ 个数的组合。

但是，艾萨克牛顿爵士绝不会仅满足于总结前人的经验，作为当时最顶尖的数学家（尽管只有二十多岁），他敏锐的发现二项式定理可以推广到任意实数位。

分数次幂即，$a^{\frac{1}{2}} = \sqrt{a}$

这也叫 广义二项式定理

广义二项式定理

首先我们会发现组合数并没有分数的形式（不然会有恐怖的位数），

这也意味着我们将展开一个无限级数，$\frac{a(a-1)…(a-b+1)}{b!}$，其中 $a$ 为指数，$b$ 无限。

当然无限级数是不一定收敛的，所以广义二项式未必有答案。

而广义二项式最大的作用就是快速收敛无理数，

列如 $\sqrt{7} = (9 - 2)^{\frac{1}{2}} = \frac{\frac{1}{2}(\frac{1}{2}-1)…(\frac{1}{2}-b+1)}{b!}$，此无限级数收敛速度远大于 $\sqrt{n}$，若要求小数点后 $n$ 位的 $\sqrt{7}$ 仅需要计算 $2n$ 项即可。

同样，负指数也满足这个公式。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 50;

int n;
int w[N];
unsigned f[N][N];
int root[N][N];

void dfs(int l, int r)
{
    if (l > r) return;

    int k = root[l][r];
    printf("%d ", k);
    dfs(l, k - 1);
    dfs(k + 1, r);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int len = 1; len <= n; len ++ )
        for (int l = 1; l + len - 1 <= n; l ++ )
        {
            int r = l + len - 1;

            for (int k = l; k <= r; k ++ )
            {
                int left = k == l ? 1 : f[l][k - 1];
                int right = k == r ? 1 : f[k + 1][r];
                int score = left * right + w[k];
                if (l == r) score = w[k];
                if (f[l][r] < score)
                {
                    f[l][r] = score;
                    root[l][r] = k;
                }
            }
        }

    printf("%d\n", f[1][n]);
    dfs(1, n);
    puts("");

    return 0;
}

树形结构区间dp题，注意，一个中序遍历可以构造很多棵树。

但由于是二叉树，对应区间DP左右端点的枚举，不需要拆分。

空结点值为 $1$，需要特判，同时，记得将父节点位置空出来。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 50;

int n;
int w[N];
unsigned f[N][N];
int root[N][N];

void dfs(int l, int r)
{
    if (l > r) return;

    int k = root[l][r];
    printf("%d ", k);
    dfs(l, k - 1);
    dfs(k + 1, r);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int len = 1; len <= n; len ++ )
        for (int l = 1; l + len - 1 <= n; l ++ )
        {
            int r = l + len - 1;

            for (int k = l; k <= r; k ++ )
            {
                int left = k == l ? 1 : f[l][k - 1];
                int right = k == r ? 1 : f[k + 1][r];
                int score = left * right + w[k];
                if (l == r) score = w[k];
                if (f[l][r] < score)
                {
                    f[l][r] = score;
                    root[l][r] = k;
                }
            }
        }

    printf("%d\n", f[1][n]);
    dfs(1, n);
    puts("");

    return 0;
}

求相似，用hash

多方向，得枚举

我们可以先找出所有星群，以及它们的群（按最小字典序保存）

用 hash 数组求其值（相似的），然后枚举，按出现顺序（用字典序）编号。

double get_dist(PII a, PII b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

double get_hash()
{
    double sum = 0;
    for (int i = 0; i < top; i ++ )
        for (int j = i + 1; j < top; j ++ )
            sum += get_dist(q[i], q[j]);    // hash 贡献值
    return sum;
}

// 可用最小表示法替换

static ：静态全局变量，清空数组用

字符 hash：前缀和思想，两参量为：

typedef unsigned long long ULL;

P = 131;

统计连通块：

dfs，参量：坐标，由上往下（递推式）记得判重。

bfs，参量：坐标，如上。

扩展——最小表示法：

双指针，解决循环同构问题

int get_min(char a[N], int n)
{
    static char b[N * 2];
    for(int i = 0; i < n; i ++)  b[i] = b[i + n] = a[i];    // 拆链法

    int i = 0, j = 1, k = 0;                            
    while(i < n and j < n)  // 枚举起点
    {
        for(k = 0; k < n and b[i + k] == b[j + k]; k ++);   // 找不同
        if(k == n)  break;          // 换一波起点
        if(b[i + k] > b[j + k]) {   // j 更优
            i += k + 1;             // i 后 p = [1,k] 位都不够优秀，因为j+p起在同构处之后，有更优字符
            if(i == j)  i ++;       // 错位法
        }
        else {
            j += k + 1;             
            if(i == j)  j ++;
        }
    }
    k = min(i, j);                  // i >= n ? j : i
    for(int i = 0; i < n; i ++)  a[i] = b[k + i];
    a[i + n] = 0;

    return k;
}

求相似，用hash

多方向，得枚举

我们可以先找出所有星群，以及它们的群（按最小字典序保存）

用 hash 数组求其值（相似的），然后枚举，按出现顺序（用字典序）编号。

double get_dist(PII a, PII b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

double get_hash()
{
    double sum = 0;
    for (int i = 0; i < top; i ++ )
        for (int j = i + 1; j < top; j ++ )
            sum += get_dist(q[i], q[j]);    // hash 贡献值
    return sum;
}

// 可用最小表示法替换

static ：静态全局变量，清空数组用

字符 hash：前缀和思想，两参量为：

typedef unsigned long long ULL;

P = 131;

统计连通块：

dfs，参量：坐标，由上往下（递推式）记得判重。

bfs，参量：坐标，如上。

扩展——最小表示法：

双指针，解决循环同构问题

int get_min(char a[N], int n)
{
    static char b[N * 2];
    for(int i = 0; i < n; i ++)  b[i] = b[i + n] = a[i];    // 拆链法

    int i = 0, j = 1, k = 0;                            
    while(i < n and j < n)  // 枚举起点
    {
        for(k = 0; k < n and b[i + k] == b[j + k]; k ++);   // 找不同
        if(k == n)  break;          // 换一波起点
        if(b[i + k] > b[j + k]) {   // j 更优
            i += k + 1;             // i 后 p = [1,k] 位都不够优秀，因为j+p起在同构处之后，有更优字符
            if(i == j)  i ++;       // 错位法
        }
        else {
            j += k + 1;             
            if(i == j)  j ++;
        }
    }
    k = min(i, j);                  // i >= n ? j : i
    for(int i = 0; i < n; i ++)  a[i] = b[k + i];
    a[i + n] = 0;

    return k;
}

笔记汇总

$AC$ 自动机是 以 Trie 的结构为基础，结合 KMP 的思想 建立的。

它最大的特点是在确保正确的情况下最快。

简单来说，建立一个 AC 自动机有两个步骤：

1. 基础的 Trie 结构：将所有的模式串构成一棵 Trie。
2. KMP 的思想：对 Trie 树上所有的结点构造失配指针。

然后就可以利用它进行 多模式串匹配 了。

失配指针

与$next$串的对比：

1. 共同点：两者同样是在失配的时候用于跳转的指针。
2. 不同点：next 指针求的是最长 Border（即最长的相同前后缀），而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。

即在失配后跳到其它分支上的与其真后缀相等的最长真前缀的末尾上。

或者说在不同模式串上的部分匹配表。

实现

建字典树

void insert(char *s) {
  int u = 0;
  for (int i = 1; s[i]; i++) {
    if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot;  // 如果没有则插入新节点
    u = tr[u][s[i] - 'a'];                              // 搜索下一个节点
  }
  e[u]++;  // 尾为节点 u 的串的个数
}

建失配指针

tr[u][c] 从u往后加一个字符c到达的结点

void build() {
  for (int i = 0; i < 26; i++)
    if (tr[0][i]) q.push(tr[0][i]); 
  while (q.size()) {    // bfs 更新确保前面阶段求出
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u][i])
        fail[tr[u][i]] = tr[fail[u]][i];
        // tr[u][i] 的失配指针等于其父节点的失配指针下沿（若有的话）的节点编号
        q.push(tr[u][i]);
      else
        tr[u][i] = tr[fail[u]][i];
        // 没有时快速返回，减少时间复杂度
    }
  }
}

多模式匹配

int query(char *t) {    // 搜索模式串的字符数组
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {  // 非空搜索
    u = tr[u][t[i] - 'a'];      // 往后走
    for (int j = u; j && e[j] != -1; j = fail[j]) { // 未走完且未重复走则统计出现过的模式串数量
      res += e[j], e[j] = -1;
    }
  }
  return res;
}

由于 $e$ 同时需要记录是否重复，所以我们在多次搜索时会新增一个 $copy$ 数组。

扩展

T1

输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。

查询路径有单向路径搜索算法，时间复杂度 $O(n)$。

但字符串是连续的，所以用 $hash$ 也可以，时间复杂度 $O(1)$。

对比:

int query(char *t) {    // 搜索模式串的字符数组
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {  // 非空搜索
    u = tr[u][t[i] - 'a'];      // 往后走
    for (int j = u; j && e[j] != -1; j = fail[j]) { // 未走完且未重复走则统计出现过的模式串数量
      res += e[j], e[j] = -1;
    }
  }
  return res;
}

// 以 u 为结尾的字符串编号为 idx[u]

int query(char *t) {  // 返回最大的出现次数
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u][t[i] - 'a'];
    for (int j = u; j; j = fail[j]) val[j]++;
    // 可以重复走，不用 e 数组
  }
  for (int i = 0; i <= tot; i++)    // 搜索所有节点, 但只用看字符串的末尾结点（的编号）
    if (idx[i]) res = max(res, val[i]), cnt[idx[i]] = val[i]; // 最优化更新, 维护 cnt 以便于输出出现次数相同的字符串
  return res;   // 出现次数
}

一棵用边来表示字母，插入时动态开点的树（降低时间复杂度），

它可以用较少的空间储存字符串，且查询效率较高，同时维护了字符串的前后缀。

KMP 是可以在文本串$s$中快速查找模式串$p$的一种算法。

部分匹配表

$pmt[i]$ 就是，从 $p[0]$ 往后数、同时从 $p[i]$ 往前数相同的位数，在保证前后缀相同的情况下，最多能数多少位。（但要 小于 $p$的长度）

线性规划题，真前缀后缀的前缀和都往后添加。

故而可以用前缀去匹配后缀。

此过程还可以顺带求出前面的部分匹配表，即失配后往前移动模式串到未失配且最优时，

正确且复杂度为 $O(2n)$

匹配

若失配，则直到模式串成功匹配或移到头时继续。

因为每当 $j$ 往后移了，则之后 $i$ 必定往后移动（部分决定 $j$ 到底可以往前移几位），

算法正确，且时间复杂度为 $O(2n)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
struct Data
{
    int a, b, c, s, res;    // s 是单点的贡献(即所有重复数据)

    bool operator< (const Data& t) const
    {
        if (a != t.a) return a < t.a;
        if (b != t.b) return b < t.b;
        return c < t.c;
    }
    bool operator== (const Data& t) const
    {
        return a == t.a && b == t.b && c == t.c;
    }
}q[N], w[N];
int tr[M], ans[N];  // 可以用权值线段树替换

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int v)
{
    for (int i = x; i < M; i += lowbit(i)) tr[i] += v;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

// 归并排序
void merge_sort(int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);

    // 双指针统计区间合并时的贡献
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)  // 边界
        if (q[i].b <= q[j].b) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
        else q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
    // q[i].b > q[j].b,仅当 q[i].a < q[j].a,则统计此时贡献
    while (i <= mid) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
    // i 余下的仍然要加入树,以便于后面清空树状数组
    while (j <= r) q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
    // 统计贡献,此时都是满足的
    for (i = l; i <= mid; i ++ ) add(q[i].c, -q[i].s);  // 清空树状数组
    for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        q[i] = {a, b, c, 1};
    }
    sort(q, q + n);

    int k = 1;
    for (int i = 1; i < n; i ++ )
        if (q[i] == q[k - 1]) q[k - 1].s ++ ;
        else q[k ++ ] = q[i];

    merge_sort(0, k - 1);
    for (int i = 0; i < k; i ++ )
        ans[q[i].res + q[i].s - 1] += q[i].s;

    for (int i = 0; i < n; i ++ ) printf("%d\n", ans[i]);

    return 0;
}