题解 P3799 【妖梦拼木棒】

· · 题解

solution

转到题目

在解决这道题目前，我们需要了解一些关于组合数学的知识

我们知道，当我们在n个数中选择m个（不重复）那么可以选择的方案数为C_n ^m

C_n ^m=\frac {n!}{m!\times(n-m)!}

那么，当m=2时

C_n ^m=\frac {n!}{m!\times(n-m)!} =\frac {n!}{2\times(n-2)!}

又因为

n!=n\times (n-1)\times(n-2)\times ……\times2\times1 (n-2)!=(n-2)\times(n-3)\times……\times2\times1

所以

\frac{n!}{(n-2)!}=n\times(n-1) C_n^2=\frac{1}{2}\times(n)\times(n-1)

有了这些铺垫以后，我们再来看这道题

要从n根木棒中选出4根，使他们能组成一个正三角形。

简单的来说，就是先选出两根一样的，在选出两根使这两根的长度之和与先前选出的相同

那么现在来看核心代码

for(int i=Min+1;i<=Max;i++)
    {
        if(num[i]>=2)
        {
            for(int j=Min;j<=i/2;j++)
            {
                if(j!=i-j)
                    ans+=num[i]*(num[i]-1)*num[j]*num[i-j]/2%mod;//后选的两条不相等
                else if(num[j]>=2&&j*2==i)
                    ans+=num[i]*(num[i]-1)*num[i/2]*(num[i/2]-1)/4%mod;//后选的两根相等
            }
            ans%=mod;
        }
    }

如果你看懂了，那么

at last

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5*1e3+500,mod=1e9+7;
int num[maxn],n,Max=-1,Min=0x3f3f,ans=0;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a;
        cin>>a;
        num[a]++;
        Max=max(Max,a);Min=min(Min,a);
    }
    for(int i=Min+1;i<=Max;i++)
    {
        if(num[i]>=2)
        {
            for(int j=Min;j<=i/2;j++)
            {
                if(j!=i-j)
                    ans+=num[i]*(num[i]-1)*num[j]*num[i-j]/2%mod;
                else if(num[j]>=2&&j*2==i)
                    ans+=num[i]*(num[i]-1)*num[i/2]*(num[i/2]-1)/4%mod;
            }
            ans%=mod;
        }
    }
    cout<<ans;
}