2019.5.29

Veröffentlicht am

学不下去了，要退赛了，暑假不来了—xxx三连

说个题外话，IEEE ban了HUAWEI，这可真是太学术自由了。

[TJOI2019]唱、跳、rap和篮球

题目背景

TJOI2019 D1T3
源文件名：queue.*
时间限制: 4s 内存限制: 128M

题目描述

大中锋的学院要组织学生参观博物馆，要求学生们在博物馆中排成一队进行参观。他的同学可以分为四类：一部分最喜欢唱、一部分最喜欢跳、一部分最喜欢rap，还有一部分最喜欢篮球。如果队列中$k$,$k + 1$,$k + 2$,$k + 3$位置上的同学依次，最喜欢唱、最喜欢跳、最喜欢rap、最喜欢篮球，那么他们就会聚在一起讨论蔡徐坤。大中锋不希望这种事情发生，因为这会使得队伍显得很乱。大中锋想知道有多少种排队的方法，不会有学生聚在一起讨论蔡徐坤。两个学生队伍被认为是不同的，当且仅当两个队伍中至少有一个位置上的学生的喜好不同。由于合法的队伍可能会有很多种，种类数对$998244353$取模。

输入输出格式

输入格式：
输入数据只有一行。每行$5$个整数，第一个整数$n$，代表大中锋的学院要组织多少人去参观博物馆。接下来四个整数$a$、$b$、$c$、$d$，分别代表学生中最喜欢唱的人数、最喜欢跳的人数、最喜欢rap的人数和最喜欢篮球的人数。保证$a+b+c+d \ge n$。
输出格式：
每组数据输出一个整数，代表你可以安排出多少种不同的学生队伍，使得队伍中没有学生聚在一起讨论蔡徐坤。结果对$998244353$取模。
输入输出样例

输入样例#1：
4 4 3 2 1

输出样例#1：
174

输入样例#2：
996 208 221 132 442

输出样例#2：
442572391

说明

对于20%的数据，有$n=a=b=c=d\le500$
对于100%的数据，有$n \le 1000$ ， $a, b, c, d \le 500$

题解

和wzx在路上讨论出了做法。

容斥，枚举$k$表示至少$k$组讨论cxk的同学，它对答案的贡献为两部分相乘：

在$n$个同学的序列中放置$k$组讨论cxk的同学，这个可以简单dp出来：$dp{i,j}=dp{i-1,j}+dp_{i-4,j-1}$

不一定讨论cxk的同学如何排列，即从人数分别为$a-4k,b-4k,c-4k,d-4k$（以下记作$A,B,C,D$）的4组同学中选出总数为$n-4k$（以下记作$N$）的同学。

如果$A+B+C+D=N$，那么就是可重排列问题，答案为$\frac{N!}{A!B!C!D!}$。
如果$A+B+C+DN$呢？那么我们就枚举$=N$的部分，答案为：
$\sum\limits{i=0}^A\sum\limits{j=0}^B\sum\limits{k=0}^C\sum\limits{l=0}^D[i+j+k+l=N]\frac{N!}{i!j!k!l!}$
$=N!\sum\limits{i=0}^A\sum\limits{j=0}^B\sum\limits{k=0}^C\sum\limits{l=0}^D[i+j+k+l=N]\frac 1{i!}\frac 1{j!}\frac 1{k!}\frac 1{l!}$
卷积！NTT！
$O(n^2 log n)$

抄题解复习Mobius Inversion.jpg

[国家集训队]和与积

题目描述

给出$N$，统计满足下面条件的数对$(a,b)$的个数：

$1\le ab \le N$
$a+b$整除$a\times b$

$ n \leq 2^{31}-1$

输入输出格式

输入格式：
一行一个数$N$
输出格式：
一行一个数表示答案
输入输出样例

输入样例#1：
15

输出样例#1：
4

solution

设

那么由同余的线性法则，可以得出

根据$(X,Y)$的定义，不难得出以下结论：
结论 1.1：$(k1,k_2)=1$
证明：反证法。设$(k_1,k_2)=u1$，那么定有$uG | a$,$uG | b$，即存在一个更大的数$uG$为$a,b$的公因数，与$G$为最大公因数矛盾。
结论 1.2：$(k_1,k_1+k_2)=(k_2,k_1+k_2)=1$
证明：由结论1.1 可知，$(k_1,k_2)=1$因此$k_1+k_2$一定不能整除$k_1,k_2$，即最大公因子为1.
结论1.3：$(k_1k_2,k_1+k_2)=1$
证明：由结论1.1 可知，$k_1k_2$的公因子只有$k_1,k_2$，由结论1.2 ，可知其一定与$k_1,k_2$互素。
结论1.4：$(k_1+k_2)\mid G$
证明：由结论1.3可知，$k_1k_2\nmid G$。因为$(k_1,k_2)|k_1k_2G$，因此必有$(k_1+k_2)\mid G$
由结论1.4，我们要想办法找出满足这个解的$G$有多少个。不妨设最小的一个为$G_0$。由整除的定义，必有$G_0=k_1+k_2$，且$G=\delta G_0, \delta\in\mathbb N+$。因此，
即对于一组$(k_1, k_2)$，其解的数量恰好为$\left\lfloor\dfrac{N}{\max(k_1,k_2)(k_1+k_2)}\right\rfloor$。
结论 2.1：对于一组$(k_1,k_2)$，共有$\left\lfloor\dfrac{N}{\max(k_1,k_2)(k_1+k_2)}\right\rfloor$。组解
有以下不等式组。

考虑第三个不等式，我们把两边都乘$k_2$

这将是另一个重要的结论
结论3.1：$k_2(k_1+k_2)\leqslant N$
考虑到，由于$k_11$，因此

即$k_2\leqslant \sqrt N$
结论3.2：$k_2 \leqslant \sqrt N$
由于$N\leqslant 2^{32}-1$，因此我们可以尝试枚举$k_2$。应用结论2.1，可得：

由于$k2k_1$，因此可以通过替换得到以下结论。
结论4.1：ans = $\sum^{\sqrt N}{k1=1}\sum^{\sqrt N} {k_2=k_1+1}\left[(k_1,k_2)=1\right]\left\lfloor\frac{N}{k_2(k_1,k_2)}\right\rfloor$
时间复杂度为$O(n\log n)$，个人得分为55分。
下面，考虑Möbius 反演。根据常识

因此，不难进行Möbius反演

考虑将后面含Möbius函数的和式提前：

（$\delta^2$的来历不难思考）
此时，时间复杂度似乎不那么显然了。第一个和式显然执行了$\sqrt N$次，而后面的，每个执行了

取$\lim\limits_{n\to\infty}$，由调和级数求和公式，可知

因此，整个方法的时间复杂度为$O(\sqrt n\log^2 n)$。能得到70分。
考虑继续进行优化。令$\beta=i+j$，则可以得出以下式子：

根据组合数学与求和技巧，复杂度是$O(\sqrt{n}logn)$

话说指针优化寻址确实快不少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int maxn = 200005;
bool vis[maxn];
int prime[maxn], mu[maxn];
inline void init_mu(int n) {
    int cnt = 0;
    *(mu + 1) = 1;
    for (int i = 2; i < n; i++) {
        if (!*(vis + i)) {
            *(prime + cnt++) = i;
            *(mu + i) = -1;
        }
        for (int j = 0; j < cnt && i* *(prime + j) < n; j++) {
            *(vis + i* *(prime + j)) = 1;
            if (i % *(prime + j) == 0) { *(mu + i* *(prime + j)) = 0; break; }
            else { *(mu + i* *(prime + j)) = - *(mu + i); }
        }
    }
}

题目背景

WD整日沉浸在积木中，无法自拔……

题目描述

WD想买$n$块积木，商场中每块积木的高度都是1，俯视图为正方形（边长不一定相同）。由于一些特殊原因，商家会给每个积木随机一个大小并标号，发给WD。
接下来WD会把相同大小的积木放在一层，并把所有层从大到小堆起来。WD希望知道所有不同的堆法中层数的期望。两种堆法不同当且仅当某个积木在两种堆法中处于不同的层中，由于WD只关心积木的相对大小，因此所有堆法等概率出现，而不是随机的大小等概率（可以看样例理解）。输出结果mod 998244353即可。
（如果还是不能够理解题意，请看样例）

输入输出格式

输入格式：
第一行一个数$T$，表示询问个数。
接下来$T$行每行一个数$n$，表示WD希望使用$n$块积木。
输出格式：
共$T$行，每行一个数表示答案mod 998244353。
输入输出样例

输入样例#1：
4
1
2
3
4

输出样例#1：
1
665496237
307152111
186338949

说明

接下来用大括号表示分在一层。
对于$n=1$，合法的分法只有$\{1\}$；
对于$n=2$，合法的序列有$\{1,2\}$，$\{1\}\{2\}$，$\{2\}\{1\}$，期望层数为$\frac{1+2+2}{3}=665496237(mod~998244353)$；
对于$n=3$，合法的序列有$\{1\}\{2\}\{3\}$，$\{1\}\{3\}\{2\}$，$\{2\}\{1\}\{3\}$，$\{2\}\{3\}\{1\}$，$\{3\}\{1\}\{2\}$，$\{3\}\{2\}\{1\}$
$\{1,2\}\{3\}$，$\{1,3\}\{2\}$，$\{2,3\}\{1\}$，$\{1\}\{2,3\}$，$\{2\}\{1,3\}$，$\{3\}\{1,2\}$，$\{1,2,3\}$共13种。因此期望就是$\frac{6\times3+6\times2+1}{13}=307152111(mod~998244353)$
对于$n=4$，我想到了一个绝妙的解释，可惜这里写不下。
$subtask1(21pts):~1\le T\le 1,000,~1\le n\le 1,000$
$subtask2(37pts):~1\le T\le 10,~1\le n\le 100,000$
$subtask3(42pts):~1\le T\le 100,000,~1\le n\le 100,000$

题解

NTT水题。并不知到题意为什么很罗嗦，越描越黑的感觉

当初比赛不会NTT不过找规律出来分母是Bell Number分子是个简单和。

这里递推+生成函数推一推。

设$f_n$为$n$个积木能搭出的方案数，$g_n$为所有方案的高度之和。
由递推关系（枚举一个塔高度化归）：

发现$f_n$似乎更容易搞出来，我们先搞$f_n$。
由转移方程可以得到：

设

则有

多项式求逆即可。
接下来是求$g_n$。
令$t_n=f_n+g_n$，则有

设

可以得到

NTT即可。
最后$ans_n=\frac{g_n}{f_n}$。

注意$n=0$的时候$f_n$是1，我RE了。。常数项是1.

学了一种其它做法。

由于是选出积木有标号，所以使用指数型生成函数

显然每一层的生成函数为 $F(x)=\displaystyle\sum{k=1}^{\infty}\dfrac 1{k!}x^k=e^x-1$
枚举层数，答案即为 $\displaystyle\sum{k=0}^{\infty}F^k(x)=\dfrac 1{1-F(x)}=\dfrac 1{2-e^x}$
接下来求所有方案的层数总和
枚举层数，答案即为 $\displaystyle\sum_{k=0}^{\infty}kF^k(x)=\dfrac {F(x)}{(1-F(x))^2}=\dfrac{e^x-1}{(2-e^x)^2}$

NTT+求逆即可。

CF70D Professor’s task

两种操作:

  • 1 往点集S中添加一个点(x,y);
  • 2 询问(x,y)是否在点集S的凸包中. 数据保证至少有一个2操作, 保证刚开始会给出三个1操作, 且这三个操作中的点不共线.

$q \leq 10^5$

Solution

动态凸包。

静态凸包

将各点坐标按 $x$ 从小到大排序
分别维护上凸壳和下凸壳。注意到如果之前有两点 $A$ 和 $B$ ，当插入新节点 $C$ 时，以上凸壳为例，如果 $\overrightarrow{AB} \times \overrightarrow{AC} \ge 0$ 时，这说明 $B$ 在线段 $AC$ 的下方，就可以将 $B$ 删除。我们可以看出此时凸包是一个类似单调栈的结构。

排序过程是算法的瓶颈，效率 $\Theta(n \log n)$。而后面的构建是 $\Theta(n)$ 的。
从上面的启发我们可以找到一种动态维护凸包的方法。
用 $\texttt{std::map}$ 维护上下凸壳， $x$ 为第一关键字， $y$ 为第二关键字。在插入一个新的点到凸壳上时，检查它周围的点是否可以被删掉，用与静态凸包类似的方法判断。
虽然插入一个点时可能删除若干个点，但注意到每个点只有在被删除时才会多贡献这 $\mathcal O(\log n)$ 的时间，所以本算法复杂度$O(nlogn)$

然后不会用迭代器看了半天std(放一个觉得写的可以的std

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <cstdio>
#include <cmath>

#include <algorithm>
#include <map>

typedef std::map<int, int> map;
typedef map::iterator iterator;
typedef int num;
typedef long long ll;

map top, down;

ll det(int x1, int y1, int x2, int y2);
bool check_top(int x, int y);
bool check_down(int x, int y);
bool remove_top(iterator it);
bool remove_down(iterator it);
void insert_top(int x, int y);
void insert_down(int x, int y);

int main() {
    int q, op, x, y;
    scanf("%d", &q);
    while (q--) {
        scanf("%d%d%d", &op, &x, &y);
        if (op == 1) {
            insert_top(x, y);
            insert_down(x, y);
        } else
            puts((check_top(x, y) && check_down(x, y)) ? "YES" : "NO");
    }
    return 0;
}

void insert_top(int x, int y) {
    if (check_top(x, y))
        return;
    top[x] = y;
    iterator it = top.find(x);
    iterator jt = it;
    if (it != top.begin()) {
        --jt;
        while (remove_top(jt++))
            --jt;
    }
    if (++jt != top.end())
        while (remove_top(jt--))
            ++jt;
}

ll det(int x1, int y1, int x2, int y2) {
    return (ll)x1 * y2 - (ll)x2 * y1;
}

void insert_down(int x, int y) {
    if (check_down(x, y))
        return;
    down[x] = y;
    iterator it = down.find(x);
    iterator jt = it;
    if (it != down.begin()) {
        --jt;
        while (remove_down(jt++))
            --jt;
    }
    if (++jt != down.end())
        while (remove_down(jt--))
            ++jt;
}

bool remove_top(iterator it) {
    if (it == top.begin())
        return false;
    iterator jt = it, kt = it;
    --jt;
    ++kt;
    if (kt == top.end())
        return false;
    if (det(it->first - jt->first, it->second - jt->second, kt->first - jt->first, kt->second - jt->second) >= 0) {
        top.erase(it);
        return true;
    }
    return false;
}

bool remove_down(iterator it) {
    if (it == down.begin())
        return false;
    iterator jt = it, kt = it;
    --jt;
    ++kt;
    if (kt == down.end())
        return false;
    if (det(it->first - jt->first, it->second - jt->second, kt->first - jt->first, kt->second - jt->second) <= 0) {
        down.erase(it);
        return true;
    }
    return false;
}

bool check_top(int x, int y) {
    iterator it = top.lower_bound(x);
    if (it == top.end())
        return false;
    if (it->first == x)
        return y <= it->second;
    if (it == top.begin())
        return false;
    iterator jt = it;
    --jt;
    return det(it->first - jt->first, it->second - jt->second, x - jt->first, y - jt->second) <= 0;
}

bool check_down(int x, int y) {
    iterator it = down.lower_bound(x);
    if (it == down.end())
        return false;
    if (it->first == x)
        return y >= it->second;
    if (it == down.begin())
        return false;
    iterator jt = it;
    --jt;
    return det(it->first - jt->first, it->second - jt->second, x - jt->first, y - jt->second) >= 0;
}