【题解】CF1854C Expected Destruction

标签：NN int 题解 ll times 答案 Expected Destruction MOD

你考虑，我们如果没有重合就将元素删去的操作，我们就有答案：\(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);
}

标签：NN,int,题解,ll,times,答案,Expected,Destruction,MOD
From： https://www.cnblogs.com/rickylin/p/17688355.html