2019.5.29

学不下去了,要退赛了,暑假不来了—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:$(k_1,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,可得:

由于$k_2k_1$,因此可以通过替换得到以下结论。
结论4.1:ans = $\sum^{\sqrt N}_{k_1=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;
}