自动搬运

查看原文

来自洛谷，原作者为

	Itst 没钩选手瑟瑟发抖

搬运于2025-08-24 21:39:39，当前版本为作者最后更新于2019-01-27 21:39:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Update On 2020.03.07: 修复了代码中的小问题，修改了部分细节，优化了阅读体验。感谢 Marser 指出代码错误。

考虑拆开绝对值计算贡献。对于 $1$ 到 $N$ 的排列，从小到大地将插入它们插入排列中，假设即将插入数 $i$ ，则前 $i-1$ 个数已经被插入到排列中。考虑如何计算 $i$ 的贡献。

不难发现：在最终的排列中，$i$ 的贡献与它和前 $i-1$ 个数和边界的相邻情况有关。如果 $i$ 某一边与边界相邻，会产生 $0$ 的贡献；某一边与小于 $i$ 的数相邻，会产生 $i$ 的贡献；某一边与大于 $i$ 的数相邻，会产生 $-i$ 的贡献。

但是在这里大于 $i$ 的数还没有被插入，所以这里必须要强制数 $i$ 与前 $i-1$ 个数和边界的相邻情况才能够在当前阶段计算出 $i$ 对序列价值的贡献。

设 $f_{i,j,k,l}$ 表示放完前 $i$ 个数、数列中存在 $j$ 个连通块（定义连通块为一段极长区间，满足这一段区间任意的相邻的两个数都被强制定为相邻，也就是说在之后的转移中，这一段区间内不能插入数）、数列总价值为 $k-5000$、有 $l$ 个边界已经与某个数强制相邻的方案数。

转移考虑数 $i$ 的相邻情况：

1. 一边与边界相邻，一边不与当前存在的连通块相邻。这会产生额外的一个连通块，并产生 $-i$ 的价值，方案数为 $2-l$；

2. 一边与边界相邻，一边与当前存在的连通块相邻。这不会导致连通块数变化，产生 $i$ 的价值，方案数为 $2-l$ ，要求 $j \neq 0$；

3. 两边均与当前存在的连通块相邻。这会导致两个连通块合并从而连通块数减少 $1$，产生 $2i$ 的价值，方案数为 $j-1$ ，要求 $j \geq 2$；

4. 两边均不与当前存在的连通块相邻。这会产生额外的一个连通块，产生 $-2i$ 的价值，方案数为 $j+1-l$；

5. 一边与当前存在的连通块相邻，另一边不与当前存在的连通块相邻。这不会产生额外的连通块，产生 $0$ 的价值，方案数为 $2j-l$ ，要求 $j \neq 0$。

注意到 $45$ 两种转移的方案数都减去了 $l$，因为对于两端都不与边界相邻的连通块，可以选择左右之一与当前的数相邻，但是有一段与边界相邻的连通块只有另一端可以。

答案是 $\frac{\sum\limits_{i=5000+M}^{10000} f_{N,1,i,2}}{n!}$。

然后这鬼题还要数据类型分治……$K \leq 8$使用long double，$K \leq 30$使用__float128。

还要注意在 DP 的过程中将 $\frac{1}{n!}$ 乘入，也就是当转移完 $f_{i,j,k,l}$ 之后将其乘上 $\frac{1}{i}$，而不是先计算方案数再乘上 $\frac{1}{n!}$。后者在比较刁钻的数据下会掉精度。

#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;

namespace db{long double dp[2][110][10010][3];}
namespace flt{__float128 dp[2][110][10010][3];}
int N , M , K;

template < class T >

void out(T ans){
        if(ans + 1e-14 >= 1){cout << "1." << string(K,'0') << endl; return;}
	cout << "0.";
	ans *= 10;
	for(int i = 1 ; i <= K ; ++i){
		cout << (int)(ans + (K == i) * 0.5);
		ans = (ans - (int)ans) * 10;
	}
}

template < class T >

inline void solve(T dp[][110][10010][3]){
	T ans = 0;
	dp[0][0][5000][0] = 1;
	int now = 0;
	for(int i = 1 ; i <= N ; ++i){
		now ^= 1;
		memset(dp[now] , 0 , sizeof(dp[now]));
		for(int j = 0 ; j < i ; ++j)
			for(int k = 0 ; k <= 10000 ; ++k)
				for(int p = 0 ; p <= 2 ; ++p)
					if(dp[now ^ 1][j][k][p]){
						if(k - 2 * i >= 0)
							dp[now][j + 1][k - 2 * i][p] += dp[now ^ 1][j][k][p] * (j + 1 - p) / i;
						if(j)
							dp[now][j][k][p] += dp[now ^ 1][j][k][p] * (j * 2 - p) / i;
						if(j >= 2 && k + 2 * i <= 10000)
							dp[now][j - 1][k + 2 * i][p] += dp[now ^ 1][j][k][p] * (j - 1) / i;
						if(p != 2){
							if(k - i >= 0)
								dp[now][j + 1][k - i][p + 1] += dp[now ^ 1][j][k][p] * (2 - p) / i;
							if(j && k + i <= 10000)
								dp[now][j][k + i][p + 1] += dp[now ^ 1][j][k][p] * (2 - p) / i;
						}
					}
	}
	for(int i = M ; i <= 5000 ; ++i)
		ans += dp[now][1][5000 + i][2];
	out(ans);
}

int main(){
	cin >> N >> M >> K;
	if(K <= 8)
		solve(db::dp);
	else
		solve(flt::dp);
	return 0;
}