2017 ICPC 乌鲁木齐区域赛 D.Fence Building（平面图欧拉公式）

分析

根据平面图欧拉公式可以推导出来，面数 = 新产生的点数 + 边数 + 1 。
新产生的点数：C(n, 4) ，因为四个点可以产生一个新的点
边数：C(n, 2) ，因为每两个点可以连成一条边
最后公式就为 ans = C(n, 4) + C(n, 2) + 1

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const ll mod = 1e9+7;
ll n;ll qm(ll x,ll y)
{
    ll res = 1;while(y){
    if(y & 1) res = res * x % mod;x = x * x % mod;y >>= 1;}return res % mod;
}int main()
{
    int t;scanf("%d",&t);for(int k=1;k<=t;k++){
    scanf("%lld",&n);if(n <= 5){
    printf("Case #%d: %lld\n",k,qm(2, n - 1));continue;}ll ans = 0;ans = (n % mod * ((n - 1) % mod) % mod * qm(2, mod - 2) % mod + n % mod * ((n - 1) % mod) % mod * ((n - 2) % mod) % mod * ((n - 3) % mod) % mod * qm(24, mod - 2) % mod) % mod;ans = (ans + 1) % mod;printf("Case #%d: %lld\n",k,ans);}return 0;
}