officeyutong

分类： 未分类

  • UOJ461 新年的Dog划分

    首先考虑搞出来原图的一棵生成树，直接把这棵生成树二分图染色即可。

    一个比较显然的方法是在边集中二分，把所有的边依次排开，假设当前位于边x，在保留已经确定了的生成树上的边的情况下，删掉x之前的所有边，然后看原图是否联通。

    使得x尽可能靠右即可。

    这样一定可以搞出来n-1条边。

    如何判断奇环?

    把树二分图染色后，枚举一条树边，然后删掉这条树边和所有二分图中连接两个点集的边，如果此时图仍然联通说明存在奇环。

    这样的询问次数大概是$(n-1)log(n^2)=O(2nlogn)$的，过不去。

    然后我们尝试考虑对于点进行二分。

    从1号点开始BFS。

    假设当前点为vtx，没访问过的并且和vtx不在一条树边上的点v纳入二分范围。

    设这个点集为S。

    如果所有的边$(vtx,v)(v\in S)$全部删除后原图仍然联通，那么就直接把这些边纳入删除集合，然后队列弹出点vtx。

    否则二分一个位置x，使得位置在x之前的所有边删掉后都不会使得图不连通，但是删掉x后图就不连通。

    此时把x之前的所有边纳入删除集合，$(vtx,x)$纳入树边。

    然后接着二分x后面的点即可（实际实现就是队列不弹出点vtx）。

    询问次数在$O(nlogn)$级别的。

    #include <assert.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include "graph.h"
using int_t = int;
using pair_t = std::pair<int_t, int_t>;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 200;

std::vector<pair_t> result;
std::vector<pair_t> removes;
bool onTree[LARGE + 1][LARGE + 1];
bool removed[LARGE + 1][LARGE + 1];
int_t n;
//删除已知的待删除边和vtx编号在id之前的所有边是否联通
bool myCheck(int_t vtx, const std::vector<int_t>& to, int_t id) {
    std::vector<std::pair<int, int>> next = removes;
    for (int_t i = 0; i <= id; i++) {
        if (onTree[vtx][to[i]] == false) next.push_back(pair_t(vtx, to[i]));
    }
    for (auto& p : next) {
        p.first -= 1;
        p.second -= 1;
        assert(p.first != p.second);
    }
    bool result = query(next);
    return result;
}
void BFS() {
    static bool inq[LARGE + 1];
    std::queue<int_t> queue;
    queue.push(1);
    inq[1] = true;
    while (queue.empty() == false) {
        int_t front = queue.front();

        std::vector<int_t> to;
        for (int_t i = 1; i <= n; i++) {
            if (i != front && inq[i] == false && removed[front][i] == false)
                to.push_back(i);
        }
        int_t left = 0, right = to.size() - 1;
        int_t result = to.size();
        //所有边保留仍然联通,直接标记成废边
        if (myCheck(front, to, right)) {
            for (int_t x : to) {
                removed[x][front] = removed[front][x] = true;
                removes.push_back(pair_t(x, front));
            }
        } else {
            while (left <= right) {
                int_t mid = (left + right) / 2;
                if (!myCheck(front, to, mid)) {
                    right = mid - 1;
                    result = std::min(result, mid);
                } else {
                    left = mid + 1;
                }
            }
            for (int_t i = 0; i < result; i++) {
                removed[to[i]][front] = removed[front][to[i]] = true;
                removes.push_back(pair_t(to[i], front));
            }
        }
        if (result != to.size()) {
            onTree[front][to[result]] = onTree[to[result]][front] = true;
            queue.push(to[result]);
            inq[to[result]] = true;
        } else {
            queue.pop();
        }
    }
}
std::vector<int_t> graph[LARGE + 1];
int_t color[LARGE + 1];
void DFS(int_t vtx, int_t from = -1) {
    for (int_t to : graph[vtx]) {
        if (to != from) {
            color[to] = color[vtx] ^ 1;
            DFS(to, vtx);
        }
    }
}
bool removeCheck(pair_t edge) {
    std::vector<pair_t> next;
    for (int_t i = 1; i <= n; i++) {
        if (color[i] == 0) {
            for (int_t j = 1; j <= n; j++) {
                if (color[j] == 1 && onTree[i][j] == false) {
                    next.push_back(pair_t(i, j));
                }
            }
        }
    }
    next.push_back(edge);
    for (auto& p : next) {
        p.first -= 1;
        p.second -= 1;

        assert(p.first != p.second);
    }
    bool result = query(next);
    return result;
}
std::vector<int> check_bipartite(int vsize) {
    ::n = vsize;
    BFS();
    std::vector<pair_t> treeEdges;
    for (int_t i = 1; i <= n; i++) {
        for (int_t j = i + 1; j <= n; j++) {
            if (onTree[i][j]) {
                graph[i].push_back(j);
                graph[j].push_back(i);
                treeEdges.push_back(pair_t(i, j));
            }
        }
    }
    DFS(1);
    for (const auto& edge : treeEdges) {
        if (removeCheck(edge)) {
            return std::vector<int_t>();
        }
    }
    std::vector<int_t> result;
    for (int_t i = 1; i <= n; i++)
        if (color[i] == 0) result.push_back(i - 1);
    return result;
}

     

  • YT2sOJ04 give you a tree

    zzs上辈子就会做的题我现在才会做..

    一个区间能形成一个联通块，当且仅当这个区间内的边有 区间长度-1 条。

    考虑扫描线。

    每个点存下终点编号比它小的边。

    然后从1开始扫，设当前扫到的点为vtx，维护一棵线段树，线段树下标为x的点的值减掉x后表示的是区间[x,vtx]内存在的边数。

    每次扫到先vtx后，首先把vtx的值设置成vtx，然后枚举vtx一条终点编号比vtx小的出边v，显然v可以给左端点区间在[1,v]内的区间贡献一条边（让以这些地方为左端点，vtx为右端点的区间包括的边数多了1）。

    考虑一个左端点什么时候会成为合法的左端点。

    设这个左端点是x，这个左端点在线段树上的值为val，当且仅当$val-x=vtx-x$（根据上面的定义，线段树下标为x的点的值减掉x后表示的是区间[x,vtx]内存在的边数），即$val=vtx$时，这个左端点会成为一个合法的左端点。

    所以只需要维护全局最大值出现的次数即可。

    #include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#define debug(x) std::cout << #x << " = " << x << std::endl;

typedef int int_t;

using std::cin;
using std::endl;
using std::cout;
const int_t LARGE = 3e5;
struct Node {
    Node* left, *right;
    int_t begin, end;
    int_t mark;
    int_t count;
    int_t max;
    void maintain() {
        if (begin != end) {
            max = std::max(left->max, right->max);
            count = 0;
            if (left->max == max)
                count += left->count;
            if (right->max == max)
                count += right->count;
        }
    }
    void add(int_t x) {
        max += x;
        mark += x;
    }
    void pushDown() {
        if (begin != end) {
            left->add(mark);
            right->add(mark);
            mark = 0;
        }
    }
    Node(int_t begin, int_t end) {
        this->begin = begin;
        this->end = end;
        max = mark = count = 0;
        left = right = nullptr;
    }
    void add(int_t begin, int_t end, int_t val) {
        if (end < this->begin || begin > this->end) {
            return;
        }
        if (this->begin >= begin && this->end <= end) {
            this->add(val);
            return;
        }
        pushDown();
        left->add(begin, end, val);
        right->add(begin, end, val);
        maintain();
    }
    void setPos(int_t pos, int_t val) {
        if (begin == end) {
            this->max = pos;
            this->count = 1;
            return;
        }
        int_t mid = (begin + end) / 2;
        pushDown();
        if (pos <= mid)
            left->setPos(pos, val);
        else
            right->setPos(pos, val);
        maintain();
    }
    static Node* build(int_t begin, int_t end) {
        Node* node = new Node(begin, end);
        if (begin != end) {
            int_t mid = (begin + end) / 2;
            node->left = Node::build(begin, mid);
            node->right = Node::build(mid + 1, end);
            node->maintain();
        }
        return node;
    }
};
std::vector<int_t> graph[LARGE + 1];
int_t n;
int main() {
    scanf("%d", &n);
    for (int_t i = 1; i <= n - 1; i++) {
        int_t v1, v2;
        scanf("%d%d", &v1, &v2);
        if (v1 < v2)
            std::swap(v1, v2);
        graph[v1].push_back(v2);
    }
    int64_t result = 0;
    Node* root = Node::build(1, n);
    for (int_t i = 1; i <= n; i++) {
        root->setPos(i, i);
        for (int_t to : graph[i]) root->add(1, to, 1);
        result += root->count;
#ifdef DEBUG
        cout << "got " << root->count << " at vtx " << i << endl;
#endif
    }
    printf("%lld\n", result);
    return 0;
}

     

  • 多项式三角函数 & 多项式幂函数

    多项式三角函数

    根据欧拉公式，$e^{iF(x)}=\cos(F(x))+i\sin(F(x))$,令$F(x)$为模意义下的复多项式，直接计算即可。

    #include <cmath>
#include <iostream>
using int_t = long long int;

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

const int_t mod = 998244353;
const int_t g = 3;
const int_t LARGE = 1 << 19;
template <typename T>
T power(T base, int_t index);
void poly_inv(const struct complex* A, int_t n, struct complex* result);
int_t bitRev(int_t base, int_t size2);
int_t upper2n(int_t x);
void poly_log(const struct complex* A, int_t n, struct complex* result);
void transform(complex* A, int_t len, int_t arg);
void poly_exp(const struct complex* A, int_t n, struct complex* result);
struct complex {
    int_t real, imag;
    complex operator+(const complex& another) const {
        return complex{(real + another.real) % mod,
                       (imag + another.imag) % mod};
    }
    complex operator-(const complex& another) const {
        return complex{(real - another.real + mod) % mod,
                       (imag - another.imag + mod) % mod};
    }
    complex operator*(const complex& another) const {
        return complex{
            (real * another.real % mod - imag * another.imag % mod + mod) % mod,
            (real * another.imag % mod + imag * another.real % mod) % mod};
    }
    complex operator/(const complex& another) const {
        int_t a = real, b = imag, c = another.real, d = another.imag;
        int_t inv = power(c * c % mod + d * d % mod, -1);
        return complex{(a * c % mod + b * d % mod) % mod * inv % mod,
                       (b * c % mod - a * d % mod + mod) % mod * inv % mod};
    }
    complex operator%(const int_t& x) const {
        return complex{real % x, imag % x};
    }
    complex(int_t a = 0, int_t b = 0) {
        this->real = a;
        this->imag = b;
    }
    complex& operator=(const int_t& rhs) {
        this->real = rhs;
        this->imag = 0;
        return *this;
    }
};
std::ostream& operator<<(std::ostream& os, const complex& comp) {
    os << "complex{real=" << comp.real << ",imag=" << comp.imag << "}";
    return os;
}
int_t revs[20][LARGE + 1];

int main() {
    for (int i = 0; (1 << i) <= LARGE; i++) {
        for (int j = 0; j < LARGE; j++) {
            revs[i][j] = bitRev(j, i);
        }
    }
    static complex A[LARGE], B[LARGE];
    int_t n, type;
    scanf("%lld%lld", &n, &type);
    for (int_t i = 0; i < n; i++) scanf("%lld", &A[i].imag);
    poly_exp(A, n, B);
    if (type == 0) {
        for (int_t i = 0; i < n; i++) printf("%lld ", B[i].imag);
    } else {
        for (int_t i = 0; i < n; i++) printf("%lld ", B[i].real);
    }
    return 0;
}

void transform(complex* A, int_t len, int_t arg) {
    int_t size2 = log2(len);
    for (int_t i = 0; i < len; i++) {
        int_t x = revs[size2][i];
        if (x > i) std::swap(A[i], A[x]);
    }
    for (int_t i = 2; i <= len; i *= 2) {
        complex mr = power(complex{g, 0}, arg * (mod - 1) / i);
        for (int_t j = 0; j < len; j += i) {
            complex curr{1, 0};
            for (int_t k = 0; k < i / 2; k++) {
                complex u = A[j + k];
                complex t = A[j + k + i / 2] * curr;
                A[j + k] = (u + t);
                A[j + k + i / 2] = (u - t);
                curr = curr * mr;
            }
        }
    }
}
//计算多项式A在模x^n下的逆元
// C(x)<-2B(x)-A(x)B^2(x)
void poly_inv(const complex* A, int_t n, complex* result) {
    if (n == 1) {
        result[0] = power(A[0], -1);
        return;
    }
    poly_inv(A, n / 2 + n % 2, result);
    static complex temp[LARGE + 1];
    int_t size2 = upper2n(3 * n + 1);
    for (int_t i = 0; i < size2; i++) {
        if (i < n)
            temp[i] = A[i];
        else
            temp[i] = complex{0, 0};
    }
    transform(temp, size2, 1);
    transform(result, size2, 1);
    for (int_t i = 0; i < size2; i++) {
        result[i] =
            (complex{2, 0} * result[i] - temp[i] * result[i] * result[i]);
    }
    transform(result, size2, -1);
    int_t inv = power(size2, -1);
    for (int_t i = 0; i < size2; i++) {
        if (i < n) {
            result[i] = result[i] * complex{inv, 0};
        } else {
            result[i] = complex{0, 0};
        }
    }
}

void poly_log(const complex* A, int_t n, complex* result) {
    int_t size2 = upper2n(2 * n);
    static complex Ad[LARGE + 1];
    for (int_t i = 0; i < size2; i++) {
        if (i < n) {
            Ad[i] = complex{(i + 1), 0} * A[i + 1];

        } else {
            Ad[i] = complex{0, 0};
        }
        result[i] = complex{0, 0};
    }
    transform(Ad, size2, 1);
    poly_inv(A, n, result);
    transform(result, size2, 1);
    for (int_t i = 0; i < size2; i++) {
        result[i] = result[i] * Ad[i];
    }
    transform(result, size2, -1);
    int_t inv = power(size2, -1);
    for (int_t i = 0; i < size2; i++)
        if (i < n)
            result[i] = result[i] * complex{inv, 0};
        else
            result[i] = complex{0, 0};
    for (int_t i = n - 1; i >= 1; i--) {
        result[i] = result[i - 1] / complex{i, 0};
    }
    result[0] = complex{0, 0};
}
void poly_exp(const complex* A, int_t n, complex* result) {
    if (n == 1) {
        // assert(A[0] == 0);
        result[0] = complex{1, 0};
        return;
    }
    poly_exp(A, n / 2 + n % 2, result);
    static complex G0[LARGE + 1], Ax[LARGE + 1];
    int_t size2 = upper2n(2 * n);
    poly_log(result, n, G0);
    for (int_t i = 0; i < size2; i++) {
        if (i < n)
            Ax[i] = A[i];
        else
            Ax[i] = complex{0, 0};
    }
    transform(Ax, size2, 1);
    transform(G0, size2, 1);
    transform(result, size2, 1);
    for (int_t i = 0; i < size2; i++)
        result[i] = (result[i] - result[i] * (G0[i] - Ax[i]));
    transform(result, size2, -1);
    int_t inv = power(size2, -1);
    for (int_t i = 0; i < size2; i++)
        if (i < n)
            result[i] = result[i] * complex{inv, 0};
        else
            result[i] = complex{0, 0};
}
template <typename T>
T power(T base, int_t index) {
    const int_t phi = mod - 1;
    index = (index % phi + phi) % phi;
    T result = 1;
    while (index) {
        if (index & 1) result = result * base % mod;
        base = base * base % mod;
        index >>= 1;
    }
    return result;
}
int_t bitRev(int_t base, int_t size2) {
    int_t result = 0;
    for (int_t i = 1; i < size2; i++) {
        result |= (base & 1);
        base >>= 1;
        result <<= 1;
    }
    result |= (base & 1);
    return result;
}
int_t upper2n(int_t x) {
    int_t result = 1;
    while (result < x) result *= 2;
    return result;
}

    多项式幂函数

    求$F(x)^m$。

    令$F(x)=cx^pG(x)$,其中$G(x)$为常数项为1多项式。

    则$F(x)^m=(cx^p)^mG(x)^m=c^m\times x^{pm}\times e^{m\log G(x)}$。

    // luogu-judger-enable-o2
#include <assert.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
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 << 19;
int revs[20][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_sqrt(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);
void poly_power(const int* A, int n, int index, int* result);
int modSqrt(int a);
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_t readInt() {
    int_t result = 0;
    char chr = getchar();
    while (isdigit(chr) == false) chr = getchar();
    while (isdigit(chr)) {
        result = (result * 10 + chr - '0') % mod;
        chr = getchar();
    }
    return result;
}
int main() {
    for (int i = 0; (1 << i) <= LARGE; i++) {
        for (int j = 0; j < LARGE; j++) {
            revs[i][j] = bitRev(j, i);
        }
    }
    static int A[LARGE + 1], B[LARGE + 1];
    int_t n, k;
    scanf("%lld%lld", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &A[i]);

    int_t x0pos = -1;
    for (int_t i = 0; i < n; i++) {
        if (A[i]) {
            x0pos = i;
            break;
        }
    }
    if (x0pos == -1) {
        for (int_t i = 0; i < n; i++) printf("0 ");
        return 0;
    }
    // x0pos += 1;
    for (int_t i = 0; i < n; i++) A[i] = A[i + x0pos];
    int_t x0 = A[0];
    const int_t inv = power(x0, -1);
    for (int_t i = 0; i < n; i++) A[i] = A[i] * inv % mod;
    poly_log(A, n, B);
    for (int_t i = 0; i < n; i++) B[i] = B[i] * k % mod;
    memset(A, 0, sizeof(A));
    poly_exp(B, n, A);
    for (int_t i = 0; i < n; i++) A[i] = (int_t)A[i] * power(x0, k) % mod;
    int_t time = x0pos * k;
    if (time <= n - 1) {
        for (int_t i = n - 1; i >= time; i--) A[i] = A[i - time];
        for (int_t i = time - 1; i >= 0; i--) A[i] = 0;
        for (int_t i = 0; i < n; i++) printf("%d ", A[i]);
    } else {
        for (int_t i = 0; i < n; i++) printf("0 ");
    }
    return 0;
}
//计算A(x)^index mod x^n
void poly_power(const int* A, int n, int index, int* result) {
    int size2 = upper2n(2 * n);
    static int base[LARGE + 1];
    for (int i = 0; i < size2; i++) {
        if (i < n)
            base[i] = A[i];
        else
            base[i] = 0;
        result[i] = 0;
    }
    result[0] = 1;
    while (index) {
        transform(base, size2, 1);
        if (index & 1) {
            transform(result, size2, 1);
            for (int i = 0; i < size2; i++) {
                result[i] = (int_t)result[i] * base[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 = 0; i < size2; i++)
            base[i] = (int_t)base[i] * base[i] % mod;
        transform(base, size2, -1);
        for (int i = 0; i < size2; i++) {
            if (i < n)
                base[i] = (int_t)base[i] * power(size2, -1) % mod;
            else
                base[i] = 0;
        }
        index >>= 1;
    }
}
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) {
    int size2 = log2(len);
    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;
        }
    }
}
int modSqrt(int a) {
    const int_t b = 3;
    // mod-1=2^s*t
    int s = 23, t = 119;
    int x = power(a, (t + 1) / 2);
    int e = power(a, t);
    int k = 1;
    while (k < s) {
        if (power(e, 1 << (s - k - 1)) != 1) {
            x = (int_t)x * power(b, (1 << (k - 1)) * t) % mod;
        }
        e = (int_t)power(a, -1) * x % mod * x % mod;
        k++;
    }
    return x;
}
//计算多项式开根
void poly_sqrt(const int* A, int n, int* result) {
    if (n == 1) {
        int p = modSqrt(A[0]);
        result[0] = std::min(p, mod - p);
        return;
    }
    poly_sqrt(A, n / 2 + n % 2, result);
    int size2 = upper2n(3 * n);
    static int Ax[LARGE + 1], pInv[LARGE];
    for (int i = 0; i < size2; i++) {
        if (i < n) {
            Ax[i] = A[i];
        } else {
            Ax[i] = 0;
        }
        pInv[i] = 0;
    }
    poly_inv(result, n, pInv);
    transform(Ax, size2, 1);
    transform(result, size2, 1);
    transform(pInv, size2, 1);
    const int inv2 = power(2, -1);
    for (int i = 0; i < size2; i++) {
        result[i] = (result[i] -
                     ((int_t)result[i] * result[i] % mod - Ax[i] + mod) % mod *
                         inv2 % mod * pInv[i] % 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;
    }
}
void poly_log(const int* A, int n, int* result) {
    int size2 = upper2n(2 * n);
    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 G0[LARGE + 1], Ax[LARGE + 1];
    int size2 = upper2n(2 * n);
    poly_log(result, n, G0);
    for (int_t i = 0; i < size2; i++) {
        if (i < n)
            Ax[i] = A[i];
        else
            Ax[i] = 0;
    }
    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;
}

     

  • 广义二项式定理与生成函数

    $$ \left( x+y \right) ^k=\sum_{n\ge 0}{\left( \begin{array}{c} k\\ n\\ \end{array} \right) x^ny^{k-n},\text{其中}k\text{为任意实数。}} \\ \text{其中}\left( \begin{array}{c} k\\ n\\ \end{array} \right) \text{定义为}\frac{k\left( k-1 \right) \left( k-2 \right) …\left( k-n+1 \right)}{n!} \\ \text{对于形如}\frac{1}{\left( 1-x \right) ^k}=\left( 1-x \right) ^{-k}\text{的生成函数，则有} \\ \left( 1-x \right) ^{-k}=\sum_{n\ge 0}{\left( \begin{array}{c} -k\\ n\\ \end{array} \right) \left( -x \right) ^n=\sum_{n\ge 0}{\left( -1 \right) ^n\left( \begin{array}{c} -k\\ n\\ \end{array} \right) x^n}} \\ \text{对于}\left( \begin{array}{c} -k\\ n\\ \end{array} \right) =\frac{\left( -k \right) \left( -k-1 \right) \left( -k-2 \right) …\left( -k-n+1 \right)}{n!}=\left( -1 \right) ^n\frac{k\left( k+1 \right) \left( k+2 \right) \left( k+3 \right) …\left( k+n-1 \right)}{n!}=\left( -1 \right) ^n\left( \begin{array}{c} k+n-1\\ n\\ \end{array} \right) \\ \text{故}\left( 1-x \right) ^{-k}=\sum_{n\ge 0}{\left( -1 \right) ^{2n}\left( \begin{array}{c} k+n-1\\ n\\ \end{array} \right) x^n}=\sum_{n\ge 0}{\left( \begin{array}{c} k+n-1\\ n\\ \end{array} \right) x^n} $$

  • 洛谷5245 多项式快速幂

    板子。

    // luogu-judger-enable-o2
#include <assert.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
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 << 19;
int revs[20][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_sqrt(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);
void poly_power(const int* A, int n, int index, int* result);
int modSqrt(int a);
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_t readInt() {
    int_t result = 0;
    char chr = getchar();
    while (isdigit(chr) == false) chr = getchar();
    while (isdigit(chr)) {
        result = (result * 10 + chr - '0') % mod;
        chr = getchar();
    }
    return result;
}
int main() {
    for (int i = 0; (1 << i) <= LARGE; i++) {
        for (int j = 0; j < LARGE; j++) {
            revs[i][j] = bitRev(j, i);
        }
    }
    static int A[LARGE + 1], B[LARGE + 1];
    int_t n, k;
    scanf("%lld", &n);
    k = readInt();
    for(int i=0;i<n;i++) scanf("%d",&A[i]);
    // cout << " - " << k << endl;
    poly_log(A, n, B);
    for (int_t i = 0; i < n; i++) {
        B[i] = (B[i] * k) % mod;
#ifdef DEBUG
        cout << B[i] << endl;
#endif
    }
    memset(A, 0, sizeof(A));
    poly_exp(B, n, A);
    for (int i = 0; i < n; i++) printf("%d ", A[i]);
    return 0;
}
//计算A(x)^index mod x^n
void poly_power(const int* A, int n, int index, int* result) {
    int size2 = upper2n(2 * n);
    static int base[LARGE + 1];
    for (int i = 0; i < size2; i++) {
        if (i < n)
            base[i] = A[i];
        else
            base[i] = 0;
        result[i] = 0;
    }
    result[0] = 1;
    while (index) {
        transform(base, size2, 1);
        if (index & 1) {
            transform(result, size2, 1);
            for (int i = 0; i < size2; i++) {
                result[i] = (int_t)result[i] * base[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 = 0; i < size2; i++)
            base[i] = (int_t)base[i] * base[i] % mod;
        transform(base, size2, -1);
        for (int i = 0; i < size2; i++) {
            if (i < n)
                base[i] = (int_t)base[i] * power(size2, -1) % mod;
            else
                base[i] = 0;
        }
        index >>= 1;
    }
}
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) {
    int size2 = log2(len);
    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;
        }
    }
}
int modSqrt(int a) {
    const int_t b = 3;
    // mod-1=2^s*t
    int s = 23, t = 119;
    int x = power(a, (t + 1) / 2);
    int e = power(a, t);
    int k = 1;
    while (k < s) {
        if (power(e, 1 << (s - k - 1)) != 1) {
            x = (int_t)x * power(b, (1 << (k - 1)) * t) % mod;
        }
        e = (int_t)power(a, -1) * x % mod * x % mod;
        k++;
    }
    return x;
}
//计算多项式开根
void poly_sqrt(const int* A, int n, int* result) {
    if (n == 1) {
        int p = modSqrt(A[0]);
        result[0] = std::min(p, mod - p);
        return;
    }
    poly_sqrt(A, n / 2 + n % 2, result);
    int size2 = upper2n(3 * n);
    static int Ax[LARGE + 1], pInv[LARGE];
    for (int i = 0; i < size2; i++) {
        if (i < n) {
            Ax[i] = A[i];
        } else {
            Ax[i] = 0;
        }
        pInv[i] = 0;
    }
    poly_inv(result, n, pInv);
    transform(Ax, size2, 1);
    transform(result, size2, 1);
    transform(pInv, size2, 1);
    const int inv2 = power(2, -1);
    for (int i = 0; i < size2; i++) {
        result[i] = (result[i] -
                     ((int_t)result[i] * result[i] % mod - Ax[i] + mod) % mod *
                         inv2 % mod * pInv[i] % 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;
    }
}
void poly_log(const int* A, int n, int* result) {
    int size2 = upper2n(2 * n);
    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 G0[LARGE + 1], Ax[LARGE + 1];
    int size2 = upper2n(2 * n);
    poly_log(result, n, G0);
    for (int_t i = 0; i < size2; i++) {
        if (i < n)
            Ax[i] = A[i];
        else
            Ax[i] = 0;
    }
    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;
}

     

  • YNOI2018 五彩斑斓的世界

    AVX2优化暴力。

    #pragma GCC target("avx,avx2")

#include <immintrin.h>
#include <cstdio>
#include <iostream>
using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 1e5;

int seq[LARGE + 1];
int n, m;
void modify(int* left, int* right, int val) {
    __m256i addval = _mm256_set_epi32(val, val, val, val, val, val, val, val);
    while (int_t(left) % 32 && left <= right) {
        if (*left > val) *left -= val;
        left++;
    }
    while (left + 7 <= right) {
        __m256i curr = *(__m256i*)left;
        *(__m256i*)left = _mm256_add_epi32(
            curr, _mm256_mullo_epi32(_mm256_cmpgt_epi32(curr, addval), addval));
        left += 8;
    }
    while (left <= right) {
        if (*left > val) *left -= val;
        left++;
    }
}
int query(int* left, int* right, int val) {
    int result = 0;
    __m256i sum = _mm256_setzero_si256();
    while (int_t(left) % 32 && left <= right) {
        if (*left == val) result++;
        left++;
    }
    __m256i tocmp = _mm256_set_epi32(val, val, val, val, val, val, val, val);
    while (left + 7 <= right) {
        sum = _mm256_sub_epi32(sum, _mm256_cmpeq_epi32(*(__m256i*)left, tocmp));
        left += 8;
    }
    while (left <= right) {
        if (*left == val) result++;
        left++;
    }
    int* arr = (int*)∑
    for (int i = 0; i < 8; i++) result += arr[i];
    return result;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &seq[i]);
    for (int i = 1; i <= m; i++) {
        int opt, left, right, x;
        scanf("%d%d%d%d", &opt, &left, &right, &x);
        if (opt == 1) {
            modify(seq + left, seq + right, x);
        } else {
            printf("%d\n", query(seq + left, seq + right, x));
        }
    }
    return 0;
}

     

  • NOI2016 循环之美

    $$ \text{设循环节长度为}l,,\text{如果有}\frac{x}{y}\text{为纯循环小数，则有} \\ \frac{x}{y}\,\,mod\,\,\text{1 }=\frac{x}{y}k^l\,\,mod\,\,1 \\ \text{即} \\ \frac{x}{y}-\lfloor \frac{x}{y} \rfloor =\frac{xk^l}{y}-\lfloor \frac{xk^l}{y} \rfloor \\ x-y\lfloor \frac{x}{y} \rfloor =xk^l-y\lfloor \frac{xk^l}{y} \rfloor \\ \text{由于}x\,\,mod\,\,y=x-y\lfloor \frac{x}{y} \rfloor \\ \text{故}x-y\lfloor \frac{x}{y} \rfloor =xk^l-y\lfloor \frac{xk^l}{y} \rfloor \text{等价于} \\ x=xk^l\left( mod\,\,y \right) \\ \text{由于}\frac{x}{y}\text{为最简分数，故}x\text{与}y\text{互质，所以} \\ 1=k^l\left( mod\,\,y \right) \\ \text{当且仅当}k\text{与}y\text{互质的时候，存在}l=c\varphi \left( y \right) \text{使得}1=k^l\left( mod\,\,y \right) \text{成立，故答案等价于统计} \\ \sum_{1\le i\le n}{\sum_{1\le j\le m}{\left[ gcd\left( i,j \right) =1 \right] \left[ gcd\left( j,k \right) =1 \right]}} \\ \text{设}f\left( n,m,k \right) =\sum_{1\le i\le n}{\sum_{1\le j\le m}{\left[ gcd\left( i,j \right) ==1 \right] \left[ gcd\left( j,k \right) ==1 \right]}} \\ f\left( n,m,k \right) =\sum_{1\le i\le n}{\sum_{1\le j\le m}{\left[ gcd\left( i,j \right) =1 \right] \sum_{d|gcd\left( j,k \right)}{\mu \left( d \right)}}} \\ =\sum_{1\le i\le n}{\sum_{1\le jd\le m}{\left[ gcd\left( i,jd \right) =1 \right] \sum_{d|gcd\left( jd,k \right)}{\mu \left( d \right)}}} \\ =\sum_{1\le i\le n}{\sum_{1\le jd\le m}{\left[ gcd\left( i,jd \right) =1 \right] \sum_{d|k}{\mu \left( d \right)}}} \\ =\sum_{d|k}{\mu \left( d \right) \sum_{1\le i\le n}{\sum_{1\le j\le \lfloor \frac{m}{d} \rfloor}{\left[ gcd\left( i,jd \right) =1 \right]}}} \\ =\sum_{d|k}{\mu \left( d \right) \sum_{1\le i\le n}{\sum_{1\le j\le \lfloor \frac{m}{d} \rfloor}{\left[ gcd\left( i,j \right) =1 \right] \left[ gcd\left( i,d \right) =1 \right]}}} \\ =\sum_{d|k}{\mu \left( d \right) \sum_{1\le i\le \lfloor \frac{m}{d} \rfloor}{\sum_{1\le j\le n}{\left[ gcd\left( i,j \right) =1 \right] \left[ gcd\left( j,d \right) =1 \right]}}} \\ =\sum_{d|k\,\,and\,\,\mu \left( d \right) \ne 0}{\mu \left( d \right) f\left( \lfloor \frac{m}{d} \rfloor ,n,d \right)}\left( \text{直接过滤掉}\mu \left( d \right) \text{为0的}d,\text{加快时间} \right) \\ \text{边界条件}f\left( n,m,k \right) =0\left( n=\text{0或}m=0 \right) \\ f\left( n,m,1 \right) =\sum_{1\le i\le n}{\sum_{1\le j\le m}{\left[ gcd\left( i,j \right) =1 \right]}}=\sum_{1\le k\le \min \left( n,m \right)}{\mu \left( k \right) \lfloor \frac{n}{k} \rfloor \lfloor \frac{m}{k} \rfloor},\text{可以通过杜教筛快速求出。} \\ \text{复杂度瞎猜一顿是}O\left( kf\left( k \right) \log n\log m+n^{\frac{2}{3}} \right) ,\text{其中}f\left( k \right) \text{是}k\text{的约数中莫比乌斯函数值不为0的约数个数} $$

    #include <algorithm>
#include <cmath>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <iostream>
#include <unordered_map>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 1e6;
bool isPrime[LARGE + 1];
int factor[LARGE + 1];
int mu[LARGE + 1];
std::vector<int> divisors[LARGE + 1];
#ifdef COUNT
int_t count = 0;
#endif
int n, m, k;
int sqrtN;
int muPrefix(int n) {
    if (n <= LARGE) return mu[n];
#ifdef COUNT
    count += 1;
#endif
    static __gnu_pbds::gp_hash_table<int, int> memory;
    if (memory.find(n) != memory.end()) return memory[n];
    int &result = memory[n];
    result = 1;
    int i = 2;
    for (; i * i <= n; i++) {
        result -= muPrefix(n / i);
    }
    int k = n / i;
    while (i <= n) {
        int next = n / k;
        result -= (next - i + 1) * muPrefix(k);
        i = next + 1;
        k--;
    }
    return result;
}
int_t f1(int n, int m) {
    int_t result = 0;
    int i = 1;
    if (n > m) std::swap(n, m);
    while (i <= n) {
        int p1 = n / i, p2 = m / i;
        int next = std::min(n / p1, m / p2);
        result += (int_t)(muPrefix(next) - muPrefix(i - 1)) * p1 * p2;
        i = next + 1;
    }
    return result;
}
int_t f(int n, int m, int k) {
    if (n == 0 || m == 0) return 0;
#ifdef DEBUG
    cout << "at " << n << "," << m << "," << k << endl;
#endif
    if (k == 1) return f1(n, m);
    int_t result = 0;
    for (int x : divisors[k]) {
        result += (mu[x] - mu[x - 1]) * f(m / x, n, x);
    }
    return result;
}
int main() {
    cin >> n >> m >> k;
    sqrtN = sqrt(n);
    std::fill(isPrime + 1, isPrime + 1 + LARGE, 1);
    for (int_t i = 2; i <= LARGE; i++) {
        if (isPrime[i]) {
            for (int_t j = i * i; j <= LARGE; j += i) {
                isPrime[j] = false;
                factor[j] = i;
            }
            factor[i] = i;
        }
    }
    mu[1] = 1;
    for (int_t i = 2; i <= LARGE; i++) {
        int_t factor = ::factor[i];
#ifdef DEBUG
        if (i <= 100) cout << "factor " << i << " = " << ::factor[i] << endl;
#endif
        if (i / factor % factor == 0) {
            mu[i] = 0;
        } else {
            mu[i] = mu[i / factor] * -1;
        }
    }
    for (int_t i = 1; i <= LARGE; i++) {
        mu[i] += mu[i - 1];
    }
    for (int_t i = 1; i <= k; i++) {
        //过滤掉值为0的数
        if (mu[i] - mu[i - 1] != 0)
            for (int_t j = 1; j * i <= k; j++) {
                divisors[j * i].push_back(i);
            }
    }
#ifdef DEBUG
    for (int_t i = 1; i <= k; i++) {
        cout << "div " << i << " ";
        for (int_t x : divisors[i]) cout << x << " ";
        cout << endl;
    }
#endif
    cout << f(n, m, k) << endl;
#ifdef COUNT
    cout << count << endl;
#endif
    return 0;
}

     

  • 洛谷2012 拯救世界2

    $$ \text{考虑对于每一种基因搞出来一个指数生成函，最后把他们乘起来。} \\ \text{注意到}\frac{\sin \left( ix \right)}{i}=\frac{\sinh \left( x \right)}{i}=\sum_{i\ge 0}{\frac{x^{2i+1}}{\left( 2i+1 \right) !}},\cos \left( ix \right) =\cosh \left( x \right) =\sum_{i\ge 0}{\frac{x^{2i}}{\left( 2i \right) !}} \\ \text{所以基因序列的生成函数为}F\left( x \right) =\left( \frac{\sinh \left( x \right)}{i}\cosh \left( x \right) e^x \right) ^4=\sinh \left( x \right) ^4\cosh \left( x \right) ^4e^{4x} \\ \text{大力麦克劳林展开发现} \\ F\left( x \right) =\frac{24}{\text{4!}}x^4+\frac{480}{\text{5!}}x^5+\frac{107520x^6}{\text{6!}}+\frac{1419264x^7}{\text{7!}}+\frac{18063360x^8}{\text{8!}}+\frac{225116160x^9}{\text{9!}}+…. \\ \text{所以答案即为}F^{\left( n \right)}\left( 0 \right) ,\text{同时注意到，对于}n<\text{4,答案为}0. \\ \text{经过}sympy\text{打表发现，答案极有可能是一个线性递推式，故写程序验证，发现} \\ f\left( n \right) =20f\left( n-1 \right) -80f\left( n-2 \right) -320f\left( n-3 \right) +1536f\left( n-4 \right) ,\text{同时} \\ f\left( 4 \right) =\text{24,}f\left( 5 \right) =\text{480,}f\left( 6 \right) =\text{7680,}f\left( 7 \right) =\text{107520，对于}k\le \text{3,}f\left( k \right) =0 \\ \text{然后直接矩乘即可通过本题}\left( \text{然而我一开始读入写挂导致在结尾没有回车或者空格的点}TLE \right) \\ \text{如果追求更高的速度，可以算一下这个递推的特征根，}x^4=20x^3-80x^2-320x+\text{1536,解得} \\ x=\left\{ -\text{4,4,8,}12 \right\} \\ \text{之后大力解方程求出来系数，故} \\ f\left( n-4 \right) =\left( -4 \right) ^n+6\times 4^n-64\times 8^n+81\times 12^n \\ \text{直接整数快速幂即可。} \\ $$

    from sympy import *
x = symbols("x")
f = ((sinh(x)*cosh(x)*exp(x))**4).diff().diff().diff().diff()
coefs = []
for i in range(20):
    coefs.append(f.subs([(x, 0)]))
    f = f.diff()
print(coefs)

eqs = []
xs = list([symbols("x%d" % i) for i in range(8)])
A = 4
for i in range(A+4):
    a = 0
    for j in range(i, i+A):
        a += xs[j-i]*coefs[j]
    eqs.append(Eq(a, coefs[i+A]))
print(eqs)
print(solve(eqs))
    #pragma GCC target("avx2,sse")
#include <assert.h>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
using int_t = unsigned long long int;
using std::cin;
using std::cout;
using std::endl;

const int mod = 1e9;
const int phi = 400000000;
template <class T>
void read(T& x) {
    x = 0;
    char chr = getchar();
    assert(chr != '-');
    int counter = 0;
    while (isdigit(chr) == false) {
        int curr = getchar();
        if (curr == -1) return;
        chr = curr;
        counter++;
        assert(counter <= 10);
    }
    while (isdigit(chr)) {
        x = x * 10 + (chr - '0');
        chr = getchar();
    }
}
template <class T>
void write(T x) {
    assert(x >= 0);
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
}
int main() {
    int counter = 0;
    while (true) {
        int_t x;
        read(x);
        if (x == 0) break;
        counter += 1;
        assert(counter <= 200000);
        if (x > phi) x = x % phi + phi;
        if (x < 4) {
            write(0);
            putchar('\n');
            continue;
        }
        x -= 4;
        int t2 = 1;
        int t3 = 1;
        int b3 = 3, b2 = 2;
        int index = x;
        while (index) {
            t2 = (int_t)t2 * ((index & 1) ? b2 : 1) % mod;
            t3 = (int_t)t3 * ((index & 1) ? b3 : 1) % mod;
            b3 = (int_t)b3 * b3 % mod;
            b2 = (int_t)b2 * b2 % mod;
            index >>= 1;
        }
        int t4 = (int_t)t2 * t2 % mod;
        int result = ((int_t)((x & 1) ? (mod - 1) : 1) + (int_t)81 * t3 + 6 -
                      (int_t)64 * t2 % mod + mod) %
                     mod * t4 % mod;
        write(result);
        putchar('\n');
    }
    return 0;
}

     

  • 有下界的可行流/有源汇最大流/有源汇的最小流

    带下界的无源汇可行流

    建立超级源$S_0$，超级汇$T_0$

    对于边$(from,to,lower,upper)$，拆成以下三条下界为0的边：

    • $(from,T_0,lower)$
    • $(S_0,to,lower)$
    • $(from,to,upper-lower)$

    然后在新的网络里跑从$S_0$到$T_0$的最大流。

    如果流量为所有边的下界之和，则存在解，每条边的流量为新边的流量加上他的下界，否则无解。

    原理：

    给每条边提供了额外的流量用来满足下界，同时又要求必须要把这些流量流出去。

    带下界的有源汇最大流

    设源点为$S_1$,汇点为$T_1$.

    显然有源汇的情况下无法满足对于每个点均流量守恒，于是连接一条边$(T_1,S_1,\infty)$，这样就可以构造一个满足每个点均流量守恒的无源汇可行流了。

    可行流的值即为边$(T_1,S_1,\infty)$的流量。

    先跑出来可行流并判断是否可行，然后删掉边$(T_1,S_1,\infty)$，在跑一遍从$S_1$到$T_1$的最大流(目的是把除了下界流量之外，还能够增广的流量补上)，可行流加上这次的最大流即为结果。

    带下界的有源汇最小流

    设源点为$S_1$,汇点为$T_1$.

    像有源汇最大流一样先跑一遍可行流，然后删掉边$(T_1,S_1,\infty)$，然后跑一遍从$T_1$到$S_1$的最大流。

    注意是从$T_1$到$S_1$。

    然后可行流减掉第二次的最大流即为答案。

    目的是把除了下界之外的流量中，能够退流的给退掉。

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

const int_t LARGE = 300;
const int_t EDGE_LARGE = 10200;
const int_t SOURCE = 201;
const int_t SINK = 202;
const int_t INF = 0x7ffffffffff;
struct Edge {
    int_t to, capacity, flow;
    Edge* rev;
};

std::vector<Edge*> graph[LARGE + 1];
int_t dis[LARGE + 1], curr[LARGE + 1], visited[LARGE + 1];
//压入边(from,to,lower,upper),返回正向边
Edge* pushEdge(int_t from, int_t to, int_t cap) {
    Edge* edge0 = new Edge{to, cap, 0};
    Edge* edge1 = new Edge{from, 0, 0, edge0};
    edge0->rev = edge1;
    graph[from].push_back(edge0);
    graph[to].push_back(edge1);
    return edge0;
}
Edge* pushEdge(int_t from, int_t to, int_t lower, int_t upper) {
    pushEdge(from, SINK, lower);
    pushEdge(SOURCE, to, lower);
    return pushEdge(from, to, upper - lower);
}
bool BFS(int_t source, int_t sink) {
    std::fill(dis, dis + 1 + LARGE, INF);
    std::fill(curr, curr + 1 + LARGE, 0);
    std::fill(visited, visited + 1 + LARGE, false);
    std::queue<int_t> queue;
    dis[source] = 0;
    visited[source] = true;
    queue.push(source);
    while (queue.empty() == false) {
        int_t front = queue.front();
        queue.pop();
        for (Edge* edge : graph[front]) {
            if (edge->capacity > edge->flow && visited[edge->to] == false) {
                visited[edge->to] = true;
                dis[edge->to] = dis[front] + 1;
                queue.push(edge->to);
            }
        }
    }
    return visited[sink];
}
int_t DFS(int_t vtx, int_t sink, int_t minf = INF) {
    if (vtx == sink || minf == 0) return minf;
    int_t result = 0;
    for (int_t& i = curr[vtx]; i < graph[vtx].size(); i++) {
        Edge* edge = graph[vtx][i];
        if (dis[edge->to] == dis[vtx] + 1) {
            int_t x = DFS(edge->to, sink,
                          std::min(minf, edge->capacity - edge->flow));
            if (x > 0) {
                minf -= x;
                result += x;
                edge->flow += x;
                edge->rev->flow -= x;
                if (minf == 0) break;
            }
        }
    }
    return result;
}
Edge* edges[EDGE_LARGE + 1];
int_t lowers[EDGE_LARGE + 1];
int main() {
    int_t n, m;
    cin >> n >> m;
    int_t sum = 0;
    for (int_t i = 1; i <= m; i++) {
        int_t from, to, lower, upper;
        cin >> from >> to >> lower >> upper;
        lowers[i] = lower;
        edges[i] = pushEdge(from, to, lower, upper);
        sum += lower;
    }
    int_t flow = 0;
    while (BFS(SOURCE, SINK)) flow += DFS(SOURCE, SINK);
#ifdef DEBUG
    cout << "flow = " << flow << endl;
#endif
    if (flow != sum) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
        for (int_t i = 1; i <= m; i++) {
            cout << lowers[i] + edges[i]->flow << endl;
        }
    }
    return 0;
}
    #include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 300;
const int_t EDGE_LARGE = 10200;
const int_t SOURCE = 203;
const int_t SINK = 204;
const int_t INF = 0x7fffffffffffff;
struct Edge {
    int_t to, capacity, flow;
    Edge* rev;
};

std::vector<Edge*> graph[LARGE + 1];
int_t dis[LARGE + 1], curr[LARGE + 1], visited[LARGE + 1];
//压入边(from,to,lower,upper),返回正向边
Edge* pushEdge(int_t from, int_t to, int_t cap) {
    Edge* edge0 = new Edge{to, cap, 0};
    Edge* edge1 = new Edge{from, 0, 0, edge0};
    edge0->rev = edge1;
    graph[from].push_back(edge0);
    graph[to].push_back(edge1);
    return edge0;
}
Edge* pushEdge(int_t from, int_t to, int_t lower, int_t upper) {
    pushEdge(from, SINK, lower);
    pushEdge(SOURCE, to, lower);
    return pushEdge(from, to, upper - lower);
}
bool BFS(int_t source, int_t sink) {
    std::fill(dis, dis + 1 + LARGE, INF);
    std::fill(curr, curr + 1 + LARGE, 0);
    std::fill(visited, visited + 1 + LARGE, false);
    std::queue<int_t> queue;
    dis[source] = 0;
    visited[source] = true;
    queue.push(source);
    while (queue.empty() == false) {
        int_t front = queue.front();
        queue.pop();
        for (Edge* edge : graph[front]) {
            if (edge->capacity > edge->flow && visited[edge->to] == false) {
                visited[edge->to] = true;
                dis[edge->to] = dis[front] + 1;
                queue.push(edge->to);
            }
        }
    }
    return visited[sink];
}
int_t DFS(int_t vtx, int_t sink, int_t minf = INF) {
    if (vtx == sink || minf == 0) return minf;
    int_t result = 0;
    for (int_t& i = curr[vtx]; i < graph[vtx].size(); i++) {
        Edge* edge = graph[vtx][i];
        if (dis[edge->to] == dis[vtx] + 1) {
            int_t x = DFS(edge->to, sink,
                          std::min(minf, edge->capacity - edge->flow));
            if (x > 0) {
                minf -= x;
                result += x;
                edge->flow += x;
                edge->rev->flow -= x;
                if (minf == 0) break;
            }
        }
    }
    return result;
}
Edge* edges[EDGE_LARGE + 1];
int_t lowers[EDGE_LARGE + 1];
int main() {
    int_t n, m, s, t;
    cin >> n >> m >> s >> t;
    int_t sum = 0;
    for (int_t i = 1; i <= m; i++) {
        int_t from, to, lower, upper;
        cin >> from >> to >> lower >> upper;
        lowers[i] = lower;
        edges[i] = pushEdge(from, to, lower, upper);
        sum += lower;
    }
    int_t flow = 0;
    Edge* super = pushEdge(t, s, INF);
    while (BFS(SOURCE, SINK)) flow += DFS(SOURCE, SINK);

#ifdef DEBUG
    cout << "flow = " << flow << endl;
#endif
    if (flow < sum) {
        cout << "please go home to sleep" << endl;
    } else {
        int_t result = -super->rev->flow;
        super->capacity = 0;
        super->flow = super->rev->flow = 0;
        while (BFS(s, t)) result += DFS(s, t);
        cout << result << endl;
    }
    return 0;
}
    #include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 50103;
const int_t EDGE_LARGE = 125003;
const int_t SOURCE = 50101;
const int_t SINK = 50102;
const int_t INF = 0x7fffffffffffff;
struct Edge {
    int_t to, capacity, flow;
    Edge* rev;
};

std::vector<Edge*> graph[LARGE + 1];
int_t dis[LARGE + 1], curr[LARGE + 1], visited[LARGE + 1];
//压入边(from,to,lower,upper),返回正向边
Edge* pushEdge(int_t from, int_t to, int_t cap) {
    Edge* edge0 = new Edge{to, cap, 0};
    Edge* edge1 = new Edge{from, 0, 0, edge0};
    edge0->rev = edge1;
    graph[from].push_back(edge0);
    graph[to].push_back(edge1);
    return edge0;
}
Edge* pushEdge(int_t from, int_t to, int_t lower, int_t upper) {
    pushEdge(from, SINK, lower);
    pushEdge(SOURCE, to, lower);
    return pushEdge(from, to, upper - lower);
}
bool BFS(int_t source, int_t sink) {
    std::fill(dis, dis + 1 + LARGE, INF);
    std::fill(curr, curr + 1 + LARGE, 0);
    std::fill(visited, visited + 1 + LARGE, false);
    std::queue<int_t> queue;
    dis[source] = 0;
    visited[source] = true;
    queue.push(source);
    while (queue.empty() == false) {
        int_t front = queue.front();
        queue.pop();
        for (Edge* edge : graph[front]) {
            if (edge->capacity > edge->flow && visited[edge->to] == false) {
                visited[edge->to] = true;
                dis[edge->to] = dis[front] + 1;
                queue.push(edge->to);
            }
        }
    }
    return visited[sink];
}
int_t DFS(int_t vtx, int_t sink, int_t minf = INF) {
    if (vtx == sink || minf == 0) return minf;
    int_t result = 0;
    for (int_t& i = curr[vtx]; i < graph[vtx].size(); i++) {
        Edge* edge = graph[vtx][i];
        if (dis[edge->to] == dis[vtx] + 1) {
            int_t x = DFS(edge->to, sink,
                          std::min(minf, edge->capacity - edge->flow));
            if (x > 0) {
                minf -= x;
                result += x;
                edge->flow += x;
                edge->rev->flow -= x;
                if (minf == 0) break;
            }
        }
    }
    return result;
}
Edge* edges[EDGE_LARGE + 1];
int_t lowers[EDGE_LARGE + 1];
int main() {
    int_t n, m, s, t;
    cin >> n >> m >> s >> t;
    int_t sum = 0;
    for (int_t i = 1; i <= m; i++) {
        int_t from, to, lower, upper;
        cin >> from >> to >> lower >> upper;
        lowers[i] = lower;
        edges[i] = pushEdge(from, to, lower, upper);
        sum += lower;
    }
    int_t flow = 0;
    Edge* super = pushEdge(t, s, INF);
    while (BFS(SOURCE, SINK)) flow += DFS(SOURCE, SINK);

#ifdef DEBUG
    cout << "flow = " << flow << endl;
#endif
    if (flow < sum) {
        cout << "please go home to sleep" << endl;
    } else {
        int_t result = -super->rev->flow;
        super->capacity = 0;
        super->flow = super->rev->flow = 0;
        while (BFS(t, s)) result -= DFS(t, s);
        cout << result << endl;
    }
    return 0;
}

     

  • 2019-1-19

    // luogu-judger-enable-o2
#include <algorithm>
#include <iostream>
#include <vector>
// int_t可以直接当成int
typedef int int_t;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 5000;
const int_t OFFSET = 2000;
//某个点与哪个点匹配
int_t matched[LARGE + 1];
//这个点是否已经访问过(当前次DFS中)
bool check[LARGE + 1];
std::vector<int_t> graph[LARGE + 1];

bool DFS(int_t vertex) {
    for (int_t i = 0; i < graph[vertex].size(); i++) {
        int_t to = graph[vertex][i];
        if (check[to] == false) {
            check[to] = true;
            if (matched[to] == -1 || DFS(matched[to])) {
                matched[to] = vertex;
                matched[vertex] = to;
                return true;
            }
        }
    }
    return false;
}

void pushEdge(int_t from, int_t to) {
    graph[from].push_back(to);
    graph[to].push_back(from);
}

int main() {
    std::fill(matched + 1, matched + 1 + LARGE, -1);
    int_t n, m, e;
    cin >> n >> m >> e;
    for (int_t i = 1; i <= e; i++) {
        int_t left, right;
        cin >> left >> right;
        //题目中可能出现的不合法数据
        if (right > m) continue;
        pushEdge(left, right + OFFSET);
    }
    int_t result = 0;
    for (int_t i = 1; i <= n; i++) {
        if (matched[i] == -1) {
            //每次DFS前要清空visited数组
            std::fill(check + 1, check + 1 + LARGE, false);
            if (DFS(i)) {
                result += 1;
            }
        }
    }
    cout << result << endl;
    return 0;
}