HDU 5621 KK's Point

问题描述

我们可爱的KK遇到了一道数学难题:他在一个圆上点下了互不重合的N\left(2\leq N\leq {10}^{5} \right)N(2≤N≤105)个点，现在他要将这NN个点两两相连（圆内没有三条线交于一个点的情况），KK想知道图形中一共有多少个交点（包括边界上的点）。      

输入描述

第一行一个数T\left( 1\leq T\leq 10\right)T(1≤T≤10)，表示数据组数。
接着T行，每行一个整数N\left(2\leq N\leq {10}^{5} \right)N(2≤N≤105)，表示圆上的点数。      

输出描述

对于每一个数据输出一个整数，表示交点数。

输入样例

2

3

4

输出样例

3

5

这是个数学问题，除了圆上的n个点以外，圆内的任意一个交点对应于圆上的4个点，所以答案就是c(n,4)+n

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e5 + 10;
int T, n, m;

int main(){
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        printf("%I64u\n", (ULL)n*(n - 1)/2*(n - 2)/3*(n - 3) / 4 + n);
    }
    return 0;
}