你考虑，我们如果没有重合就将元素删去的操作，我们就有答案：\(n \times (m+1) - \sum\limits_{i=1}^n a_i\)
但是，我们显然最后的答案是小于这个的，如果有两个数在 \(i\) 相撞，那么我们的答案就会减少 \((m-i+1)\)
我们设 \(f_{i,j}\) 表示两个数分别在 \(i\) 和 \(j\) 的概率 \((i\leq j)\)，\(f_{i,i}\) 表示第一次相撞在 \(i\) 的概率，我们可以得到下面递推式：
\[f_{i,j} = f_{i,j-1} \times \frac {[i \neq j-1]} 2 + f_{i-1,j} \times \frac {[i-1 \neq j]} 2
\]
然后我们最终的答案即为：
\[n \times (m+1) - \sum\limits_{i=1}^n (a_i + f_{i,i} \times (m-i+1))
\]
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 508,MOD = 1e9 + 7;
bool Med;
int n,m;
ll ans;
ll s[NN];
ll f[NN][NN];
bool Mbe;
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; ++i) {
scanf("%lld",&s[i]);
ans = (ans + m + 1 - s[i]) % MOD;
if(i != 1) f[s[i-1]][s[i]] = 1;
}
for(int i = 1; i <= m; ++i){
ans = (ans + MOD - 1ll * f[i][i] * (m - i + 1) % MOD) % MOD;
for(int j = i + 1; j <= m; ++j){
f[i][j+1] = (f[i][j+1] + f[i][j] * (MOD+1 >> 1) % MOD) % MOD;
f[i+1][j] = (f[i+1][j] + f[i][j] * (MOD+1 >> 1) % MOD) % MOD;
}
}
printf("%lld\n",ans);
// fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
// fprintf(stderr, "%.5lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
}