同色旗帜对计数

由于题目中说，只需要输出方案数而不需要输出具体的选择方案，因此可以采用各种各样的办法来做，只要把数据存进来就行。

本蘜蒻思路：计数排序，对于n个同种颜色的旗子来说，不重复选择的前提下一共有1+2+...+n-1种方案，可通过下图进行简易证明：

因此，运用高斯的等差数列求和公式进行计算即可。

long long！long long！long long！

我交了足足八次！八次！你知道我这八次怎么过来的吗！你对得起我吗！

在进行等差数列求和的时候，使用公式虽然可以大大降低时间复杂度，但是注意，两个int型相乘之后结果仍为int型，所以需要(long long)后再取模，否则只能拿到70分。（或者干脆直接全开longlong）

上代码

#include<bits/stdc++.h>
using namespace std;
int n,a[1000010];
long long sum;
long long jh(long long x)
{
	long long sum1=0;
	sum1=((1+x)*x/2)%1000000007;
	return sum1;
} 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int ls;
		cin>>ls;
		a[ls]++;
	}
	for(int i=1;i<=1000000;i++)
	{
		if(a[i]>=2)
			sum+=jh(a[i]-1);
		sum=sum%1000000007;
	}
	cout<<sum%1000000007;
	return 0;
}