怎么感觉我这个考场做法有点非常规啊
还是写写思路吧，初步观察数组 a 的顺序没用，有用的是每个元素的出现次数数组 cnt ，考虑将 cnt 画成直方图研究一下，然后 (x,x,x)，(x,x+1,x+2) 分别变为了 3\times 1，1\times 3 的矩形，而且覆盖的时候还能纵向断开（同时这些矩形还能唯一的被描述，求全覆盖的本质不同总方案数，然后就想到了每一个 cnt_i 不就是一个对方案的限制吗，具体来说设一号三元组 (i,i,i) 的个数为 x_i ，二号 (i,i+1,i+2) 的个数为 y_i ，则有 m 条方程限制： 3x_i+y_i+y_{i-1}+y_{i-2}=cnt_i 。
然后显然要考虑 \texttt{dp} ，非常正常的沿直方图横轴考虑逐个满足方程，那么还要记录那些状态呢？首先应该要记两个量 ，其实记哪两个都可以，但因为 3x_i 在转移的时候有 \frac{1}{3} 的常熟，所一不妨就记录 y_{i-1} 和 y_{i-2} 吧，再有就是 (y_{i-1},y_{i-2}) 的总数量是 O(n^2) 的，这个对着直方图使劲来一发就想出来了，虽然单次转移是有可能 O(n) 的，但总和也是 O(n) 的，所以总复杂度 O(n^2) ， 拿个 unordered_map 转移即可。
#include<bits/stdc++.h>
using namespace std;
#define fio(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define tio() freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)
using ll=long long ;
const int mod=1e9+7;
const int N=5010;
int cnt[N];
int n,m;
struct ph{
ll operator()(const pair<int,int>& a)const{
return ((ll)a.first<<32)|a.second;
}
};
unordered_map<pair<int,int>,int,ph>u,v;
int main(){
// fio("triple");
// tio();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
int x;
scanf("%d",&x);
if(1<=x&&x<=m)++cnt[x];
}
u[{0,0}]=1;
for(int i=1;i<=m;++i){
v.clear();
for(pair<pair<int,int>,int> p:u){
pair<int,int> key=p.first;
int w=p.second;
int x=key.first,y=key.second;
int r=cnt[i]-x-y;
if(r<0)continue;
int tmax=r/3;
for(int t=0;t<=tmax;++t){
int cc=r-3*t;
int nw=v[{y,cc}];
nw+=w;
if(nw>=mod)nw-=mod;
v[{y,cc}]=nw;
}
}
u.swap(v);
}
int ans=u[{0,0}];
printf("%d\n",ans%mod);
return 0;
}