UVa 10213 How Many Pieces of Land ?

题目

UVa 10213 How Many Pieces of Land ?

题解

欧拉公式$V-E+F=2$所以找出顶点数和边数就行了，枚举两个点，在左半边的如果有$i$个，右边有$n-i-2$个，交点个数$i*(n-i-2)$（其实感觉不太明白为啥钦定交点不重合，感觉是因为重合了会使答案变差），然后这条线段被分成了$i*(n-i-2)+1$部分，然后外围凸包上的边有n条，圆弧分成了n段，所以V，E就能算出来了。

$$V=n+\frac{n}{4}\sum_{i=1}^{n-3}i(n-2-i)$$
$$E=2n+\frac{n}{2}\sum_{i=1}^{n-3}(i(n-2-i)+1)$$

恩然后能算出$F=E-V+2$，但是这包括了最外面那个无限面，所以答案实际上是$E-V+1$

恩展示一下化简过程($1^2+2^2+3^3+\ldots+n^2=\frac{n(n+1)(2n+1)}{6}$)。
设

$$\begin{eqnarray*} A & = &\sum_{i=1}^{n-3}(n-i-2)i\\ & = &(n-2)*\frac{(n-2)(n-3)}{2}-\frac{(n-3)(n-2)(2n-5)}{6}\\ & = &\frac{n^3-6n^2+11n-6}{6} \end{eqnarray*}$$

则

$$\begin{eqnarray*} E-V+1 & = &1+2n+\frac{n}{2}(A+\sum_{i=1}^{n-3}1)-n-\frac{n}{4}*A \\ & = &1+n+\frac{n(n-3)}{2}+\frac{n}{4}*A\\ & = &1+\frac{n^2-n}{2}+\frac{n}{4}*A\\ & = &\frac{1}{24}(n^4-6^3+23n^2-18n)+1 \end{eqnarray*}$$

然后就高精xjb搞了，因为这里有除法所以好像很多人懒得写的样子（像我根本就不会），其实这里24很小，属于低精，可以写成按位除的形式，详见紫书P314页–大整数取模，或者看代码。

代码

//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;const int maxn=1000;
char a[maxn];
struct BIGNUM{static const int base=10000;static const int baseL=4;int num[maxn],len;BIGNUM (){
   memset(num,0,sizeof(num));len=1;}BIGNUM operator = (int x){memset(num,0,sizeof(num));int tmp=x;len=0;for(;tmp;tmp/=10)len++;a[len]='\0';tmp=x;for(int i=len-1;i>=0;i--) a[i]='0'+tmp%10,tmp/=10;return *this=a; }BIGNUM operator = (const char* s){memset(num,0,sizeof(num));len=strlen(s);for(int cnt=0;baseL*cnt<=len;cnt++)for(int j=baseL;j>=1;j--)if(len-cnt*baseL-j>=0) num[cnt]=num[cnt]*10+s[len-cnt*baseL-j]-'0';len=len/baseL+(len%baseL!=0);return *this;}BIGNUM(const int rhs){*this=rhs;}BIGNUM operator *(const BIGNUM& x){BIGNUM c;c.len=len+x.len;for(int i=0;i<x.len;i++)for(int j=0;j<len;j++){c.num[i+j]+=num[j]*x.num[i];c.num[i+j+1]+=c.num[i+j]/base;c.num[i+j]%=base;}while(c.num[c.len-1]==0&&c.len>1)c.len--;return c;}BIGNUM operator *=(const BIGNUM& rhs){
   return *this=*this * rhs;}BIGNUM operator + (const BIGNUM& rhs)const{BIGNUM c;int alen;alen=max(rhs.len,len);c.len=alen+1;int x=0;for(int i=0;i<=alen;i++){if(i<rhs.len){x+=rhs.num[i];}if(i<len){x+=num[i];} c.num[i]+=x%base;x/=base;}  while(c.num[c.len-1]==0&&c.len>1)c.len--;return c;}BIGNUM operator += (const BIGNUM& rhs){
   return *this=*this+rhs;}BIGNUM operator - (const BIGNUM& rhs)const{BIGNUM c;c.len=len;for(int i=0;i<len;i++){c.num[i]=c.num[i]+num[i]-rhs.num[i];if(c.num[i]<0) c.num[i]+=base,c.num[i+1]-=1; }while(c.num[c.len-1]==0&&c.len>1) c.len--;return c;}BIGNUM operator -= (const BIGNUM& rhs){
   return *this=*this-rhs;} BIGNUM operator / (const int &rhs)const{
   //高精除低精做法BIGNUM c;c.len=len;long long x=0;for(int i=len-1;i>=0;--i){x=x*base+num[i];c.num[i]=x/rhs;x%=rhs;}while(c.num[c.len-1]==0&&c.len>1) --c.len;return c;}
};
istream&  operator >> (istream& in,BIGNUM &x){in>>a;x=a;return in;    
}
ostream&  operator << (ostream& out,const BIGNUM &x)
{printf("%d",x.num[x.len-1]);for(int i=x.len-2;i>=0;i--)printf("%04d",x.num[i]);return out;
}typedef BIGNUM ll;inline void solve()
{ll n;cin>>n;n=n*n*n*n+(ll)23*n*n-(ll)6*n*n*n-(ll)18*n;cout<<n/24+(ll)1<<endl;
}int main()
{int T;cin>>T;while(T--) solve();return 0;
}