HNSDFZ2016 #5

A. 微小的数学 (ruanxingzhi)

题目描述

到了附中我这三年也没有什么别的,大概三件事:一个,算出了$\varphi(n)$了; 第二个,算出了$\mu(n)$; 第三个,就是算出$\varphi \times \mu$了。
如果还说有一点成绩就是科普了杜教筛......还有上周的狄利克雷卷积也是很大的。但这些都是次要的。
我主要干的就是三件事,很惭愧,就做了一点微小的数学。

—— Gromah

现在请你追随Gromah的脚步,来虐掉这个题,做一点微小的数学吧。

—— ruanxingzhi

一句话题意:求：
$$ \sum_{i=1}^n\sum_{d \mid i} \varphi(d) \mu(\frac{i}d) $$

输入格式

仅一行,一个正整数$n$。

输出格式

仅一行,一个正整数,表示答案。

样例输入1

1

13

样例输出1

1

38

样例输入2

1

233

样例输出2

1

10138

数据范围及提示

对于$10\%$的数据,有$n \le 32$。
对于$30\%$的数据,有$n \le 1000$。
对于$50\%$的数据,有$n \le 100000$。
对于$100\%$的数据,有$n \le 50000000$

B. 一圈一圈 (Haogram)

题目描述

“有些事,我都已忘记,但我现在还记得,啦啦啦啦啦......”
“一圈一圈似爪牙,似魔鬼的步伐,啦啦啦啦......”
传闻《我的滑板鞋》作者约瑟翰·庞麦郎即将推出新歌《一圈一圈》,并且mv中要配上鬼畜的舞蹈,于是他贴出了应聘广告,Hagram们自然不想放弃这个赚钱的好机会,毅然决然地前往应聘......

约瑟翰·庞麦郎一共应聘了$k$个Hagram，$k$个Hagram都要参与舞蹈。Hagram们被要求在一个$n$行$m$列的矩阵上跳舞，当然一个格子只能站一个Hagram。为了保证舞蹈的鬼畜性，矩阵的第$c$个圈上必须四边都要有Hagram存在，圈数是从最外层往内数的。
两个舞蹈队形不同当且仅当其中一个方案的一个格子上有Hagram而另一个方案没有。
如果有一个Hagram在某一圈的顶点上，可以认为其既在行上，又在列上。
现在约瑟翰·庞麦郎想知道一共有多少种不同的方案，答案对$10^9+7$取模。

输入格式

对于每组数据，四个数：$n,\;m,\;k,\;c$
当$n=m=k=c=0$时结束。

输出格式

对于每组数据，输出一行一个正整数表示答案。

样例输入

1
2
3
4
5

2 2 1 1
2 2 2 1
3 3 1 2
3 3 2 2
0 0 0 0

样例输出

1
2
3
4

0
2
1
8

数据范围及提示

对于$30\%$的数据，$n,\;m \le 3$，$k \le 10$。
对于$100\%$的数据，$n,\;m \le 50$，$k \le 3 \times 10^3$。
保证$c$合法。

C. KFight (Link)

题目描述

Zy他是一位在异界闻名的勇士。
Zy在知道公主ZY被恶龙BigGayY抓走后，内心及其不平静。
Zy知道他走向人生巅峰，迎娶公主的时候到了。他要去找到BigGayY，然后打摆他。
但是，BigGayY早就知道闻名的勇士Zy会来。
因此倾心于他的公主SAMA找到了他的骑士们阻止Zy的到来。
骑士有$N$个，他们挡在了Zy去打摆恶龙的路上。Zy要想办法打败他们，但是他不能出全力。
不然的话，到时候没力气打摆BigGayY。因此他只能出$K$拳。
骑士们很逗逼，他们有些人会组成团来和Zy战斗，有些人分开和Zy战斗。
作为勇士的Zy很强，他每次一拳都可以打死一个人或者一团人。
但是骑士团里面还有其他的ZY，作为Zy，他不能够去打败这些ZY，这些ZY也不会去阻止他。
作为异界王者的国王，很想知道Zy不能够救出公主的概率是多少，他并不想让Zy找到公主。
因此他找到了你，想知道Zy不能救出公主的概率是多少。

输入格式

第一行一个T表示有T波骑士来阻挡了Zy。
第二行三个数$N,\;K,\;Q$，分别表示每一波有$N$个骑士来袭，Zy只能打$K$拳，然后这一波骑士里面有$Q$个ZY。

输出格式

对于每一波骑士，输出Zy打不过的概率，保留$10$位小数。

样例输入

1
2

1
3 1 0

样例输出

1

0.8000000000

数据范围及提示

注意精度,由于取的小数位很多，注意精度问题。

对于$30\%$的数据有$K \le N \le 4,\;Q = 0,\;T \le 10$。
对于$60\%$的数据有$K \le N \le 20,\;Q \le 10,\;T \le 2000$。
对于$100\%$的数据有$K \le N \le 30,\;Q \le 20,\;T \le 2000$。

D. 空袭 (riteme)

题目描述

这是一道交互题。
注意本交互库不提供Pascal支持。只支持C\C++。

统计学家Lunk所居住的城市遭到的软斯兰国的空袭，弄得Lunk心神不定。
然而伟大的统计学家怎么会就因为空袭而四处避难呢？Lunk决定弄出个大新闻。
由于各种原因，Lunk所居住的城市的市区的形状十分奇怪。Lunk将其大致的轮廓画在地图上，形成了一个多边形的形状。软斯兰国的飞机每丢下一枚炸弹，Lunk就会马上观测到炸弹的位置，并将其画在地图上。但是，他所想要统计的只是智障的软斯兰国有多少枚炸弹攻击到了市区。
于是Lunk放弃了在地图上画下每一个炸弹的位置，而是转而在地下室里直接统计。

现在它所需要的就是一个能帮他统计的程序。他希望能在你们写的程序中选出一个精确度高并且跑得比香港记者还快的程序来帮助它完成这个任务。

我该如何编写这个程序

选手目录下将会下发interface.h这个文件。
你需要实现interface.h中的接口。
你需要在同一目录下新建一个文件airstrike.cpp，其中包含以下内容：

1
2
3

#include "interface.h"

// 实现部分

你需要实现的接口在头文件中有简要说明。这里做详细说明。

1

void initialize(const double *x, const double *y, const size_t n, const int id);

是载入程序的入口。在进行查询之前，会调用这个函数。
载入所用的时间不会计入你的程序用时。但是载入时间不能超过$3\text{s}$。
x和y是两个数组，给出的是市区的轮廓，即Lunk绘制的多边形的顶点，按照逆时针顺序给出。
n是多边形的顶点数量。
id是当前数据点的标号，在下文会有解释。

1

bool query(const double dx, const double dy);

是Lunk的操作，每次调用即查询炸弹是否炸在市区内。如果炸在市区内则返回true，否则返回false。
dx和dy是炸弹炸到的坐标。
该函数的用时会被计入程序用时。

1

void finalize();

是结束程序。这个函数将在所有查询任务完成后调用。
用于释放你的程序所用的资源。
该函数的用时不会计入程序用时，但是其运行时间不能超过$3\text{s}$。
注意，请不要使用delete[]删除掉之前initialize参数中给你的顶点数组，否则后果自负。

我该如何测试这个程序

选手目录下将会下发main.cpp这个文件。
首先你需要有输入的数据，其格式将在下文给出。
假设你的程序文件是airstrike.cpp，那么使用以下命令来编译：

1

g++ main.cpp airstrike.cpp -std=c++11 -o main

或者你需要调试：

1

g++ main.cpp airstrike.cpp -std=c++11 -o main -g

打开-O2优化：

1

g++ main.cpp airstrike.cpp -std=c++11 -o main -O2

对于C语言，将main.cpp改名为main.c，使用gcc，并且将-std=c++11改为-std=c11即可。
然后使用：

1

./main

来运行程序。
如果需要使用文件输入输出，你可以使用管道，也可以修改main.cpp，将其中的两行带有注释的freopen取消注释，然后重新编译即可。
注意，该程序不会测试你的用时并给你评分。并且与最终评测时的运行程序不同。

输入格式

此处的输入格式是根据上面的测试程序所说的。

第一行输入两个整数$n$和$d$，表示顶点数量和数据编号。
下面$n$行描述市区，每一行给出一个整点$(x,\;y)$，表示一个顶点。
之后给出若干行，一直到文件尾，每行给出一个整点$(x_q,\;y_q)$，表示炸弹的位置。

输出格式

对于每一个Lunk的询问，输出对应的信息 (YES或NO)。

样例输入1

1
2
3
4
5
6
7
8
9

3 1
0 0
6 1
8 7

6 5
2 7
8 1
3 1

样例输出1

1
2
3
4

YES
NO
NO
YES

样例解释1

样例输入1如下图所示：

样例输入2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

7 1
1 1
7 1
4 2
3 4
7 5
5 6
1 6

0 4
2 4
4 4
5 3
5 5
3 1

样例输出2

1
2
3
4
5
6

NO
YES
NO
NO
YES
YES

样例解释2

样例输入2如下图所示：

数据限制

共$7$个数据测试点，限制如下：

对于$100\%$的数据，满足$3 \le n \le 10^6,\;|x|,\;|y|,\;|x_q|,\;|y_q| \le 10^9$。
顶点按照逆时针顺序输入，没有两个顶点一样，并且为简单多边形。

评分标准

对于不同的数据点，分值和时间限制如下表所示：

在时间限制内，如果程序不出意外 (如运行时错误)，将会不断的给出询问。设你的程序完成的询问个数为$x$。对于每一个点的评分标准如下：

你的$x$需要达到对应的要求才能得到对应的百分比。评测程序将选取你能达到的最高的百分比。
其中百分比是将该点总分乘上该百分比并向下取整，作为你该点的分数。

如果询问回答错误，将每回答错误一次扣除$1$分，扣分到$0$分为止，分数不会变为负数。
如果发生运行时错误，或者运行严重超时，将导致该点得$0$分。
如果你的initialize或finalize超时，该点得$0$分。

关于评测机

出于一些原因，GCC编译出来的评测器并不是很稳定，可能出现成绩波动的情况，所以评测时最好采用Clang进行编译，得到的结果会稳定一些。
如果你对你的算法十分自信，然而在评测时却没有得到满分，可以进行重测。

温馨提示

评测时限很长，请不要恶意卡评测，谢谢合作！

部分题解

A

raunxingzhi总是喜欢出这种题目，莫名其妙。

首先是$O(n \ln n)$的做法，令：
$$ f(n) = \sum_{d \mid n} \varphi(d) \mu(\frac{n}d) $$

对其进行逆反演，可以得到：
$$ \varphi(n) = \sum_{d \mid n} f(d) $$

所以：
$$ f(n) = \varphi(n) - \sum_{d \mid n,\;d \lt n} f(d) $$

所以欧拉函数可以$\Theta(n)$预处理，而后面的部分可以按照贡献计算，做到$O(n \ln n)$。
mdzz，$O(n \ln n)$怎敢过......

其次是两种更快算法。
第一种是乱搞算法，是一个分块打表。
由于我们计算一个$\sum_{d \mid n} \varphi(d) \mu(\frac{n}d)$就需要$\Theta(\sqrt{n})$的时间，考虑提前将一些答案计算出来。
设每隔$T$个打一个表，那么总共会打$n / T$个表，每次询问的时间为$O(T\sqrt{n})$。因此，只要你的文件存得下，$T$越小这个速度越快。

第二种是$\Theta(n)$的算法。首先考虑将式子变形，改变枚举顺序：
$$ \sum_{i=1}^n \sum_{d \mid i} \varphi(d) \mu(\frac{i}d) \Longrightarrow \sum_{d = 1}^n \varphi(d) \sum_{k = 1}^{\left\lfloor \frac{n}d \right\rfloor} \mu(k) $$

变成了先枚举因子，然后枚举因子的倍数。于是就变成了欧拉函数和莫比乌斯函数的前缀和之积。
注意不要写出以下代码：

1

typedef int int64;

否则会挂得很惨。

B

Haogram的题似乎有很多做法，我都不太记得了，这里瞎BB一下：
我的做法是生成函数。一个最原始的想法是枚举环上四条边有多少个人，这样将四条边上的答案相乘并且乘上站在环外的方案数就是当前答案。
这样纯枚举是$\Theta(n^4)$的。这个过程非常类似于多项式乘法，换成生成函数的观点，就是将答案组合起来。
于是设四个生成函数，分别表示一条边上站$0,\;1,\;2,\;\dots$个人的方案数，实际上就是一个组合数，然后暴力将多项式乘起来 (因为$n$很小)，可以做到$\Theta(n^2)$的复杂度。
如果$n$很大可以换成FFT或NTT。注意使用NTT时，因为题目中已经有了一个模数，所以这两个模数或多或少会有一些冲突，需要注意一下。
然后就是留下四个角的特殊情况。之前我们需要在边上的人不能站在角上。现在来钦定这四个角上有没有人。最后你一共要手动枚举$7$中情况orzorz......
注意其中一条边退化为$1$的情况。

标解是使用容斥原理。因为不考虑那个莫名其妙的要求，直接计数是很简单的。然后就需要考虑去掉不合法的情况。基础情况自然是一条边上没有人。
运用容斥原理乱搞就好了~~只有$4$个条件所以速度很快。

C

你们自己问Link吧，我也不会......

D

原来只要出交互题就可以做到全场爆$\color{red}{0}$，曾经有人出过提答题，结果全场AC......
60分不写就算了，40分智障分也不写你们好劲啊！一颗赛艇啊！

首先百度一下和谷歌一下的第一版的算法基本上就$10$到$20$左右吧。射线法和角度判别法都是$\Theta(n)$的算法。
然后后面$40$分是些智障数据点。第$5$个点是上边会上下起伏，我们可以二分找出对应的边，然后叉积判断即可。
第$6$个点凸多边形可以直接进行三角剖分，然后利用角度二分找到对应的三角形，就可以愉快地判定了。这些过程均可用叉积。
第$7$个点直接在initialize里面全部预处理就OK了。注意查询的点可能不在那个范围内，需要特判一下。

接下来是标准解法。
首先考虑一个离线算法，这个算法我是从梯形化三角剖分里借鉴到的。首先将所有边建立两个事件，左端点插入和右端点删除，然后排序。查询也要排序。
然后做一条从左至右的竖直扫描线，用一棵平衡树来维护当前穿过扫描线的边。
很明显的一点就是平衡树中的边不会相交，这样我们可以方便地确定两条边之间的比较关系。
首先如果一条边的两个端点都在另一条边所在的直线下面，那么这条边肯定在在另一条边下面。
利用这一点就可确定大小关系。但是需要注意一种特殊情况：

此时$A$显然在$B$下面，然而如果用$A$去判定$B$就会得到错误的结果 (因为$B$有一个点在$A$所在直线下方)。
我们所要做的就是，当发现这种情况时，交换$A$和$B$，就可以避免处理这种情况。

这样我们每扫描完一个$x$，就可以逐个回答当前的询问了。在平衡树上二分找到上下边，然后判定这个点是否在这两条边所表示的半平面交的范围内。
由于是交互题，被强制在线了。为了能够在线，我们需要每一个$x$处的平衡树来在线回答。这个东西可以利用可持久化平衡树高效地存下来。