题解 P2612 【[ZJOI2012]波浪】

Itst · 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 的相邻情况：

一边与边界相邻，一边不与当前存在的连通块相邻。这会产生额外的一个连通块，并产生 -i 的价值，方案数为 2-l；
一边与边界相邻，一边与当前存在的连通块相邻。这不会导致连通块数变化，产生 i 的价值，方案数为 2-l ，要求 j \neq 0；
两边均与当前存在的连通块相邻。这会导致两个连通块合并从而连通块数减少 1，产生 2i 的价值，方案数为 j-1 ，要求 j \geq 2；
两边均不与当前存在的连通块相邻。这会产生额外的一个连通块，产生 -2i 的价值，方案数为 j+1-l；
一边与当前存在的连通块相邻，另一边不与当前存在的连通块相邻。这不会产生额外的连通块，产生 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;
}