1 条题解

  • 0
    @ 2022-11-6 0:07:58

    同色旗帜对计数

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

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

    image

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

    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;
    }
    

    信息

    ID
    1129
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    91
    已通过
    24
    上传者