Install Kafka

step 1. launch zookeeper in background

1
2
3
4
5

docker run -d \
-p 2181:2181 \
--name zookeeper \
-m 100M --memory-swap 100M --cpus 0.1 \
zookeeper

step 2. launch kafka

1
2
3
4
5
6
7
8
9
10

docker run -it --rm \
--link zookeeper:zookeeper \
--name=kafka \
-p 9092:9092 \
-m 200M --memory-swap=1024M \
1144560553/kafka:test \
bin/kafka-server-start.sh config/server.properties \
--override zookeeper.connect=zookeeper:2181 \
--override listeners=PLAINTEXT://0.0.0.0:9092 \
--override advertised.listeners=PLAINTEXT://localhost:9092

Project In Github

https://github.com/fightinggg/kafka-docker

Project In Dockerhub

使用Github Packages Repository

这里主要介绍Github packages搭建私服，这种方案上传和下载都需要使用token

步骤1

访问地址 ,点击Generate new token 创建新的token，选择权限 write:packages

理论篇

决策单调性

对于一类一维\(dp\),若有转移\(dp[i]=min/max(dp[j]+w(i,j)) 0<j<i\)，并假定\(pri[i]\)为到\(dp[i]\)的最优转移\(j\)，如果\(pri[i]\)关于\(i\)单调，那么我们称该\(dp\)具有决策单调性。

对于一类二维\(dp\),如果有转移$dp[i][j]=min/max(dp[i][k]+dp[k+1][j]+w(i,j)) i<=k<j \(并假定\)pro[i][j]\(为到\)dp[i][j]\(的最优转移\)k\(,如果\)pri[i][j]\(关于\)i\(单调，且关于\)j\(单调，那么我们称该\)dp$具有决策单调性。

四边形不等式

对于二元数论函数，\(w(i,j)\)，若满足\(a\le b\le c\le d\)恒有 \(w(a,d)+w(b,c) \ge w(a,c)+w(b,d)\)则该二元函数满足四边形不等式

他的充要条件是: 若\(a\lt b\) 恒有\(w(a,b)+w(a+1,b+1) \ge w(a,b+1)+w(a+1,b)\)

可以理解为，交叉小于包含

区间包含单调性

对于二元数论函数，\(i<j\)的\(w(i,j)\) 我们将参数看做区间，定义区间的包含为偏序关系， 若\(w\)的值关于该偏序关系单调，则称该函数具有区间包含单调性。

比赛链接

https://www.jisuanke.com/contest/20871/challenges

比赛链接

https://www.jisuanke.com/contest/20844

B. So Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> v1;
const int bit = 30;
const int maxn = 1e5 + 5;

v1 tree[maxn], kdisSon[maxn];
int value[maxn], stk[maxn];
unsigned long long dp[maxn], ans[maxn];
int state[maxn][4];

void dfs1(int cur, int k, int dep) {
    stk[dep] = cur;
    if (dep - k >= 0) {
        kdisSon[stk[dep - k]].push_back(cur);
    }
    for (int son:tree[cur]) {
        dfs1(son, k, dep + 1);
    }
}


void dfs2(int cur, int j, int k) {
    for (int t = 0; t < 4; t++) {
        state[cur][t] = 0;
    }
    for (int son:tree[cur]) {
        dfs2(son, j, k);

        for (int kson:kdisSon[son]) {
            int msk1 = (value[kson] & (1 << j)) >> j;
            int msk2 = (value[kson] & (1 << k)) >> k;
            int t = msk1 << 1 | msk2;
            state[cur][t]--;
        }
        for (int t = 0; t < 4; t++) {
            state[cur][t] += state[son][t];
        }
    }
    int msk1 = (value[cur] & (1 << j)) >> j;
    int msk2 = (value[cur] & (1 << k)) >> k;
    int t = msk1 << 1 | msk2;
    state[cur][t]++;
    dp[cur] = 0;
    for (int t = 0; t <= 1; t++) {
        ll add = 1ll * state[cur][t ^ 3] * state[cur][t];
        add <<= j + k;
        dp[cur] += add;
    }
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &value[i]);
    }
    for (int i = 2; i <= n; i++) {
        int fa;
        scanf("%d", &fa);
        tree[fa].push_back(i);
    }

    dfs1(1, k, 0);
    for (int i = 0; i < bit; i++) {
        dfs2(1, i, i);
        for (int cur = 1; cur <= n; cur++) {
            ans[cur] += dp[cur];
        }
        for (int j = i + 1; j < bit; j++) {
            dfs2(1, i, j);
            for (int cur = 1; cur <= n; cur++) {
                ans[cur] += dp[cur] * 2;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%llu\n", ans[i]);
    }
}

分块

已知某函数\(f(x)\)对于\(x\in[l,r]\)，有\(f(x)\)关于\(x\)单调，且\(f(x)\)值域远小于\(x\)的定义域。

现在要你求\(\sum_{x=1}^n g(x,f(x))\)

那么我们就可以根据\(f(x)\)对\(g\)进行分块，在这一块中，始终有常数\(y=f(x)\)，然后对\(h(x)=g(x,y)\)统计\(x\)的前缀和。

最终我们就能很快的计算答案。

莫比乌斯反演

狄利克雷卷积

\[ \begin{aligned} f(n)\circ g(n)=\sum_{d|n} f(d)\cdot g(\frac{n}{d}) \end{aligned} \]

莫比乌斯函数

\[ f(n)= \begin{cases} 1 &n=1 \\(-1)^k &n=p_1\cdot p_2\cdot \cdot \cdot p_k \\0 &p^k|n , k>1 \end{cases} \]

反演

若\(F(n)=\sum_{d|n} f(d)\)

则\(f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})\)

二项式反演

\[ f_n = \sum_{i=0}^n (-1)^i {n \choose i} g_i \Leftrightarrow g_n = \sum_{i=0}^n (-1)^i {n \choose i} f_i \]

前言

关于生成函数有很多概念模糊的地方，比如生成函数的乘法是怎么定义的，比如乘法可以换序吗？比如为什么可以把多项式变成对数函数？为什么又可以使用泰勒展开？

前置知识

代数系统，群论

环

环是一个具有两个二元运算的代数系统。环\(\lt R,+,\circ\gt\)满足

• \(\lt R,+\gt\)构成交换群， 即\(+\)满足封闭性、结合律、单位元、逆元、交换律

• \(\lt R,\circ\gt\)构成半群， 即\(\cdot\)满足封闭性、结合律、单位元

• \(\circ\)对\(+\)有分配率，即\(a\circ(b+c)=a\circ b+a\circ c\)

比赛链接

https://ac.nowcoder.com/acm/contest/16151?&headNav=www

D. Fake News

题意

输入一个数\(n\)，问你\(\begin{aligned}\sum_{i=1}^n i^2\end{aligned}\) 是不是一个完全平方数。

数据范围

\(10^6\)组输入

\(n\lt 10^{15}\)

题解

前缀和为\(\frac{n\cdot(n+1)\cdot(2n+1)}{6}\), 由于\(n\)，\(n+1\)，\(2n+1\)两两互质，所以他们排除掉\(2\)和\(3\)这两个因子以后是完全平方数。直接验证这个就可以了。

H. Dividing

题意

• (1,k)合法
• 如果(n,k)合法，则(n+k,k)合法
• 如果(n,k)合法，则(nk,k)合法

输入\(N\),\(K\), 问你有多少组\(1\le n\le N,1\le k\le K\)合法。

题解

显然每个\(k\)都是独立的。

考虑n的k进制，很容易发现第一句话说的是\(1\)合法，第二句话说的是合法的数加上\(10\)合法，第三句话说的是合法的数左移一位合法。

所以很容易发现，只要最低位为0或者1，就是合法的。

然后就是一个分块的模版题了。计算\(\begin{aligned}\sum_{i=1}^K \sum_{j=1}^N [j\mod i\le 1]\end{aligned}\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int mod = 1e9 + 7;

// [0,n] sum n/i
ll cal(ll k, ll n) {
    ll ans = 0, pos;
    // i=1, min(n,k)
    for (ll i = 1; i <= min(n, k); i = pos + 1) {
        pos = n / (n / i);
        pos = min(pos, min(n , k));
        //doing something
        ans += (pos - (i - 1)) * (n / i);
        ans %= mod;
    }
    // i=min(n,k)+1 , k
    return ans;
}

ll cal2(ll k, ll n) {
    if(k == 1) {
        return 0;
    }
    ll ans = 0, pos;

    for (ll i = 2; i <= min(n - 1, k); i = pos + 1) {
        pos = (n - 1) / ((n - 1) / i);
        pos = min(pos, min(n - 1, k));
        //doing something
        ans += (pos - (i - 1)) * ((n - 1) / i);
        ans %= mod;
    }
    ans += k-1;
    return ans % mod;
}

int main() {
    ll n, k;
    scanf("%lld %lld", &n, &k);
   // cout << cal(k, n) << " " << cal2(k, n) << endl;
    ll ans = (cal(k, n) + cal2(k, n));
    printf("%lld", ans % mod);
}

B. Mask Allocation

题意

给你\(n\times m\)个口罩，你可以对口罩进行分组，要求分组后可以在不拆开组的情况下，分配给n个医院。每个医院m个口罩，也可以分配给m个医院，每个医院n个口罩。

数据范围

\(100\)组输入

\(1\le n,m \le 10^4\)

题解

不妨考虑\(n<m\), 那么我们直接分出n个n，那么后面剩余\(n\times m-n\times n\)个口罩，要求可以分成\(m-n\)个n，以及n个\(m-n\)，注意到出现了子问题。所以递归解决。

公式

\[ g(1)\sum_{i=1}^nf(i)=\sum_{i=1}^{n}(f*g)(i)-\sum_{d=2}^{n}g(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i) \]

使用

很多时候我们会碰到求积性函数前缀和的情况，由于积性函数的前缀和不一定依然是积性函数，所以我们需要使用一些技巧。

比如给你一个积性函数\(f(x)\), 现在要求你计算\(\begin{aligned}\sum_{i=1}^n f(x)\end{aligned}\)。