题解：P3779 [SDOI2017] 龙与地下城

· · 题解

众所周知，这道题我们可以用列出一个简单的 dp 方程计算概率。既然大家都可以刷到这道题，想必推出这个方程对大家来说不在话下。

看到这题的惊人数据，我们可以用 FFT 来优化。如果你很牛，那么你就可以 AC 了。但是，如果你的 FFT 常数不优秀在大数据下TLE，那么，这里有适合你的更加简单的解法。

我们可以先整理以下题意。

反复看几遍题面，你会发现当数据变得很大的时候，结果似乎越来越服从正态分布。他要我们计算的就是 N(a,b)。

题目又告诉我们 \mu=\frac{x-1}{2}y 还有 \sigma^2=\frac{x^2-1}{12}y。

我们看向高中数学选修三中的一句话：

数值积分？这不由得让我们想起来了自适应辛普森法！不会了话建议左转进入 P4526 学习包教包会。

注意此题数据十分变态需要将数据转化标准正态分布让我们的精度加强。

于是我们将数据分类讨论，当 x \times y \leq 2000 的时候用 dp，其他时候用自适应辛普森法，就可以 AC 了。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 2000 + 5;
const double eps = 1e-5;
const double PI = 3.1415926535897;
double x, y, f[N], s[N], mu, sigma;
double fu(double x) {
    return exp(-x * x / 2) / sqrt(2 * PI);
}
double simpson(double l, double r) {
    double mid = (l + r) / 2;
    return (r - l) * (fu(l) + 4 * fu(mid) + fu(r)) / 6;
}

double use_simpson(double l, double r, double eps, double ans, int step) {
    double mid = (l + r) / 2;
    double tl = simpson(l, mid), tr = simpson(mid, r);
    if (abs(tl + tr- ans) <= 15 * eps && step < 0) {
        return tl + tr + (tl + tr - ans) / 15;
    }
    return use_simpson(l, mid, eps / 2, tl, step - 1) + use_simpson(mid, r, eps / 2, tr, step - 1);
}
void auto_ac() {
    cin >> x >> y;
    mu = (x - 1) / 2 * y;
    sigma = (x * x - 1) / 12 * y;
    if (x * y <= 2000) {
        s[0] = 0;
        f[0] = pow(1 / x, y);
        for (int i = 1; i <= x * y - 1; i++) {
            f[i] = 0;
            for (int j = 1; j <= min(int(x - 1), i); j++) {
                f[i] += y * j * f[i - j] - (i - j) * f[i - j]; 
            }
            f[i] /= i;
        }
        for (int i = 0; i <= x * y - 1; i++) {
            s[i] = (i ? s[i - 1] : 0) + f[i];
        }
        for (int i = 1; i <= 10; i++) { 
            int a, b;
            cin >> a >> b;
            cout << fixed << setprecision(9) << s[b] - (a ? s[a - 1] : 0) << endl;
        }
    }
    else {
        for (int i = 1; i <= 10; i++) {
            double a, b;
            cin >> a >> b;
            a = (a - mu) / sqrt(sigma);
            b = (b - mu) / sqrt(sigma);

            cout << fixed << setprecision(9) << use_simpson(0, b, eps, simpson(0, b), 10) - use_simpson(0, a, eps, simpson(0, a), 10) << endl;
        }
    }
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        auto_ac();
    }
    return 0;
}