出题人题解 | #平面#

原题解链接：https://ac.nowcoder.com/discuss/149980

定理: $nn$条直线最多能把空间划分为$\frac{n\ast (n+2)}{2}+1\backslash frac\{n\; *(n+2)\}\{2\}+1$ 份

我们可以把$XX$型看做两条不相交的直线，因此答案为$\frac{2n\ast (2n+1)}{2}+1\backslash frac\{2\; n\; *(2\; n+1)\}\{2\}+1$

证明:

对于第$nn$条直线，如果使得区域增加$kk$个， 当且仅当它与$k-1k-\; 1$条直线相交 而我们之前已经构造好了$n-1n\; -\; 1$条两两相交的直线，且三三不相交的直线，因此第$nn$条直线一定可以找到一种方法使得与$n-1n-\; 1$条直线相交

因此$ans=1+1+2+3+\mathrm{.}\mathrm{.}\mathrm{.}+nans=\; 1+1+2+3+...+n$

直接上等差数列求和公式

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define LL long long 
using namespace std;
const int MAXN = 2001 * 2, INF = 1e9 + 10;
inline LL read() {
    char c = getchar(); LL x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int main() {
    long long n = read();
    if(n > (long long) 1e9) {
		puts("GG");
    }
    long long  ans = n * (2 * n + 1) + 1; 
    //printf("%lld\n", ans);
    cout << (long long)ans;
    return 0;
}