月赛t2全WA蒟蒻求助dalao
查看原帖
月赛t2全WA蒟蒻求助dalao
282292
966123anyunchuan楼主2020/8/21 23:06
#include <iostream>
using namespace std;
const int  MAXN=200000, mod=998244353;
int n, a[MAXN+10], b[MAXN+10], c[MAXN+5][5], mx, ans;
void C()//先用杨辉三角算好组合数,这个大概率是对的 
{
    c[0][0] = 1;
    for(int i=1; i<=n; i++)
    {
        c[i][0] = 1;
        for(int j=1; j<=3; j++)
        {
            c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod;
        }
    }
}
int main()
{
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
        mx = max(mx, a[i]);
        b[a[i]]++;//b[x]为长度为x的边出现的次数 
    }
    C(); 
    for(int i=1; i<=mx; i++)//枚举腰的长度,i为腰的长度 
    {
        if(b[i]<2) continue;//同样长的腰至少出现两次 
        for(int j=1; j<i+i; j++)//枚举底的长度,j为底的长度 
        //j<i+i是因为两边长大于第三边,所以 底<腰+腰 
        {
            if(b[j]==0) continue;//腰必须有一个木棒来拼 
            if(i!=j)//底、腰不相等 
            {
                ans = (ans+c[b[i]][2]*b[j])%mod;//c[x][y]为从x个数中选y个数的方案数 
            }else{
                if(b[i]<3) continue;//等边三角形,至少有三个等长的木棒 
                ans = (ans+c[b[i]][3])%mod;
            }           
        }
    }
    cout << ans%mod;
    return 0;
}

输出了中间变量,发现没问题,可能是些比较坑的地方出了错。求助大佬,万分感谢!

2020/8/21 23:06
加载中...