博客

CFGYM102394A CCPC2019哈尔滨A Artful Paintings

一眼看过去是差分约束板子题，实际上也就是差分约束板子题。

首先这个题可以对答案进行二分。如果铺x个可行，那么x+1个显然可行，所以我们先二分确定一个x。

然后我们的题目转变成了，能不能在恰好铺x个的情况下构造一组合法方案，根据最短路的松弛条件可知，不等式$x_a+v\leq x_b$等价于从a到b，边权为$-v$的边（最短路存在时，令$x_a$表示源点到a的距离，$x_b$同理，那么$x_a$和$x_b$在作为未知变量的时候一定是满足上述不等式的。）

所以我们可以得到，需要建立以下六种不等式：

1. $x_{n-1}+0\leq x_n$(前缀和不减)

2. $x_n+(-1)\leq x_{n-1}$前缀和要么加1要么不变

3. $x_{l-1}+x\leq x_r$ 区间染色数下限

4. $x_r +(x-M) \leq x_{l-1}$ 区间外染色数下限

5. $x_0+M\leq x_n$ 一共至少染M个

6. $x_n+(-M)\leq x_0$ 一共至多染M个(与5一起保证恰好染M个)

然后据此建边，其中$M$是我们二分的铺的个数。建出来的图跑一个从n到0的最短路，如果最短路存在（即没有负环），那说明M可行，答案可以考虑进一步缩小。如果存在负环，则说明M不可行。

但是这里的SPFA要注意优化，大概需要一个SLF（Small Label First），即如果待入队节点的已知最短距离小于队列头部节点，则把他扔到队列头部。

然后别用long long，跑的有点慢。

#include <algorithm>
#include <deque>
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

using int_t = int;

/*
1. x_{n-1}+0<=x_n(前缀和不减)
2. x_n+(-1)<=x_{n-1}前缀和要么加1要么不变
3. x_{l-1}+x<=x_r 区间染色数下限
4. x_r +(x-M) <= x_{l-1} 区间外染色数下限
5. x_0+M<=x_n 一共至少染M个
6. x_n+(-M)<=x_0 一共至多染M个(与5一起保证恰好染M个)

*/

const int_t LARGE = 3010;
const int_t INF = 0x3fffffff;
int_t dis[LARGE + 1];
int_t inqN[LARGE];
bool inqueue[LARGE + 1];
struct Edge {
    int_t to, weight;
    Edge(int_t v, int_t w) : to(v), weight(w) {}
};
struct Limitation {
    int_t left, right, val;
} cond1[LARGE + 1], cond2[LARGE + 1];

int_t n, m1, m2;
//不等式A+X<=B变为边(A,B)，长度-X
std::vector<Edge> graph[LARGE + 1];

void clear() {
    std::fill(dis, dis + 1 + n, INF);
    std::fill(inqueue, inqueue + 1 + n, false);
    std::fill(inqN, inqN + 1 + n, 0);
    for (int_t i = 0; i <= n; i++)
        graph[i].clear();
}

void pushEdge(int_t u, int_t v, int_t w) {
#ifdef DEBUG
    cout << "edge " << u << " to " << v << " val " << w << endl;
#endif
    graph[u].push_back(Edge(v, w));
}
//添加不等式x_a+v<=x_b
void pushLEQ(int_t a, int_t b, int_t v) {
#ifdef DEBUG
    cout << "cond x_" << a << " + " << v << " <= x_" << b << endl;
#endif
    pushEdge(b, a, -v);
}

bool SPFA(int_t src, int_t target) {
    std::deque<int_t> queue;
    dis[src] = 0;
    inqueue[src] = true;
    queue.push_back(src);
    while (!queue.empty()) {
        int_t front = queue.front();
        queue.pop_front();
        inqueue[front] = false;
        inqN[front]++;
        if (inqN[front] > n)
            return false;
        for (const auto& edge : graph[front]) {
            if (dis[edge.to] > dis[front] + edge.weight) {
                dis[edge.to] = dis[front] + edge.weight;
#ifdef DEBUG
                cout << "dis " << edge.to << " to " << dis[edge.to] << endl;
#endif
                if (!inqueue[edge.to]) {
                    if (!queue.empty() && dis[edge.to] < dis[queue.front()])
                        queue.push_front(edge.to);
                    else
                        queue.push_back(edge.to);
                    inqueue[edge.to] = true;
                }
            }
        }
    }
    return true;
}

bool check(int_t x) {
#ifdef DEBUG
    cout << "checking " << x << endl;
#endif
    clear();
    for (int_t i = 1; i <= n; i++) {
        pushLEQ(i - 1, i, 0);
    }
    for (int_t i = 1; i <= n; i++) {
        pushLEQ(i, i - 1, -1);
    }
    for (int_t i = 1; i <= m1; i++) {
        const auto& ref = cond1[i];
        pushLEQ(ref.left - 1, ref.right, ref.val);
    }
    for (int_t i = 1; i <= m2; i++) {
        const auto& ref = cond2[i];
        pushLEQ(ref.right, ref.left - 1, ref.val - x);
    }
    pushLEQ(0, n, x);
    pushLEQ(n, 0, -x);
    auto ret = SPFA(n, 0);
#ifdef DEBUG
    cout << "check " << x << " = " << ret << endl;
#endif
    return ret;
}

int main() {
    std::ios::sync_with_stdio(false);
    int_t T;
    cin >> T;
    while (T--) {
        cin >> n >> m1 >> m2;
        for (int_t i = 1; i <= m1; i++) {
            auto& ref = cond1[i];
            cin >> ref.left >> ref.right >> ref.val;
        }
        for (int_t i = 1; i <= m2; i++) {
            auto& ref = cond2[i];
            cin >> ref.left >> ref.right >> ref.val;
        }
        int_t left = 0, right = n;
        int_t result = INF;
        while (left + 1 < right) {
            int_t mid = (left + right) / 2;
            if (check(mid)) {
                result = std::min(result, mid);
                right = mid - 1;
            } else
                left = mid + 1;
        }
        for (int_t i = left; i <= right; i++)
            if (check(i))
                result = std::min(result, i);
        cout << result << endl;
    }

    return 0;
}

2021年4月19日

CFGYM101982F (2018 ICPC Pacific Northwest Regional Contest – Rectangles)

题意：给定n(1e5)个矩形，边与坐标轴平行，四个点的坐标都是整数(1e9级别)，问被矩形覆盖了奇数次的面积和。

首先把所有的矩形拆成上边和下边两条边，这样我们就得到了若干条与x轴平行的线段。然后我们把这些线段按照y坐标从小到大排个序。

现在我们维护一棵线段树，下标表示的是（离散化后的）整个横轴的覆盖情况。以及为了方便起见，整个线段树上所表示的区间都是左闭右开的（一条线段所能表示的实际长度是右端点减左端点）。

现在我们按照y坐标从小到大枚举每一条横线，对于一条横线，我们把它在线段树上所覆盖的的区域异或上1，同时面积取反（即用线段长度减掉区域内被标记过的线段长度和，此操作即为异或），由于我们存储的都是左闭右开区间，所以直接用右端点对应的数减掉左端点对应的数即可。

最后每插入一条线段，我们就查一下现在线段树上被覆盖的区间长度，然后乘上下一条线段的高度减掉当前线段的高度（此方法是可以正常处理有相同高度的线段的，因为他们高度相同，所以算出来都是0）。

#include <algorithm>
#include <iostream>
#include <vector>

using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;

struct Segment {
    int_t left, right, height;
};
struct Node {
    Node *left = nullptr, *right = nullptr;
    int_t begin, end;
    bool flag = false;
    int_t sum = 0;
    const std::vector<int_t>& vals;
    Node(int_t begin, int_t end, const std::vector<int_t>& vals)
        : begin(begin), end(end), vals(vals) {}
    void swap() {
        flag ^= 1;
        sum = vals[end] - vals[begin] - sum;
    }
    void pushdown() {
        if (flag) {
            left->swap();
            right->swap();
            flag = 0;
        }
    }
    void maintain() { sum = left->sum + right->sum; }
    void insert(int_t begin, int_t end) {  //插入一条线段
#ifdef DEBUG
        cout << "insert " << begin << "," << end << " to " << this->begin << ","
             << this->end << endl;
#endif
        if (this->begin >= begin && this->end <= end) {
            this->swap();
            return;
        }
        if (this->begin >= end || this->end <= begin) {
            return;
        }
        int_t mid0 = (this->begin + this->end) / 2;
        pushdown();
        left->insert(begin, end);
        right->insert(begin, end);
        maintain();
    }
};
Node* build(int_t begin, int_t end, const std::vector<int_t>& vals) {
    Node* node = new Node(begin, end, vals);
    if (begin + 1 != end) {
        int_t mid = (begin + end) / 2;
        node->left = build(begin, mid, vals);
        node->right = build(mid, end, vals);
    }
    return node;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::vector<Segment> segs;
    std::vector<int_t> nums;
    int_t n;
    cin >> n;
    for (int_t i = 1; i <= n; i++) {
        int_t x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        segs.push_back(Segment{x1, x2, y1});
        segs.push_back(Segment{x1, x2, y2});
        nums.push_back(x1);
        nums.push_back(x2);
    }
    std::sort(nums.begin(), nums.end());
    nums.resize(std::unique(nums.begin(), nums.end()) - nums.begin());

    std::sort(segs.begin(), segs.end(), [](const Segment& a, const Segment& b) {
        return a.height < b.height;
    });
    int_t result = 0;
    Node* root = build(0, nums.size() - 1, nums);
    const auto rank = [&](int_t x) {
        return std::lower_bound(nums.begin(), nums.end(), x) - nums.begin();
    };
#ifdef DEBUG
    for (const auto& s : segs) {
        cout << "seg " << s.left << " " << s.right << " " << s.height << endl;
    }
#endif
    for (int_t i = 0; i < segs.size() - 1; i++) {
        //先插入后统计结果
        const auto& curr = segs[i];
        root->insert(rank(curr.left), rank(curr.right));
        result += (segs[i + 1].height - curr.height) * root->sum;
    }
    cout << result << endl;
    return 0;
}

2021年3月11日

CFGYM 102823 CCPC2018 桂林 B题 Array Modify

题倒是还行，达标找规律找出来结论，然后就想到了一个多项式快速幂的做法。

一开始写的两个log的快速幂，TLE。

然后尝试改成exp+log，跑得看起来快了，但是遇到多组数据（n的大小递增的时候）就挂掉了？

仔细调查后发现源于自己一直以来exp函数内一直存在的错误：

exp内调用了log，log内调用了inv，exp内给G0（用以存储log返回值的数组）预留了upper2n(2*n)的空间，但是inv内却使用了upper2n(3*n+1)的空间！

（调试方法：数组切换为动态分配并开启内存检查）

对于只计算exp一次而言，这个错误不会造成影响，但是计算多次的时候由于空间污染会导致错误结果。

解决方法：在exp内也预留upper2n(3*n)的空间，通过本题。

另外小测试了一下，两个log的多项式快速幂跑本题极限数据，NTT变换的多项式总长度为“27262976”，而exp+log实现的快速幂，NTT变换的多项式总长度为 19922408，我原本以为因为常数原因，exp+log会跑得更慢，没想到事实并非如此。

// luogu-judger-enable-o2
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int mod = 998244353;
const int g = 3;
const int LARGE = 1 << 20;
int revs[21][LARGE + 1];

int power(int base, int index);
void transform(int* A, int len, int arg);
void poly_inv(const int* A, int n, int* result);
void poly_log(const int* A, int n, int* result);
void poly_exp(const int* A, int n, int* result);

std::vector transform_count;
#ifdef TDEBUG
#define TRANSFORM_DEBUG(n) \
    { transform_count.push_back(n); }
#else
#define TRANSFORM_DEBUG(n)
#endif
int bitRev(int base, int size2) {
    int result = 0;
    for (int i = 1; i < size2; i++) {
        result |= (base & 1);
        base >>= 1;
        result <<= 1;
    }
    result |= (base & 1);
    return result;
}
int upper2n(int x) {
    int result = 1;
    while (result < x)
        result *= 2;
    return result;
}
int main() {
    std::ios::sync_with_stdio(false);

    for (int i = 0; (1 << i) <= LARGE; i++) {
        for (int j = 0; j < LARGE; j++) {
            revs[i][j] = bitRev(j, i);
        }
    }
    static int F[LARGE + 1], G[LARGE + 1];
    static int arr[LARGE + 1];
    int T;
    cin >> T;
    for (int_t _i = 1; _i <= T; _i++) {
        memset(F, 0, sizeof(F));
        memset(G, 0, sizeof(G));
        memset(arr, 0, sizeof(arr));
        int_t n, L, m;
        cin >> n >> L >> m;

        for (int_t i = 1; i <= n; i++)
            cin >> arr[i];
        int size2 = upper2n(4 * (n + 1));
        for (int i = 0; i < size2; i++) {
            if (i < L)
                F[i] = 1;
            else
                F[i] = 0;
            G[i] = 0;
        }
#ifdef DEBUG
        cout << "init = " << endl;
        cout << "F = ";
        for (int_t i = 0; i < 2 * n; i++)
            cout << F[i] << " ";
        cout << endl;

        cout << "G = ";
        for (int_t i = 0; i < 2 * n; i++)
            cout << G[i] << " ";
        cout << endl;
#endif

        poly_log(F, n, G);
#ifdef DEBUG
        cout << "after log = " << endl;
        cout << "G = ";
        for (int_t i = 0; i < 2 * n; i++)
            cout << G[i] << " ";
        cout << endl;
#endif
        for (int i = 0; i < n; i++)
            G[i] = G[i] * m % mod;
        for (int i = 0; i < size2; i++)
            F[i] = 0;
#ifdef DEBUG
        cout << "before exp = " << endl;
        cout << "G = ";
        for (int_t i = 0; i < 2 * n; i++)
            cout << G[i] << " ";
        cout << endl;
#endif
        poly_exp(G, n, F);
#ifdef DEBUG
        cout << "after exp = " << endl;
        cout << "F = ";
        for (int_t i = 0; i < 2 * n; i++)
            cout << F[i] << " ";
        cout << endl;
#endif

        for (int i = 0; i < size2; i++) {
            if (i >= n)
                F[i] = 0;
            if (i >= n && i < 2 * n)
                G[i] = arr[i - n + 1];
            else
                G[i] = 0;
        }
        std::reverse(G + n, G + 2 * n);

#ifdef DEBUG
        cout << "F = ";
        for (int_t i = 0; i < 2 * n; i++)
            cout << F[i] << " ";
        cout << endl;

        cout << "G = ";
        for (int_t i = 0; i < 2 * n; i++)
            cout << G[i] << " ";
        cout << endl;
#endif

        transform(F, size2, 1);
        transform(G, size2, 1);
        for (int i = 0; i < size2; i++)
            F[i] = (int_t)F[i] * G[i] % mod;
        transform(F, size2, -1);
        int inv = power(size2, -1);
        std::reverse(F + n, F + 2 * n);
        cout << "Case " << _i << ": ";

        for (int i = n; i < 2 * n; i++) {
            cout << (int_t)F[i] * inv % mod << " ";
        }
        cout << endl;
#ifdef DEBUG
        for (int i = 0; i < n; i++) {
            cout << "F " << i << " = " << F[i] << endl;
        }
#endif
#ifdef TDEBUG
        for (auto x : transform_count) {
            cout << x << " ";
        }
        cout << endl;
#endif
    }
    return 0;
}

int power(int base, int index) {
    const int phi = mod - 1;
    index = (index % phi + phi) % phi;
    base = (base % mod + mod) % mod;
    int result = 1;
    while (index) {
        if (index & 1)
            result = (int_t)result * base % mod;
        base = (int_t)base * base % mod;
        index >>= 1;
    }
    return result;
}
void transform(int* A, int len, int arg) {
    TRANSFORM_DEBUG(len);
    int size2 = int(log2(len) + 0.5);
    for (int i = 0; i < len; i++) {
        int x = revs[size2][i];
        if (x > i)
            std::swap(A[i], A[x]);
    }
    for (int i = 2; i <= len; i *= 2) {
        int mr = power(g, (int_t)arg * (mod - 1) / i);
        for (int j = 0; j < len; j += i) {
            int curr = 1;
            for (int k = 0; k < i / 2; k++) {
                int u = A[j + k];
                int t = (int_t)A[j + k + i / 2] * curr % mod;
                A[j + k] = (u + t) % mod;
                A[j + k + i / 2] = (u - t + mod) % mod;
                curr = (int_t)curr * mr % mod;
            }
        }
    }
}
//计算多项式A在模x^n下的逆元
// C(x)<-2B(x)-A(x)B^2(x)
void poly_inv(const int* A, int n, int* result) {
    if (n == 1) {
        result[0] = power(A[0], -1);
        return;
    }
    poly_inv(A, n / 2 + n % 2, result);
    static int temp[LARGE + 1];
    int size2 = upper2n(3 * n + 1);
    for (int i = 0; i < size2; i++) {
        if (i < n)
            temp[i] = A[i];
        else
            temp[i] = 0;
    }
    transform(temp, size2, 1);
    transform(result, size2, 1);
    for (int i = 0; i < size2; i++) {
        result[i] =
            ((int_t)2 * result[i] % mod -
             (int_t)temp[i] * result[i] % mod * result[i] % mod + 2 * mod) %
            mod;
    }
    transform(result, size2, -1);
    for (int i = 0; i < size2; i++) {
        if (i < n) {
            result[i] = (int_t)result[i] * power(size2, -1) % mod;
        } else {
            result[i] = 0;
        }
    }
}
void poly_log(const int* A, int n, int* result) {
    int size2 = upper2n(3 * n + 1);
    static int Ad[LARGE + 1];
    for (int i = 0; i < size2; i++) {
        if (i < n) {
            Ad[i] = (int_t)(i + 1) * A[i + 1] % mod;
        } else {
            Ad[i] = 0;
        }
        result[i] = 0;
    }
    transform(Ad, size2, 1);
    poly_inv(A, n, result);
    transform(result, size2, 1);
    for (int i = 0; i < size2; i++) {
        result[i] = (int_t)result[i] * Ad[i] % mod;
    }
    transform(result, size2, -1);
    for (int i = 0; i < size2; i++)
        if (i < n)
            result[i] = (int_t)result[i] * power(size2, -1) % mod;
        else
            result[i] = 0;
    for (int i = n - 1; i >= 1; i--) {
        result[i] = (int_t)result[i - 1] * power(i, -1) % mod;
    }
    result[0] = 0;
}
void poly_exp(const int* A, int n, int* result) {
    if (n == 1) {
        assert(A[0] == 0);
        result[0] = 1;
        return;
    }
    poly_exp(A, n / 2 + n % 2, result);
    static int Ax[LARGE + 1];
    // memset(G0, 0, sizeof(G0));
    // memset(Ax,0,sizeof(Ax));
    int size2 = upper2n(3 * n + 1);
    // int* G0 = new int[size2];
    static int G0[LARGE + 1];
    for (int_t i = 0; i < size2; i++) {
        if (i < n)
            Ax[i] = A[i];
        else
            Ax[i] = 0;
        G0[i] = 0;
    }
    poly_log(result, n, G0);

    transform(Ax, size2, 1);
    transform(G0, size2, 1);
    transform(result, size2, 1);
    for (int i = 0; i < size2; i++)
        result[i] =
            (result[i] - (int_t)result[i] * (G0[i] - Ax[i] + mod) % mod + mod) %
            mod;
    transform(result, size2, -1);
    for (int i = 0; i < size2; i++)
        if (i < n)
            result[i] = (int_t)result[i] * power(size2, -1) % mod;
        else
            result[i] = 0;
    // delete[] G0;
}

2021年3月4日

如何在Python里解引用指针？
之前在知乎上看到有人说Python可以这么做，于是查了一顿资料后在sof上找到了做法

https://stackoverflow.com/questions/3106689/pointers-in-python
```
import gc
from ctypes import cast, py_object
a = [1, 2, 3]
b = cast(id(a), py_object).value
print(a is b) # True
```
2021年2月8日
如何从正在跑着的nginx里读到它正在使用的配置文件内容
来源：在nginx跑着的时候手贱把配置文件盖了，我想既然nginx既没重启也没重新读配置，所以肯定有什么办法dump出来当前正在用的配置文件。

然后搜了下搜到一个直接用gdb读内存的法子，来源https://serverfault.com/questions/361421/dump-nginx-config-from-running-process
```
# Set pid of nginx master process here
pid=8192

# generate gdb commands from the process's memory mappings using awk
cat /proc/$pid/maps | awk '$6 !~ "^/" {split ($1,addrs,"-"); print "dump memory mem_" addrs[1] " 0x" addrs[1] " 0x" addrs[2] ;}END{print "quit"}' > gdb-commands

# use gdb with the -x option to dump these memory regions to mem_* files
gdb -p $pid -x gdb-commands

# look for some (any) nginx.conf text
grep worker_connections mem_*
grep server_name mem_*
```
改一下pid为主进程的pid即可，然后退出gdb，去mem_*文件里搜配置文件的关键字。
2021年1月27日

CF1009F Dominant Indices 长剖入门题复习

复习长链剖分。

首先划分长链，走到每个长链顶就给这个长链开个数组拿来记答案，数组的长度（从0开始算）是整个长链上点的个数，下标为k的位置所表示的意义是到长链顶距离为k的点的个数，沿着重链走的时候，直接指针偏移一位就行了（毕竟状态在深度上连续）。

然后DFS，走到每一个点，先给这个点的DP数组指针（设为arr），下标为0的位置加个1，表示这个点自己的答案。然后如果这个点有重子节点，就先沿着重子节点走，走的时候DP数组直接偏移上1，然后这个点的答案先记录为重子节点的答案+1（我们要考虑所有子节点的答案，一会拿这玩意来更新）。

对于非重子节点的点，开个新的DP数组，然后直接传下去往下递归。

非重子节点返回后尝试更新答案。枚举非重子节点DP数组上的每一个状态，把他的值加到当前节点的DP值上（即合并子链状态，把状态合并到重链上），然后顺带更新一波结果（如果某个深度的值出现的比当前的多，就直接更新，如果相当就比一下深度），合并晚状态后直接把非重子节点的内存回收掉即可。

显然复杂度是$\theta(n)$的，每条重链会有一个DP数组，这个DP数组的长度是重链的长度，每条重链的答案只会被合并一次，而所有重链的长度之和是$n$。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using int_t = long long int;

const int_t LARGE = 1e6;

using std::cin;
using std::cout;
using std::endl;

int_t results[LARGE + 1];

int_t depth[LARGE + 1];
int_t maxDepth[LARGE + 1];
int_t maxChd[LARGE + 1];

std::vector<int_t> graph[LARGE + 1];
int_t n;

void DFS1(int_t vtx, int_t from = -1) {
    maxChd[vtx] = -1;
    maxDepth[vtx] = depth[vtx];
    for (auto to : graph[vtx])
        if (to != from) {
            depth[to] = depth[vtx] + 1;
            DFS1(to, vtx);
            if (maxChd[vtx] == -1 || maxDepth[to] > maxDepth[maxChd[vtx]]) {
                maxChd[vtx] = to;
            }
            maxDepth[vtx] = std::max(maxDepth[vtx], maxDepth[to]);
        }
}
// arr 距离为x的点的个数
void DFS2(int_t vtx, int_t from = -1, int_t* arr = nullptr) {
    arr[0]++;
    auto& result = results[vtx];
    if (maxChd[vtx] != -1) {
        DFS2(maxChd[vtx], vtx, arr + 1);
        result = results[maxChd[vtx]] + 1;  //答案初始值
    }
    for (auto to : graph[vtx])
        if (to != from && to != maxChd[vtx]) {
            int_t arrlen = maxDepth[to] - depth[vtx] + 1;
            int_t* next = new int_t[arrlen];
            std::fill(next, next + arrlen, 0);
            // next[0] = 1;
            DFS2(to, vtx, next + 1);
            for (int_t i = 1; i < arrlen; i++) {
                arr[i] += next[i];
                if (arr[i] > arr[result])
                    result = i;
                else if (arr[i] == arr[result] && i < result)
                    result = i;
            }
            delete[] next;
        }
    if (arr[result] == 1)
        result = 0;  //最小的距离
}
int main() {
    std::ios::sync_with_stdio(false);
    cin >> n;
    for (int_t i = 1; i <= n - 1; i++) {
        int_t u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    depth[1] = 1;
    DFS1(1);
#ifdef DEBUG

    for (int_t i = 1; i <= n; i++) {
        cout << "maxchd " << i << " = " << maxChd[i] << endl;
    }
#endif
    static int_t arr[LARGE + 1];
    DFS2(1, -1, arr);
    for (int_t i = 1; i <= n; i++) {
        cout << results[i] << endl;
    }

    return 0;
}

2020年11月19日

CCPC2019 秦皇岛 A Angle Beats

傻逼HDU

原题内存1G，贵题内存128M，真的nb

傻逼题，先对于一个点i，枚举所有点j，然后计算i和j构成的直线的斜率，记在i的map里（即对于每个点i，统计i作为线段一个端点的情况下，不同的斜率取值所对应的点的个数）

然后对于每个询问，分$A_i$是直角端点和非直角端点的情况讨论。

$A_i$是直角端点的情况下，枚举下n个点，算出来斜率的取值情况然后存起来。然后再枚举一个点，钦定这是第一条直角边，然后算出来另一条直角边的斜率，去刚刚存的map里反查有多少种情况，最后除个2（一种情况会被算两次）

$A_i$不是直角端点的情况下，枚举一个点，连起来构成一条直角边，然后算一下另一条直角边的斜率，然后去一开始预处理的数组里去查下能有多少种即可。（这个不需要除2，因为不会算重）

如何存斜率？别用浮点数，写个有理数类。如何记斜率不存在？分母写0，分子写1（分子不要写别的数，不方便统计）。如何记斜率为0？分子写1，分母写0。

另外为了统计方便，我们所存储的有理数均为最简分数，并且正负号全都在分子上（0和不存在除外，这时不需要考虑符号）

要做直接去CF交吧，HDU太傻逼了。

要用unordered_map并且自己写个hasher，map太慢了。

https://codeforces.com/gym/102361/problem/A

#include <assert.h>
#include <functional>
#include <iostream>
#include <map>
#include <unordered_map>
using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;

int_t gcd(int_t a, int_t b) {
    a = std::abs(a);
    b = std::abs(b);
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

struct R {
    //有理数a/b
    int_t a = 0, b = 0;
    R simplify() const {
        int_t d = gcd(a, b);
        return R{a / d, b / d};
    }
    // R operator*(const R& rhs) const {
    //     if (b == 0 || rhs.b == 0)
    //         return R{1, 0};
    //     return R{a * rhs.a, b * rhs.b}.simplify();
    // }
    bool operator<(const R& rhs) const {
        return (long double)a / b < (long double)rhs.a / rhs.b;
    }
    bool operator==(const R& rhs) const { return a == rhs.a && b == rhs.b; }
    R(int_t a = 0, int_t b = 0) : a(a), b(b) {}
};

const auto my_hash = [](const R& x) -> size_t {
    return (((uint64_t)std::abs(x.a) << 31) | (uint64_t)std::abs(x.b)) %
           998244353;
};

struct my_hasher {
    size_t operator()(const R& x) const { return my_hash(x); }
};
//以某个点为一个端点的，斜率为R的点的个数
//无序点对
std::unordered_map<R, int, my_hasher> byS[2001];

struct P {
    int x, y;
} points[2001];
std::ostream& operator<<(std::ostream& os, const R& r) {
    os << "R{" << r.a << "," << r.b << "}";
    return os;
}
int n, q;
int main() {
    {
        (scanf("%d%d", &n, &q));
        // break;
        for (int i = 1; i <= n; i++) {
            auto& ref = points[i];
            scanf("%d%d", &ref.x, &ref.y);
            // byS[i].clear();
        }
        for (int i = 1; i <= n; i++) {
#ifdef DEBUG
            cout << "pnt " << i << " = " << points[i].x << " " << points[i].y
                 << endl;
#endif
            for (int j = 1; j <= n; j++) {
                if (i == j)
                    continue;
                int_t dy = points[j].y - points[i].y;
                int_t dx = points[j].x - points[i].x;
#ifdef DEBUG
                cout << "point " << i << " " << j << " dy = " << dy
                     << " dx = " << dx << endl;

#endif
                if (dx < 0) {
                    dy *= -1, dx *= -1;
                }
                int_t d = gcd(dy, dx);
                dy /= d, dx /= d;
                if (dx == 0)
                    dy = 1;
                else if (dy == 0)
                    dx = 1;
                byS[i][R{dy, dx}]++;
            }
        }

        while (q--) {
            int x, y;
            scanf("%d%d", &x, &y);
            int_t result = 0;
#ifdef DEBUG
            cout << "BEGIN " << x << " " << y << endl;
#endif
            //作为直角顶点 先预处理
            {
                int_t curr = 0;
                static std::unordered_map<R, int, my_hasher> byS;
                // for(int i=1;i<=n;i++) byS[i].clear();
                byS.clear();
                for (int i = 1; i <= n; i++) {
                    int_t dy = y - points[i].y;
                    int_t dx = x - points[i].x;
                    if (dx < 0) {
                        dy *= -1, dx *= -1;
                    }
                    int_t d = gcd(dy, dx);
                    dy /= d, dx /= d;
                    if (dx == 0)
                        dy = 1;
                    else if (dy == 0)
                        dx = 1;
                    byS[R{dy, dx}]++;
                }
#ifdef DEBUG
                for (const auto& kvp : byS) {
                    cout << kvp.first << " = " << kvp.second << endl;
                }
#endif

#ifdef DEBUG

                cout << "TYPE 2" << endl;
#endif
                //枚举一条直角边 然后根据斜率查另一条
                for (int i = 1; i <= n; i++) {
#ifdef DEBUG
                    cout << "FOR PNT " << i << endl;

#endif
                    int_t dy = y - points[i].y;
                    int_t dx = x - points[i].x;
                    dy *= -1;
                    if (dy < 0) {
                        dy *= -1, dx *= -1;
                    }
                    int_t d = gcd(dy, dx);
                    dy /= d, dx /= d;

                    R r0{dx, dy};
                    if (r0.b == 0) {
                        r0.a = 1;
                    } else if (r0.a == 0)
                        r0.b = 1;
                    if (byS.count(r0))
                        curr += byS[r0];
                }
#ifdef DEBUG
                cout << "type1 curr=" << curr << " div2 " << curr / 2 << endl;
#endif
                // assert(curr % 2 == 0);
                result += curr / 2;
            }
            //作为非直角顶点 枚举一个点，连上一条直角边，然后去查斜率
            {
                int_t curr = 0;
                for (int i = 1; i <= n; i++) {
                    int_t dy = y - points[i].y;
                    int_t dx = x - points[i].x;
                    dy *= -1;
                    if (dy < 0) {
                        dy *= -1, dx *= -1;
                    }
                    int_t d = gcd(dy, dx);
                    dx /= d, dy /= d;
                    R r0{dx, dy};
                    if (r0.b == 0)
                        r0.a = 1;
                    else if (r0.a == 0)
                        r0.b = 1;
                    if (byS[i].count(r0))
                        curr += byS[i][r0];
#ifdef DEBUG

                    cout << "type 2 at pnt " << i << " req r = " << r0
                         << " count " << byS[i][r0] << endl;
#endif
                }
                // assert(curr % 2 == 0);
#ifdef DEBUG
                cout << "type2 curr=" << curr << " div2 " << curr / 2 << endl;
#endif
                result += curr;
            }
            printf("%lld\n", result);
        }
    }
    return 0;
}

2020年10月17日

洛谷3327 约数个数和复习
众所周知，这题不是个人也会。

$$ \text{首先可知}d\left( nm \right) =\sum_{a|n}{\sum_{b|m}{\left[ \mathrm{gcd}\left( a,b \right) =1 \right]}} \\ \sum_{1\le i\le n}{\sum_{1\le j\le m}{\sum_{a|i}{\sum_{b|j}{\left[ \mathrm{gcd}\left( a,b \right) =1 \right]}}}} \\ =\sum_{1\le i\le n}{\sum_{1\le j\le m}{\sum_{a|i}{\sum_{b|j}{\sum_{k|gcd\left( a,b \right)}{\mu \left( k \right)}}}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le i\le n}{\sum_{1\le j\le m}{\sum_{a|i}{\sum_{b|j}{\left[ k|\mathrm{gcd}\left( a,b \right) \right]}}}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le a\le n}{\sum_{1\le b\le m}{\sum_{a|i,i\le n}{\sum_{b|j,j\le m}{\left[ k|gcd\left( a,b \right) \right]}}}}} \\ a\gets ak,b\gets bk \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le ak\le n}{\sum_{1\le bk\le m}{\left[ k|gcd\left( ak,bk \right) \right] \lfloor \frac{n}{ak} \rfloor \lfloor \frac{m}{bk} \rfloor}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le a\le \lfloor \frac{n}{k} \rfloor}{\sum_{1\le b\le \lfloor \frac{m}{k} \rfloor}{\lfloor \frac{n}{ak} \rfloor \lfloor \frac{m}{bk} \rfloor}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \sum_{1\le a\le \lfloor \frac{n}{k} \rfloor}{\sum_{1\le b\le \lfloor \frac{m}{k} \rfloor}{\lfloor \frac{\lfloor \frac{n}{k} \rfloor}{a} \rfloor \lfloor \frac{\lfloor \frac{m}{k} \rfloor}{b} \rfloor}}} \\ =\sum_{1\le k\le n}{\mu \left( k \right) \left( \sum_{1\le a\le \lfloor \frac{n}{k} \rfloor}{\lfloor \frac{\lfloor \frac{n}{k} \rfloor}{a} \rfloor} \right) \left( \sum_{1\le b\le \lfloor \frac{m}{k} \rfloor}{\lfloor \frac{\lfloor \frac{m}{k} \rfloor}{b} \rfloor} \right)} \\ S\left( n \right) =\sum_{1\le i\le n}{\lfloor \frac{n}{i} \rfloor} \\ \text{原式}=\sum_{1\le k\le n}{\mu \left( k \right) S\left( \lfloor \frac{n}{k} \rfloor \right) S\left( \lfloor \frac{m}{k} \rfloor \right)} \\ $$
```
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using int_t = long long int;

const int_t LARGE = 5e4;

using std::cin;
using std::cout;
using std::endl;

int_t S[LARGE + 1];
bool isPrime[LARGE + 1];
int_t factor[LARGE + 1];
int_t mu[LARGE + 1];
int_t muSum[LARGE + 1];

int_t Sx(int_t n) {
    int_t result = 0;
    int_t i = 1;
    while (i <= n) {
        int_t next = n / (n / i);
        result += (next - i + 1) * (n / i);
        i = next + 1;
    }
    return result;
}

int_t query(int_t n, int_t m) {
    if (n > m)
        std::swap(n, m);
    int_t result = 0;
    int_t i = 1;
    while (i <= n) {
        int_t next = std::min(n / (n / i), m / (m / i));
        result += (muSum[next] - muSum[i - 1]) * S[n / i] * S[m / i];
        i = next + 1;
    }
    return result;
}

int main() {
    for (int_t i = 1; i <= LARGE; i++) {
        S[i] = Sx(i);
    }
    memset(isPrime, 1, sizeof(isPrime));
    for (int_t i = 2; i <= LARGE; i++) {
        if (isPrime[i]) {
            factor[i] = i;
            for (int_t j = i * i; j <= LARGE; j += i) {
                isPrime[j] = false;
                if (!factor[j])
                    factor[j] = i;
            }
        }
    }
    mu[1] = muSum[1] = 1;
    for (int_t i = 2; i <= LARGE; i++) {
        int_t factor = ::factor[i];
        if (i / factor % factor == 0)
            mu[i] = 0;
        else
            mu[i] = mu[i / factor] * -1;
        muSum[i] = muSum[i - 1] + mu[i];
    }
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        auto result = query(n, m);
        printf("%lld\n", result);
    }
    return 0;
}
```
2020年10月10日

$$ \text{钦定}N\le M \\ \sum_{1\le i\le N}{\sum_{1\le j\le M}{\left[ \mathrm{gcd}\left( i,j \right) =p \right]}} \\ \sum_p{\sum_{1\le pi\le N}{\sum_{1\le pj\le M}{\left[ \mathrm{gcd}\left( pi,pj \right) =p \right]}}} \\ \sum_p{\sum_{1\le i\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le j\le \lfloor \frac{M}{p} \rfloor}{\left[ \mathrm{gcd}\left( i,j \right) =1 \right]}}} \\ \sum_p{\sum_{1\le i\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le j\le \lfloor \frac{M}{p} \rfloor}{\sum_{k|gcd\left( i,j \right)}{\mu \left( k \right)}}}} \\ \sum_p{\sum_{1\le k\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le ik\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le jk\le \lfloor \frac{M}{p} \rfloor}{\sum_{k|gcd\left( ik,jk \right)}{\mu \left( k \right)}}}}} \\ \sum_p{\sum_{1\le k\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le i\le \lfloor \frac{N}{kp} \rfloor}{\sum_{1\le j\le \lfloor \frac{M}{kp} \rfloor}{\mu \left( k \right)}}}} \\ \sum_{1\le p\le N,p\,\,is\,\,prime}{\sum_{1\le k\le \lfloor \frac{N}{p} \rfloor}{\mu \left( k \right) \lfloor \frac{N}{kp} \rfloor \lfloor \frac{M}{kp} \rfloor}} \\ T=kp \\ T\le N \\ \sum_{1\le T\le N}{\sum_{p|T\left( T\text{的所有质因数} \right)}{\lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor \mu \left( \frac{T}{p} \right)}} \\ =\sum_{1\le T\le N}{\lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor \sum_{p|T,\left( T\text{的所有质因数} \right)}{\mu \left( \frac{T}{p} \right)}} $$

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 2e7;

int f[LARGE + 1];
int fSum[LARGE + 1];
int mu[LARGE + 1];
int factor[LARGE + 1];
bool isPrime[LARGE + 1];

std::vector<int> primes;

int_t query(int_t n, int_t m) {
    if (n > m)
        std::swap(n, m);
#ifdef DEBUG
    cout << "process " << n << " " << m << endl;
#endif
    int_t i = 1;
    int_t result = 0;
    while (i <= n) {
        int_t next = std::min(n / (n / i), m / (m / i));
        result += (n / i) * (m / i) * (fSum[next] - fSum[i - 1]);
        i = next + 1;
    }
    return result;
}

int main() {
    std::ios::sync_with_stdio(false);
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[1] = false;
    for (int_t i = 2; i <= LARGE; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int_t j = i * i; j <= LARGE; j += i) {
                isPrime[j] = false;
                if (factor[j] == 0)
                    factor[j] = i;
            }
            factor[i] = i;
        }
    }
    mu[1] = 1;
    for (int_t i = 2; i <= LARGE; i++) {
        int_t factor = ::factor[i];
        if (i / factor % factor == 0) {
            mu[i] = 0;
        } else {
            mu[i] = mu[i / factor] * -1;
        }
    }
    for (auto prime : primes) {
        for (int_t j = 1; j * prime <= LARGE; j++) {
            f[j * prime] += mu[j];
        }
    }
#ifdef DEBUG
    for (int_t i = 2; i <= 100; i++) {
        cout << i << ": factor=" << factor[i] << " isPrime=" << isPrime[i]
             << " mu=" << mu[i] << " f=" << f[i] << endl;
    }

#endif
    for (int_t i = 2; i <= LARGE; i++)
        fSum[i] = fSum[i - 1] + f[i];
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        int_t result = query(n, m);
        printf("%lld\n", result);
    }
    return 0;
}<span id="mce_marker" data-mce-type="bookmark" data-mce-fragment="1"></span>

2020年10月10日

洛谷5357 AC自动机模板二次加强复习

简单复习了以下AC自动机。

首先注意，$$n$$个字符串构建的AC自动机至多可能有总串长+1个节点（根节点不隶属于任何一个字符串）

由fail指针构成的树叫做后缀链接树，每个点的父节点为这个点所表示的字符串，在整个ACAM里能匹配到的公共后缀最长的字符串。（与SAM里的后缀连接好像是一样的….）

构建后缀链接，并且把Trie树补成Trie图（即将每个点的不存在的子节点指向下一个待匹配位置的操作）通过BFS进行。

初始时：根节点的子节点的fail指针全都指向根，根节点的不存在的子节点构造关于根的自环。

接下来根节点的存在的子节点入队，开始BFS。

从队列里取出来队首元素V，按照如下方法操作：

遍历其子节点，设当前遍历到的子节点通过字符chr获得，如果这个子节点存在，则其后缀链接指向V的后缀链接指向的节点的chr子节点，并将该节点入队。

如果该子节点不存在，则将其替换为V的后缀链接的chr子节点。

如果遇到一个所有字符串都没出现的字符怎么办？这时我们肯定会走到根，然后沿着根节点的子节点走自环，成功滚到下一个字符。

匹配时直接沿着Trie图走即可（我们在BFS中已经把所有点的子节点补完了），每走到一个点，则说明了我们匹配到了根到这个点的边所构成的字符串。

然后怎么统计每个子串出现的次数呢？

首先我们在ACAM上的每个点标记上以这个点结尾的字符串，可以知道这种标记只会有总字符串个数个。

然后我们构建出后缀链接树，我们可以知道，当我们的字符串走到某个点的时候，就意味着匹配到了这个点在后缀链接树上到树根经历的所有字符串，然后我们打个到根的差分标记，最后DFS统计下标记即可求出来每个字符串访问了几遍。

#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

struct Node {
    Node* chd[26];
    Node* fail = nullptr;
    // std::vector<int_t> strs;
    std::vector<int_t> strs;
    int_t mark = 0;
    Node*& access(char x) { return chd[x - 'a']; }
    Node() { memset(chd, 0, sizeof(chd)); }
    int_t id;
};
std::vector<int_t> graph[int_t(2e5) + 10];

Node* mapping[int_t(2e5) + 10];
Node* root = new Node;
int_t used = 1;
void insert(const char* str, int_t id) {
    Node* curr = root;
    for (auto ptr = str; *ptr; ptr++) {
        auto& chd = curr->access(*ptr);
        if (chd == nullptr) {
            chd = new Node;
            chd->id = ++used;
            mapping[used] = chd;
        }
        curr = chd;
    }
    curr->strs.push_back(id);
}
void buildFail() {
    std::queue<Node*> queue;
    // 安排根节点的子节点
    for (auto& ref : root->chd) {
        if (ref) {
            ref->fail = root;
            queue.push(ref);
            graph[1].push_back(ref->id);
        } else {
            ref = root;
        }
    }
    while (!queue.empty()) {
        Node* front = queue.front();
        queue.pop();
        for (char chr = 'a'; chr <= 'z'; chr++) {
            auto& ptr = front->access(chr);
            if (ptr) {
                queue.push(ptr);
                ptr->fail = front->fail->access(chr);
                graph[ptr->fail->id].push_back(ptr->id);
#ifdef DEBUG
                cout << "edge " << ptr->fail->id << " to " << ptr->id << endl;
#endif
            } else {
                ptr = front->fail->access(chr);
            }
        }
    }
}
int_t counts[int_t(2e5 + 1)];
void DFS(int_t vtx) {
    for (auto chd : graph[vtx]) {
        DFS(chd);
        mapping[vtx]->mark += mapping[chd]->mark;
    }
    Node* curr = mapping[vtx];
    for (auto x : curr->strs) {
        counts[x] += curr->mark;
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    root->id = 1;
    mapping[1] = root;
    int_t n;
    cin >> n;
    static char buf[int_t(3e6 + 10)];
    for (int_t i = 1; i <= n; i++) {
        cin >> buf;
        insert(buf, i);
    }
    buildFail();
    cin >> buf;
    auto curr = root;

    for (auto ptr = buf; *ptr; ptr++) {
        auto chd = curr->access(*ptr);
        chd->mark += 1;
        curr = chd;
    }
    DFS(1);
    for (int_t i = 1; i <= n; i++)
        cout << counts[i] << endl;
    return 0;
}

2020年10月6日