自动搬运

查看原文

来自洛谷，原作者为

	Warriors_Cat 欢迎来到这方净土，这里曾有一位普通人建造着自己的乌托邦。

搬运于2025-08-24 22:15:13，当前版本为作者最后更新于2019-12-21 12:05:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

楼下那个官方题解也是可以……

这才是官方题解!

题目大意：

给你$a_1$条直线，$a_2$个圆，$a_3$个正三边形，$a_4$个正四边形，$a_5$个正五边形......$a_n$个正n边形，问这些图形最多能把一个平面分成多少块。

首先，我们看一下只有直线的情况：

直线数：$1\quad2\quad3\quad4\quad5$

平面数：$2\quad4\quad7\quad11\quad16\quad$

发现没有？如果有$a_1$条直线，那么就可以分割成$\large\frac{a_1*(a_1+1)}{2}+1$个区间。

于是代码如下：

if(i == 1){
    ans = 1 + a * (a + 1) / 2;
    sum += a * 2;//sum1以后会有用 
    ans %= mod;//注意要mod 
}

那么，直线搞定后，我们再来康康圆。

如果刚开始没有直线，那么$a_2$个圆可以分割成$2+a_2*(a_2-1)$个区间。

为什么？

下面来证明一下：

易知一个圆时可以分成2个部分，那此时多加一个圆，这个圆跟刚开始的那一个圆会有2个交点，那么它就会把原来的圆分成2个部分。分成2个部分后，它就会多分割出两个平面，于是就变成了四个平面。

同理，3个，4个直到$a_2$个也是如此。

我们可以列一个表格来康康：

圆的总共个数：$1\quad2\quad3\quad4\quad$

新增交点个数：$0\quad2\quad4\quad6$

新增段数个数：$0\quad2\quad4\quad6$

新增块数个数：$0\quad2\quad4\quad6$

平面总共块数：$2\quad4\quad8\quad14$

那么，加上直线怎么做呢？

同样，一条直线和一个圆最多会有两个交点，于是一条直线和一个圆可以多分成两块，于是$ans$还要加上$a_1*a_2*2$。但此时第一个圆会与直线有交点，所以最终只需要每两个圆进行处理即可，于是又要加上$C^2_{a_2}*2=a_2*(a_2-1)$

于是第二部分的代码就出现啦QAQ

else if(i == 2){
    ans += sum * a;//sum的用处就在这 
    if(!sum) ans = 2 + a * (a - 1);//没有直线的情况 
    else ans += a * (a - 1);//有直线的情况 
    b = a;//b是圆的个数，以后也会有用 
    ans %= mod;
}

那么，按照这个思路，正$n$边形的就好打了。

一个正$n$边形与一条直线有2个交点，与一个圆有$2n$个交点，与一个正$3$边形有$6$个交点，……与一个正$n-1$边形有$2(n-1)$个交点。

那么，$ans$就要加上$sum*a_n+b*a*i*2$

其中$sum=2*a_1+6*a_3+8*a_4+...+2*(n-1)*a_{n-1}$，$b$就是圆的个数。

还有这$a_n$个正$n$边形两两之间有$2n$个交点，于是$ans$还要加上$C^2_{a_n}*2*n=a_n*(a_n-1)*n$

于是第三部分的代码就大功告成啦~

else{
    ans += sum * a + b * a * i * 2;//与前面图形的块数 
    if(!sum && !b) ans = 2 + a * (a - 1) * i;//还是要特判QAQ 
    else ans += a * (a - 1) * i;//两两之间的块数 
    sum += i * a * 2;//sum要加上去 
    ans %= mod;
}

综合以上三段代码，这道题就结束啦~~

$CODE:$

#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int n, a, sum, ans, b;
signed main(){
    scanf("%lld", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &a);
        if(!a) continue;//没有就直接continue掉 
        if(i == 1){
    		ans = 1 + a * (a + 1) / 2;
   		 	sum += a * 2;//sum1以后会有用 
    		ans %= mod;//注意要mod 
		}
		else if(i == 2){
    		ans += sum * a;//sum的用处就在这 
    		if(!sum) ans = 2 + a * (a - 1);//没有直线的情况 
    		else ans += a * (a - 1);//有直线的情况 
    		b = a;//b是圆的个数，以后也会有用 
    		ans %= mod;
		}
        else{
    		ans += sum * a + b * a * i * 2;//与前面图形的块数 
    		if(!sum && !b) ans = 2 + a * (a - 1) * i;//还是要特判QAQ 
    		else ans += a * (a - 1) * i;//两两之间的块数 
    		sum += i * a * 2;//sum要加上去 
    		ans %= mod;
		}
    }
    printf("%lld", ans == 0 ? 1 : ans);//最后的特判QAQ 
    return 0;
}

这道题不算难，主要考察大家的思维能力，代码也很短，为了考验大家就限制了空间。

End