练习赛115a题

题目地址： https://ac.nowcoder.com/acm/contest/64819/A

1.首先我们可以确定最大值一定是在最中间

2.把最大值放好后，我们考虑放第二大的数如何摆放，(这里注意：最大值有多个与只有一个没有区别都是放在最中间)

3.从第二大数到最小的数依次考虑，对每个数我们是以最大值为分界线的，考虑放在最大值的左边或者右边(左边确定放置情况，右边是唯一确定的)，假设第二大的数出现cnt2次，我们可以在左边右边分别放(0,cnt2),(1,cnt2-1),(2,cnt2-2)...(cnt2,0),共cnt2+1中情况

4.假设第三大的数出现了cnt3次，我们把第二大数放好后，考虑如何放第三大的数，同样，第三大的数放置情况有cnt3+1种，这里是在第二大的数放好后再放第三大的数，一个简单的分步乘法(cnt2+1)*(cnt3+1)....

算法实现：统计每一个数出现的次数，除最大值出现的次数外，对每一个数出现的次数+1累乘即可，(注意一边取模)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>


using namespace std;
int const mod=998244353;    //1e9+7

typedef long long LL;

int n,T;


void solve()
{
    unordered_map<int,int>cnt;
    scanf("%d", &n);
    
    int maxx=-1;    //记录最大值
    for(int i=0;i<n;i++){
        int x;  scanf("%d",&x);
        cnt[x]++;
        maxx=max(maxx,x);
    }
    
    LL ans=1;
    for(auto &[x,y]:cnt)
        if(x!=maxx) //除最大值外，累乘出现的次数+1
            ans=ans*(y+1)%mod;
            
    cout<<ans<<endl;
   
} 

int main()
{
    T=1;
    scanf("%d",&T);
    while(T--){
        solve();
    }
	
	return 0;
}

图一乐：哈哈，感觉我在自圆其说，，先发一篇水博客吧，慢慢进步！