牛客小白月赛5 F
题目描述：
链接：https://www.nowcoder.com/acm/contest/135/F
来源：牛客网
签到题来了，送你们一个Python秒的题。Apojacsleam来到了OI大陆，经过了连年征战，
成为了一方国王。 Apojacsleam把他的王国命名为“Apo国”，Apo国的领土是一个标准的圆形。
Apojacsleam现在想封赏他的大臣，他在国境上建立了n个城市，要求他的大臣对这n个城市两两之间修建道
（道路是笔直的），把整个王国分成尽量多的区域，使得每一个大臣都有封土并且不会太大（以免谋反）。
于是Apojacsleam找你求助，他告诉你他打算建多少个城市，而你的任务是告诉他最多可以分成多少个部分。
说的太慢可是要被处死的，所以你必须要在1s之内回答。
输入描述：
输入数据有多组，每组一行，一个正整数n，意义如“题目描述”
输出描述：
对于每一组数据输出一行描述答案：
输出一个正整数k，表示最多分成k份。
输入：
2
3
输出：
2
4
思路：
刚开始我去找规律，发现前5项是 2^n-1,所以写了一发wa了，那时不知道有欧拉公式看了题解
才知道有这个东西的存在，F=E-V+2 F代表区域数，E代表边数，V代表顶点数 。
关键是是求出E和V 两条线相交会出现一个点，所以四个点可以生成一个点，
即V=n+C(n,4);一条线段可以提供两个度，在这道题里生成的点是4圆上的点是(n+1);
所以 E=(4*c(n,4)+n*(n+1))/2;(具体题目的度不同要具体分析这题的圆弧也算一个度)最后带入公式即可
本题求的是圆内的而欧拉公式求的还有圆外一个平面所以F要减1。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ll n;
ll ans=0;
while(scanf("%lld",&n)!=EOF){
ans=0;
ans+=((n)*(n-1))/2+n*(n-1)*(n-2)*(n-3)/24+1;
cout<<ans<<endl;
}
}
牛客多校8 G Counting regions
题目描述：
链接：https://www.nowcoder.com/acm/contest/146/G
Niuniu likes mathematics. He also likes drawing pictures. One day, he was trying to
draw a regular polygon with n vertices. He connected every pair of the vertices
by a straight line as well. He counted the number of regions inside the polygon
after he completed his picture. He was wondering how to calculate the number of
regions without the picture. Can you calculate the number of regions
modulo 1000000007? It is guaranteed that n is odd.
输入描述：
The only line contains one odd number n(3 ≤ n ≤ 1000000000),
which is the number of vertices.
输出描述：
Print a single line with one number, which is the answer modulo 1000000007.
题意：
大概就是给你一个 n为奇数的正多边形 然后连接各个点求划分的区块数。
输入：
5
输出：
11
思路：
看上面一样的
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=1e9+7;
LL qpow(LL x,LL k){
LL sum=1;
while(k){
if(k&1)
sum=(sum%mod*x%mod)%mod;
k>>=1;
x=(x%mod*x%mod)%mod;
}
return sum;
}
int main(){
LL n;
cin>>n;
//cout<<n<<endl;
LL t1,t2;
LL inv1=qpow(24,mod-2);
LL inv2=qpow(2,mod-2);
t1=((n-3)%mod*(n-2)%mod*(n-1)%mod*(n)%mod*inv1%mod)%mod;
t2=(n%mod*(n-3)%mod*inv2)%mod;
cout<<(t1+t2+1+mod)%mod<<endl;
return 0;
}
总结：
第一次没写出来还好，第二次没推出来实在是罪过以后还是要多回味一下做过的题。