C++14(g++5.4) 解法, 执行用时: 35ms, 内存消耗: 8804K, 提交时间: 2019-10-04 16:12:35

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
template<class T>inline void MAX(T &x,T y){if(y>x)x=y;}
template<class T>inline void MIN(T &x,T y){if(y<x)x=y;}
template<class T>inline void rd(T &x){
	x=0;char o,f=1;
	while(o=getchar(),o<48)if(o==45)f=-f;
	do x=(x<<3)+(x<<1)+(o^48);
	while(o=getchar(),o>47);
	x*=f;
}
const int M=205;
int n,m,A[M],B[M],id[M];
bool mark[M][M][M],can[M][M];
ll ans[4];
int main(){
#ifndef ONLINE_JUDGE
	freopen("jiedai.in","r",stdin);
//	freopen("jiedai.out","w",stdout);
#endif
	while(scanf("%d%d",&n,&m)!=EOF){
		memset(id,0,sizeof(id));
		memset(ans,0,sizeof(ans));
		memset(mark,0,sizeof(mark));
		memset(can,0,sizeof(can));
		for(int i=1;i<=n;i++)rd(A[i]),B[i]=A[i];
		sort(B+1,B+1+n);
		int uni=unique(B+1,B+1+n)-B-1,cnt=0;
		for(int i=1;i<=uni;i++)if(B[i]<=m)cnt++;
		for(int i=1;i<=n;i++)for(int j=1;j<=cnt;j++)if(A[i]==B[j])id[i]=j;
//		for(int i=1;i<=n;i++)printf("%d : %d\n",i,id[i]);
//		printf("%d %d\n",uni,cnt);
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
				can[id[i]][id[j]]=1;
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
				for(int k=j+1;k<=n;k++)
					mark[id[i]][id[j]][id[k]]=1;
		for(int i=1;i<=cnt;i++)
			for(int j=1;j<=cnt;j++)
				for(int k=1;k<=cnt;k++){
					if(mark[i][j][k])ans[3]++;
					else if(can[i][j]||can[i][k]||can[j][k])ans[2]++;
					else ans[1]++;
				}
		for(int i=1;i<=cnt;i++)
			for(int j=1;j<=cnt;j++)
				if(can[i][j])ans[2]+=3ll*(m-cnt);
		ans[0]=1ll*(m-cnt)*(m-cnt)*(m-cnt);
		ans[1]=1ll*m*m*m-ans[0]-ans[2]-ans[3];
		for(int i=0;i<4;i++)printf("%lld%c",ans[i],i==n?'\n':' ');
	}
	return (0-0);
}

C++11(clang++ 3.9) 解法, 执行用时: 333ms, 内存消耗: 1016K, 提交时间: 2019-10-04 14:18:13

#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(int i=s;i<t;i++)
#define pii pair<int,int>
typedef long long ll;
ll dp[222][4],res[5],sum[5];
int num[222];
unordered_map<int,ll> um[4];
int n,m;

int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        rep(i, 1, n + 1)scanf("%d", &num[i]);
        rep(i, 0, 4)sum[i] = 0, um[i].clear();
        sum[0] = 1,dp[0][0] = 1;
        map<int,int> ss;set<pii> s2;
        ll xxx = 0;
        rep(i, 1, n + 1)if (num[i] <= m)
            {
                if (!ss.count(num[i]))xxx++;
                ss[num[i]]++;
                rep(j, 0, 3)dp[i][j + 1] = sum[j] - um[j + 1][num[i]];
                rep(j, 0, 4)sum[j] += dp[i][j], um[j][num[i]] += dp[i][j];
            }
         rep(i,1,n+1)rep(j,i+1,n+1)   s2.insert({num[i],num[j]});
         memset(res,0,sizeof(res));
        res[3] = sum[3], res[0] = (m - xxx) * 1LL * (m - xxx) * (m - xxx);
        res[2]=sum[2]*1LL*(m-xxx)*3;
        for(auto &k:ss)for(auto &k2:ss)for(auto &k3:ss)
        {
            if(s2.count({k.first,k2.first})||s2.count({k.first,k3.first})||s2.count({k2.first,k3.first}))
                res[2]++;
        }
        res[2]-=res[3];
        res[1]=m*1LL*m*m-res[3]-res[2]-res[0];
        rep(i,0,4)
        printf("%lld%c",res[i]," \n"[i==3]);
    }
}