过样例

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
using namespace std;

typedef long long ll;
typedef long double db;
const db PI = acos(-1.0);
const db EPS = 1e-12;

typedef complex<db> cp;
vector<cp> f, g;
vector<int> rev;

void fft_init(int len) {
rev.resize(len);
int l = __lg(len);
for (int i = 0; i < len; ++i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
}

void fft(vector<cp>& a, int inv) {
int n = a.size();
for (int i = 0; i < n; ++i)
if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int mid = 1; mid < n; mid <<= 1) {
cp wn(cos(PI / mid), inv * sin(PI / mid));
for (int j = 0; j < n; j += mid << 1) {
cp w(1, 0);
for (int k = 0; k < mid; ++k, w *= wn) {
cp x = a[j + k], y = w * a[j + k + mid];
a[j + k] = x + y;
a[j + k + mid] = x - y;
}
}
}
if (inv == -1)
for (auto& x : a) x /= n;
}

vector<db> poly_mul(vector<db> a, vector<db> b) {
int n = 1;
while (n < (int)(a.size() + b.size() - 1)) n <<= 1;
f.resize(n); g.resize(n);
fft_init(n);
for (int i = 0; i < n; ++i) f[i] = (i < a.size() ? a[i] : 0);
for (int i = 0; i < n; ++i) g[i] = (i < b.size() ? b[i] : 0);
fft(f, 1); fft(g, 1);
for (int i = 0; i < n; ++i) f[i] *= g[i];
fft(f, -1);
vector<db> res(n);
for (int i = 0; i < n; ++i) res[i] = f[i].real();
return res;
}

vector<db> dice_pow(int X, ll Y) {
vector<db> base(X, 1.0 / X);
vector<db> res = {1.0};
while (Y > 0) {
if (Y & 1) res = poly_mul(res, base);
base = poly_mul(base, base);
Y >>= 1;
}
return res;
}

db norm(db x) {
return 1.0 / sqrt(2 * PI) * exp(-x * x / 2);
}

db simpson(db l, db r) {
return (r - l) * (norm(l) + 4 * norm((l + r) / 2) + norm(r)) / 6;
}

db integral(db l, db r, db eps, db S) {
db mid = (l + r) / 2;
db L = simpson(l, mid), R = simpson(mid, r);
if (fabs(L + R - S) < 15 * eps) return L + R + (L + R - S) / 15;
return integral(l, mid, eps / 2, L) + integral(mid, r, eps / 2, R);
}

db CDF(db x, db mu, db sigma) {
if (x < mu - 20 * sigma) return 0.0;
if (x > mu + 20 * sigma) return 1.0;
db z = (x - mu) / sigma;
return 0.5 + integral(0, z, 1e-8, simpson(0, z));
}

db query(ll A, ll B, db mu, db sigma, vector<db>& prob) {
if (!prob.empty()) {
db sum = 0.0;
ll mx = (ll)prob.size() - 1;
ll L = max(0LL, A);
ll R = min(mx, B);
for (ll i = L; i <= R; ++i) {
sum += prob[i];
}
return sum;
} else {
return CDF((db)B, mu, sigma) - CDF((db)A - 1.0, mu, sigma);
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.precision(6);
cout << fixed;

int T;
cin >> T;
while (T--) {
    int X; ll Y;
    cin >> X >> Y;
    db mu0 = (X - 1) / 2.0;
    db var0 = (1LL * X * X - 1) / 12.0;
    db mu = Y * mu0;
    db sigma = sqrt(Y * var0);
    vector<db> prob;

    if (Y <= 800) {
        prob = dice_pow(X, Y);
    }

    for (int i = 0; i < 10; ++i) {
        ll A, B;
        cin >> A >> B;
        db ans = query(A, B, mu, sigma, prob);
        cout << ans << '\n';
    }
}
return 0;

}