题目描述
由 $[1,n]$ 组成的排列，求其波动强度大于 $m$ 的概率，结果保留 $k$ 位小数。定义波动强度为每个数与其相邻数的差的绝对值之和。
$n\le 100$，$k\le 30$，$m\le 2147483647$。
算法分析
求波度强度大于 $m$ 的概率，我们可以求出每个波度强度的方案数，累加起来除以 $n!$ 即可。
考虑拆掉绝对值符号，对每个数分别计算贡献，对于一个数 $x$，如果它旁边的数比它小，那么它此时对答案的贡献就是 $x$，否则就是 $-x$。
我们从 $1$ 到 $n$ 一个一个数地去填，定义 $f[i][j][k][l]$ 表示填了前 $i$ 个数，当前有 $j$ 段，波动强度为 $k$，被填充的边界数量为 $l$ 时的方案数。需要解释的是，这里填充时并没有将一个数填充到一个特定的位置，而是悬浮在那里，通过控制当前段数与边界数确定一个状态。
如何转移？统一说明，计算 $k$ 那一位的变化实际上是因为按顺序填充时前面已经填充的数一定比当前填充的数要小，后面填充的数一定比当前填充的数要大，因此可以先将当前数累积入贡献。
- 新填入的数单独作为一段：$f_{i,j+1,k-i-i,l}+=(j+1-l)f_{i-1,j,k,l}$，当前有 $j$ 段，那么新添入的数可以放入的空隙有 $j+1$ 个，假若已经有 $l$ 段是边界了，那么就不能放在其外面，因此需要减去。
- 新填入的数与原来的段拼起来作为一段：$f_{i,j,k,l}+=(j+j-l)f_{i-1,j,k,l}$，可以填到每个已有段的左右两边，减去边界与上面同理。
- 新填入的数合并原来的两段：$f_{i,j-1,k+i+i,l}+=(j-1)f_{i-1,j,k,l}$，可以合并任意相邻的两段。
- 新填入的数被放置在边界作为单独的一段：$f_{i,j+1,k-i,l+1}+=(2-l)f_{i-1,j,k,l}$，枚举放在左右哪个边界。
- 新填入的数合并原来的段与边界（此时如果合并原来的段与边界的段可能会在小数据下出现问题）：$f_{i,j,k+i,l+1}+=(2-l)f_{i,j,k,l}$，同样是枚举放在左右哪个边界，注意保证至少有一个段存在。
注意使用滚动数组优化空间复杂度，由于精度要求较高，针对 $k$ 比较大的情况使用 __float128 计算。
需要卡卡空间（比如把 long double 换成 double），时间复杂度为 $O(n^4)$。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include <cstdio>
#include <cstring>
int n,m,k;template<class T>
inline void solve(T f[2][101][9001][3]) {
T ans=0;f[0][0][4500][0]=1;
for(register int i=1;i<=n;++i) {
memset(f[i&1],0,sizeof(f[i&1]));
for(register int j=0;j<i;++j) {
for(register int k=0;k<=9000;++k) {
for(register int l=0;l<=2;++l) if(f[(i&1)^1][j][k][l]) {
if(k-i-i>=0) f[i&1][j+1][k-i-i][l]+=f[(i&1)^1][j][k][l]*(j+1-l);
if(j) f[i&1][j][k][l]+=f[(i&1)^1][j][k][l]*(j+j-l);
if(j-1>=1&&k+i+i<=9000) f[i&1][j-1][k+i+i][l]+=f[(i&1)^1][j][k][l]*(j-1);
if(k-i>=0&&l+1<=2) f[i&1][j+1][k-i][l+1]+=f[(i&1)^1][j][k][l]*(2-l);
if(j&&k+i<=9000&&l+1<=2) f[i&1][j][k+i][l+1]+=f[(i&1)^1][j][k][l]*(2-l);
}
}
}
}
for(register int i=4500+m;i<=9000;++i) ans+=f[n&1][1][i][2];
for(register int i=1;i<=n;++i) ans/=i;printf("0.");
for(register int i=1;i<=k;++i) {ans*=10;int x=(i^k)?ans:(ans+0.5);printf("%d",x);ans-=x;}
putchar('\n');
}
double f[2][101][9001][3];__float128 g[2][101][9001][3];
int main() {
scanf("%d%d%d",&n,&m,&k);
if(k<=8) solve(f);else solve(g);
return 0;
}
|