ZJOI2012 波浪

题目:

  阿米巴和小强是好朋友。
  阿米巴和小强在大海旁边看海水的波涛。小强第一次面对如此汹涌的海潮,他兴奋地叫个不停。而阿米巴则很淡定,他回想起曾经的那些日子,事业的起伏,
  情感的挫折……总之今天的风浪和曾经经历的那些风雨比起来,简直什么都不算。
  于是,这对好朋友不可避免地产生了分歧。为了论证自己的观点,小强建立了一个模型。他海面抽象成一个 的排列 。定义波动强度等于相邻两项的差的绝对值的和,即:
  给你一个 ,问:随机一个 的排列,它的波动强度不小于 的概率有多大?
  答案请保留小数点后 位输出,四舍五入

思路:

  观察发现 大约是 级的,所以可以试着求出每个 对应的方案数。
  但是题中的 看起来很不好搞的样子,试着拆开。假设 两边有 个大于它的值,那么它的贡献就是 ,如果有 个小于它的值,贡献就是
  试着把数字小到大加入,对于当前要加入的数字 考虑它在最终状态中边上有几个比它小的点。每次如果把确定的点连在一起(也就是说它们在最终状态中一定相邻,如果放在一起但没有连起来,那么它们在最终状态中只保证了相对位置,中间可能会插入数)这样就会组成很多的联通块,因为每次的权值与相邻点无关,所以只要知道联通块个数就行了。特别的,第一个和最后一个点只有一边有数字,所以还要记录边界的个数。
  设 表示插到第 个, 个联通块,当前权值为 ,边缘还剩 个位置的方案数。
  如果一边小于当前点,一边大于,那它就要连到一个联通块的边上:
  
  如果一边小于,一边是边界,那就会把一个联通块和边界相连:
  
  如果两边都大于,那它就独立成一个块:
  
  如果一边大于,一边是边界,那它就独立成一个和边界相连的块:
  
  如果两边都小于,那它就独立成一个联通块:
  
  最后合法的方案就是所有 的状态。
  具体实现, 可以直接 long double, 应该就要手写高精了(不过自己做题可以偷懒用 __float128

代码:

#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;
const int N = 105;

bool cur1;

template<class T>
inline void rd(T &a) {
#define gc getchar()
    char c;
    bool f = false;
    for(c = gc; !isdigit(c); c = gc) f |= (c == '-');
    for(a = 0; isdigit(c); c = gc) a = (a << 1) + (a << 3) + c - '0';
    if(f) a = -a;
#undef gc
}

template<class T> 
T getDP(int n, int m, int k) {
#define F(i, k, s, d) dp[(i) & 1][k][(s) + 4500][d]
    static T dp[2][N][9005][3];
    F(1, 1, -2, 2) = 1; F(1, 1, -1, 1) = 2; F(1, 1, 0, 0) = 1;
    rep(i, 2, n) {
        mset(dp[i & 1], 0);
        rep(k, 1, i - 1)
            rep(s, -4500, 4500)
                rep(d, 0, 2) {
                    T tmp = F(i - 1, k, s, d);
                    if(tmp == 0) continue;
                    F(i, k, s, d) += tmp * (2 * k - (2 - d));
                    if(d && s + i <= 4500) F(i, k, s + i, d - 1) += tmp * d;
                    if(s - 2 * i >= -4500) F(i, k + 1, s - 2 * i, d) += tmp * (k + 1 - (2 - d));
                    if(d && s - i >= -4500) F(i, k + 1, s - i, d - 1) += tmp * d;
                    if(s + 2 * i <= 4500) F(i, k - 1, s + 2 * i, d) += tmp * (k - 1);
                }
    }
    T ans = 0;
    rep(i, m, 4500) ans += F(n, 1, i, 0);
    rep(i, 1, n) ans /= i;
    return ans;
}

void print(int k, __float128 f) {
    printf("0.");
    rep(i, 1, k) {
        f *= 10;
        int x = (int) ((i == k) ? (f + 0.5) : f);
        printf("%d", x);
        f -= x;
    }
    puts("");
}

bool cur2;

int main() {
    // printf("%lf\n", (&cur2 - &cur1) / 1024.0 / 1024);
    int n, m, k;
    File(wave);
    rd(n); rd(m); rd(k);
    if(k <= 8) {
        printf("%.*Lf\n", k, getDP<long double>(n, m, k));
    }
    else print(k, getDP<__float128>(n, m, k));
    return 0;
}