P5880

2021CHD · 2025-01-21 19:49:36 · 题解

前言

这篇题解有完整的构造方案及证明，位于参考实现之后。

题目大意

有 n 种图形。第一种图形是直线，有 a_1 条。第二种图形是圆，有 a_2 个。第 x(x\ge3) 种图形是正 x 边形，有 a_x 个。

将所有的图形全部画到一个平面内，求这个平面最多被划分为多少个面积非零的部分，答案对 10^9+7 取模。

解决方式

先友情赠送一张样例二的解释。

然后观察这是怎么画出来的。

首先两个图形不能完全重合，这是废话。

仔细观察，如果正多边形的边之间或者正多边形的边与直线之间存在重合的情况，那一定是不优的。

不难发现，如果两个图形间只有至多一个交点（两条直线除外）或者两条直线相互平行，也是不优的。

而且三个（或以上）图形共点的情况也是不优的。（移动其中一个图形会使区域数增加）

在上面的条件限制下，如果新加入的一个封闭图形（圆或正多边形）与原有的图形交点个数为 x(x>0)，那么这个封闭图形被 x 个交点分割成的 x 个部分各会把原本存在的一个区域切成两份，所以交点数就等于新增区域数，但有一种特殊情况：如果平面上原本什么都没有，加入一个封闭图形可以在不产生交点的前提下将原本完整的平面切成两部分（内部和外部）。

例如上图中加粗的圆，它与其他图形相交形成了 6 个交点，这 6 个交点间夹了 6 段弧，每段弧都将原本存在的一个区域切成了两半。（比如 5 号弧将原本位于外部的无限大的区域切成了两半）

如果新加入的一条直线与原有的直线交点个数为 x，那么这条直线被 x 个交点分割成的 x+1 个部分各会把原本存在的一个区域切成两份，由于直线不是封闭图形，所以要先单独考虑直线，否则可能会存在直线的两段一起将一个区域（第一次加入直线时最外侧的无限大的那个区域，前提是平面中已有封闭图形）切成两半的情况导致计数错误。

容易发现，直线与直线之间最多只有一个交点，直线和圆之间最多有两个交点。由于正多边形是凸多边形，所以直线和正多边形之间最多也只有两个交点。

圆和正 x 边形之间最多有几个交点呢？由于正 x 边形由 x 条线段组成，每条线段都最多与圆有两个交点，所以圆和正 x 边形之间最多有 2x 个交点。具体的，画一个以正多边形的中心为圆心，半径比正多边形的外接圆小、比正多边形的内切圆大的一个圆就可以取到 2x 个交点的上界。

正 x 边形和正 y 边形 (x\le y) 之间最多有几个交点呢？

同样地，由于正 x 边形由 x 条线段组成，每条线段都最多与正 y 边形有两个交点，所以正 x 边形和正 y 边形之间最多也有 2x 个交点。具体的，共用外切圆且不共用顶点的正 x 边形和正 y 边形之间就可以取到 2x 个交点的上界。

下面这张图展示了上面所说的画法看起来的效果。

最后，由于这些图形是任意画的，所以我们认为可以在满足上面的条件（没有线段重叠以及三个图形共点）的前提下使得两两图形间的交点个数都取到最大值。

那么最后需要注意的几个点就是：

• 答案要对 10^9+7 取模，别忘了，也别忘了开 long long。
• 空间限制不够把输入存下，要边输入边处理，具体地，可以记录一个前缀和 x 表示前面的图形（除了圆）一共会给每个新增的图形提供几个交点，再记录圆的数量就好了。

时间复杂度：O(n)。

空间复杂度：O(1)。

参考实现

这是我的 AC 记录。

下面贴上了我自己写的代码。

#include<cstdio>
using namespace std;
const long long mod=1000000007;
long long n,ans=1,cnt,i,a,w,bj; 
main()
{
    scanf("%lld",&n);
    scanf("%lld",&a);
    ans=ans+a*(a+1)/2;
    cnt=cnt+2*a;
    if(a>0)
    bj=1;
    if(n>1)
    {
        scanf("%lld",&w);
        ans=ans+w*cnt+w*(w-1);
        if(bj==0&&w>0)
        {
            ans++;
            bj=1;
        }
    }
    if(n>2)
    {
        for(i=3;i<=n;i++)
        {
            scanf("%lld",&a);
            ans=(ans+a*cnt+a*w*i*2+a*(a-1)*i)%mod;
            cnt=(cnt+a*i*2)%mod;
            if(bj==0&&a>0)
            {
                ans=(ans+1)%mod;
                bj=1;
            }
        }
    }
    printf("%lld",ans);
}

那么这道题到这里就……

友情提示：下面这写部分完全不看也丝毫不会影响你 AC 这道题。

构造方案

是的，这道题现有的六篇题解都没有考虑的一个问题就是：为什么图形两两之间交点数量一定可以全部取到上界？

虽然不论从直觉上还是从概率上讲，这样的方案几乎一定会存在，但是还是没有说明这样的方案一定存在。

接下来的部分将给出并证明一种画图的方式使得图形两两之间交点数量全部都取到上界。

由于正多边形最难画，那么首先就应该考虑如何画出两两之间交点数量全部都取到上界的任意的正多边形。

首先，再次思考怎样画才能使两个正多边形之间的交点数取到最大值。

除了共用外接圆不共用顶点的方式，还有共用内切圆不共用切点的方式，容易说明这样的交点数是取到最大值的。

所以只要让所有正多边形共用内切圆并且不共用切点就可以使所有正多边形两两交点数达到最大，像这样。

那为什么不会有三个正多边形交于一点呢？

考虑交点处，如果有三个正多边形以不同的角度交于一点，由于所有的正多边形共用内切圆，所以过这个点可以做出三条圆的切线（就是三个正多边形的边所在的直线），显然由于过圆外一点只能作两条圆的切线，所以这是不可能的。

那么只要把圆和直线以某种方式补上就可以完成构造了。

那么接下来就是完整的构造方案。

以下用弧度制表示角。

假设要求在平面上画 a 条直线，b 个圆，c 个不超过 d 条边的正多边形，要保证 b>0 且 c>0，具体地，第 i(1\le i\le c) 个正多边形是正 s_i(3\le s_i\le d) 边形（序列 s 单调不递减，且 s_c=d），要使交点数尽可能多。

如果不需要画正多边形，那么将 c 视为 1，将 d 视为 3，再将 s 视为 (3)，最后再将多画的正三角形擦掉即可。同理，如果不需要画圆，那么将 b 视为 1，最后再将多画的圆擦掉即可。

首先在平面上建立平面直角坐标系，然后过原点画出半径为 1 的圆。（这些是辅助线）

接下来在第一象限的圆上取 c 个点使得第 i(1\le i\le c) 个点与原点的连线与 y 轴间所夹锐角为 \frac{i}{cd^2}，然后以每个点作为切点分别作一个圆外切正多边形，具体地，以第 i 个点作为切点的正多边形是正 s_i 边形。

接下来画出 b 个圆，每个圆的半径均为 1+\frac{1}{20c^2d^4}，第 i(1\le i\le b) 个圆的圆心坐标是 (\frac{i-1}{40bc^2d^4},0)。

最后如果 a>0，画出 a 条直线，第 i(1\le i\le a) 条直线的解析式为 y=bc^2d^410^{i+2}x+\frac{a-i}{2a}。

最后将辅助线（平面直角坐标系的坐标轴、以原点为圆心，半径为 1 的圆以及可能存在的多画的正三角形和圆）擦掉就画完了。

下面是两个样例画出来的效果。

样例一：a=1，b=1，c=2，d=4，s=(3,4)。

样例二：a=1，b=2，c=3，d=3，s=(3,3,3)。

什么，你说你看不到两个圆？这两个圆半径相同，圆心只相距 \frac{1}{29160}，肯定是看不清的……

证明

关于上面这种做法，我有一个绝妙的证明，由于这里位置很大，所以我可以把它完整地写在这里。

首先是正多边形之间的夹角。

为什么夹角要是 \frac{1}{cd^2} 呢？

首先夹角最大的是第一个和最后一个多边形，夹角小于 \frac{1}{d^2}，我将说明这个夹角是充分小的。

首先我们假想一种情况：所有正多边形与单位圆的切点都是 (0,1)，那么画出图应该是这样的：（图上画了正 3 到 1000 边形）

此时我们考察这些多边形与单位圆的切点在哪些地方。

容易发现正 m 边形与单位圆的切点一共有 m 个，有一个位于 (0,1)，所有的 m 个切点将单位圆 m 等分，也就是说，如果从圆心向这 m 个切点连接射线，那这些射线与 y 轴正半轴所夹的角就会是 \frac{2\pi i}{m}(0\le i<m)。

那么如果考虑所有的正 3\sim d 边形与圆的切点，从圆心向这些切点连接射线，那这些射线与 y 轴正半轴所夹的角就会是 \frac{2\pi n}{m}(0\le n<m\le d,m\ge3)。这些夹角中除去完全相同的，两两之间的差值不会小于 \frac{2\pi}{d-1}-\frac{2\pi}{d}=\frac{2\pi}{d^2-d}>2\times\frac{1}{d^2}，所以上面所说的 \frac{1}{d^2} 的夹角显然是充分小的，旋转这个角度不会让任何一个正多边形的切点转过另一个正多边形的另一个切点，甚至不会转过一半的间距。

那么就可以说明这些正多边形与圆的切点一定不会重叠，因为原本重叠的切点被正多边形间的夹角岔开了一个角度，而且由于岔开的角度充分小，所以任何原本不重叠的两个切点在旋转后不会重叠，也就是说，这些正多边形画得一定是对的。

你可能已经发现了，没有一个正多边形的偏移是零，也就是说，这样做可以在原本的每个切点附近留出一个至少 \pm \frac{1}{cd^2} 的空位，没有任何正多边形与单位圆的切点会位于这些空位处，圆和直线的画法正是靠这些空位才能成立的。

首先 (0,1) 处一定是一个原本的切点，(0,-1) 处在 d>3 时也一定是一个原本的切点（注意我们不仅考虑真正要画的正多边形，还考虑其他边数在 3\sim d 之间的正多边形），由于原本的切点附近会有一个空位，所以 (0,1) 和 (0,-1) 附近一定不会有正多边形的切点。（显然当 d=3 时 (0,-1) 附近也不会有正多边形的切点）

那么只要将圆的交点放到 (0,1) 和 (0,-1) 附近就没有问题。现在问题就是圆的半径要设多大，圆心要放在哪里，一个自然的想法就是圆心放在原点附近，半径比 1 略大一点。

那么就要考察半径要比 1 大多少，如果大得太多，可能就会有经过两个多边形的交点的可能性，于是考虑将所有多边形的交点都放到圆外。

最接近原点的哪些多边形的交点肯定都是单位圆相邻的切点引出的切线的交点，由于上面说明 \frac{1}{d^2} 是充分小的，所以相邻两个切点与原点的连线之间的夹角不会小于 \frac{1}{cd^2}。

那么半径要画多大呢？请看下面这张图下面是我将样例二绘制得到的图片在 (0.075,1) 附近放大的结果。

在这幅图上可以清晰（？）地看到蓝色的线是紫色的圆的割线，但是蓝色的线与红色和绿色的线的交点都在紫色的圆外。

在这幅图上画上一些辅助线就可以帮助我们的计算。

现在上面画上了一个橙色散点围成的单位圆和黑色虚线围成的直角三角形（三个顶点分别为原点、蓝线和红线的交点以及蓝线和单位圆的切点，原点在画面外），容易得知图上这个直角三角形较小的锐角（顶点是原点）的大小是 \frac{1}{2cd^2}，对边（画面中完整展示的边）长为 \tan(\frac{1}{2cd^2})>\frac{1}{2cd^2}，斜边（画面中靠左的边）长为 \sqrt{1^2+\tan^2(\frac{1}{2cd^2})}>\sqrt{1^2+(\frac{1}{2cd^2})^2}=\sqrt{1+\frac{1}{4c^2d^4}}>\sqrt{1+\frac{1}{5c^2d^4}+\frac{1}{100c^4d^8}}=1+\frac{1}{10c^2d^4}>1+1.5\times\frac{1}{20c^2d^4}，考虑到 cd^2\ge9，上述推导应该是没有问题的。这也说明了 \frac{1}{20c^2d^4} 是充分小的，圆的半径取到 1+\frac{1}{20c^2d^4} 可以使得每个圆内都一定没有多边形的交点。

由于有多个圆，所以第一个圆的圆心位于原点处，后面每个圆的圆心向右移动 \frac{1}{40bc^2d^4}，所以最右边的圆与第一个圆之间的偏移量小于 0.5\times\frac{1}{20c^2d^4}，也就是说，最右边的圆仍与最左边的边保持有两个交点，而不包含位于最右边的正多边形的交点。

圆与圆的交点都位于 (0,1) 和 (0,-1) 附近（距离小于 \frac{1}{20bc^2d^4}），并且这附近不存在多边形之间的交点，甚至不存在多边形的边（因为 \frac{1}{20bc^2d^4} 是充分小的并且在 (0,1) 和 (0,-1) 附近不存在正多边形于单位圆的切点），所以圆和圆之间的交点不可能在正多边形上。

由于所有圆的半径相同，圆心位于同一直线上，假设有三圆交于一点，则该点与直线上的三个点距离都相同，这是不可能的（因为直线和圆最多只有两个交点），然后又由于这些圆之间明显两两相交（0<\frac{1}{40bc^2d^4} 且 \frac{1}{40c^2d^4}<1+\frac{1}{20c^2d^4}），所以这些圆画得一定是对的。

最后就是直线了（如果直线存在的话），可以考虑利用 (0,1) 和 (0,-1) 附近的空位画出一些斜率超大的直线，但是还要保证正多边形的交点不会离 y 轴太近，可以参考上面给出的那个画了很多圆外切正多边形的图。

考虑 y 轴的正半轴，显然只有所有正多边形最上面的一条边会经过 y 轴正半轴，而这些边的交点又全部位于第一象限，离 y 轴距离至少为 \frac{1}{2d^2}<\sin(\frac{1}{d^2})（考虑到 d^2 至少为 9），所以 y 轴的正半轴附近 \frac{1}{2d^2} 范围内是没有正多边形的交点的。

再考虑 y 轴的负半轴。发现如果 x 是偶数，那么正 x 边形也只有最下面一条边会经过 y 轴负半轴，情况和正半轴类似，不再过多探讨。

如果 x 是奇数，那么正 x 边形有一个顶点位于最下方，那么对于一个固定的奇数 x，就应该会在正 x 边形最下方的顶点附近存在交点，但是和 y 轴的距离至少为 \frac{1}{4d^2}<\sin(\frac{1}{2d^2})（同样考虑到 d^2 至少为 9）。由于正多边形旋转的角度 \frac{1}{d^2} 是充分小的，而且在旋转之前在 y=-1 这条直线以下的部分本来就是没有任何交点的，所以不存在某个奇数 x_1 与另一个奇数 x_2 使得在旋转之后正 x_1 边形与正 x_2 边形在下方产生了新的交点。（旋转前不存在交点就是因为对于奇数 x，x 越大，正 x 边形最靠下的与单位圆的切点就越靠下，同时内角也越大，旋转后交点间的相对顺序没有发生改变，所以结论仍成立）

所以就是要考虑对于奇数 x_1 和偶数 x_2，正 x_1 边形和正 x_2 边形最靠下的交点的位置，然而这种情况其实不用考虑，因为正 x_1 边形最下方的顶点附近的交点一定比正 x_1 边形和正 x_2 边形最靠下的交点更接近 y 轴，（对于正 x_1 边形最下面的一部分（最下面的顶点连接的两条边）而言，基本上越靠下越接近 y 轴，只有在 y 坐标相差不多（\frac{1}{x_1d^2} 级别）的时候才可能会有反例，而正 x_1 边形与正正 x_2 边形最靠下的交点的 y 坐标最多也只比 -1 小一点点，正 x_1 边形最靠下的顶点的 y 坐标则是比 -1 小得多（偏移量远大于 \frac{1}{x_1d^2}））所以正多边形之间的交点离 y 轴的距离不会小于 \frac{1}{4d^2}，并且 y 坐标的范围显然在 \pm2 内，但在 \pm1 外。

由于圆与多边形的交点离 y 轴的距离也不会小于 \frac{1}{4d^2}，所以只用考察圆与圆之间的交点，显然圆与圆之间的交点离 y 轴的距离不会小于 \frac{1}{80bc^2d^4}，所以直线的斜率只要足够大就可以完全避免与上面这些交点相碰，这里斜率最小的直线的斜率取到了 1000bc^2d^4，是充分大的。

现在只要让直线与直线之间的交点全部位于单位圆内且不存在三线共点就大功告成了。

于是令直线与 y 轴的交点的纵坐标在 [0,\frac{1}{2}) 的范围内，直线解析式的常数项 \frac{a-i}{2a} 可以保证这一点。

而相邻两条直线的斜率相差 10 倍，而且越往下斜率越大，可以保证第 i 条直线与第 j 条直线 (1<i<j\le a) 的交点位于第 i-1 条直线与 y 轴的交点下方，且第 1 条直线与第 i(i>1) 条直线的交点位于圆内。

具体地，只需求出第 i 条直线与第 i+1 条直线的交点纵坐标即可。联立 y=bc^2d^410^{i+2}x+\frac{a-i}{2a} 与 y=bc^2d^410^{i+3}x+\frac{a-i-1}{2a} 即可解得 y=\frac{a-i}{2a}+\frac{1}{18a}<\frac{a-i+1}{2a}<1，则上述说法成立。

综上，这种方案在不产生重叠以及三个图形共点的前提下，直线、圆及正多边形两两之间的交点数均取到最大值，则这题的结论成立。

后记

一不小心就写了 9k+，能看到这里也是真不容易。如果有什么疏漏的话可以在评论区指出，如果可以的话，我会在第一时间改正。

也不知道有没有人看完了呢？如果真的有，那一定是真正对这门学科怀着热爱的人吧。

不过，不论从直觉上还是从概率上讲，这样的人几乎一定会存在。

最后一点空白就留给你们自己探索吧：