标签：概率生成函数

CometOJ 37F 真实无妄她们的人生之路

第一道非板子的多点求值题。

题意：

有$n$个物品，每个物品使用后有$p_i$的概率升一级（初始时等级为0），有$1-p_i$的概率不升级。

等级为$i$时的攻击力为$a_i$。

现在要求对于每一个$i\in [1,n]$，依次求出不使用第$i$件物品，但是使用了剩下的$n-1$件物品时，攻击力的期望。

$n\leq 10^5$，所有运算在模$998244353$意义下进行。

时限$10s$(Comet OJ的评测机非常烂)。

题解

对于第$i$个物品，构造多项式$C_i(x)=1-p_i+p_ix$，显然不使用第$i$个物品，但是使用了剩下所有物品的概率生成函数为$P_i(x)=\frac {\prod_{1\leq j\leq n}C_j(x)}{C_j(x)}$，计算这个多项式对序列${a_i}$的点积即不使用第$i$个物品的答案。

但是很显然这样只能做到$O(n^2+n\log n)$，考虑其他做法。

$$ \text{构造一个多项式函数}g\left( F \right) =\sum_{0\le i\le n-1}{a_i\times \left[ x^i \right] F\left( x \right)} \\ \text{显然则有}g\left( F+G \right) =g\left( F \right) +g\left( G \right) ,\text{其中}F,G\text{均为多项式。} \\ g\left( cF \right) =cg\left( F \right) ,\text{其中}c\text{是常数。} \\ \text{令}F\left( x \right) =\prod_{1\le i\le n}{\left( 1-p_i+p_ix \right)}, \\ \text{我们要求的结果则为所有的}g\left( \frac{F\left( x \right)}{1-p_i+p_ix} \right) ,\text{即}\frac{1}{1-p_i}g\left( \frac{F\left( x \right)}{1+\frac{p_i}{1-p_i}x} \right) \text{。} \\ \text{如果}p_i=\text{1,那么显然可以比较便捷的计算出答案，以下假设}p_i\ne 1 \\ \text{由于}\frac{1}{1-x}=\sum_{i\ge 0}{x^i} \\ \text{故}\frac{1}{x}=\sum_{i\ge 0}{\left( 1-x \right) ^i} \\ \text{故}\frac{1}{1-p_i}g\left( \frac{F\left( x \right)}{1+\frac{p_i}{1-p_i}x} \right) =\frac{1}{1-p_i}g\left( \sum_{j\ge 0}{F\left( x \right) \left( -\frac{p_i}{1-p_i}x \right) ^j} \right) \\ \text{又由于}g\left( A+B \right) =g\left( A \right) +g\left( B \right) \\ \text{故}\frac{1}{1-p_i}\sum_{j\ge 0}{g\left( F\left( x \right) \left( -\frac{p_i}{1-p_i} \right) ^j\times x^j \right)} \\ \text{又由于}g\left( cA \right) =cg\left( A \right) \\ \text{可得}\frac{1}{1-p_i}\sum_{j\ge 0}{\left( -\frac{p_i}{1-p_i} \right) ^jg\left( F\left( x \right) x^j \right)} \\ \text{令多项式}G\left( y \right) =\sum_{j\ge 0}{y^jg\left( F\left( x \right) x^j \right)} \\ \text{则答案可以通过计算出多项式}G\left( y \right) \text{后通过多点求值}G\left( -\frac{p_1}{1-p_1} \right) ,G\left( -\frac{p_2}{1-p_2} \right) …G\left( -\frac{p_n}{1-p_n} \right) \text{得到。} \\ \text{显然在}j\ge n\text{时有}g\left( F\left( x \right) x^j \right) \text{为0，所以}G\left( y \right) \text{的次数为}n \\ \text{考虑}g\left( F\left( x \right) x^j \right) \text{如何计算，}g\left( F\left( x \right) x^j \right) =\sum_{0\le i\le n-1}{a_i\times \left[ x^i \right] F\left( x \right) x^j}=\sum_{0\le i\le n-1}{a_i\times \left[ x^{i-j} \right] F\left( x \right)} \\ \text{构造多项式}F_0\left( x \right) =\sum_{0\le i\le n-1}{a_ix^i},\text{然后计算}F_0\left( x \right) \left( xF^R\left( x \right) \right) ,\text{其}i+n\text{次项前的系数即为}g\left( F\left( x \right) x^i \right) \\ $$

#pragma GCC optimize("O3")
#include <assert.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <fstream>
#include <iostream>
#include <vector>
// #include
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 5e5;
const int_t mod = 998244353;
const int_t g = 3;

void transformX(int_t* A, int_t len, int_t g, int_t mod);
void transformNTT(int_t* A, int_t size2, int_t arg);
std::vector<int_t> poly_dc_mul(const std::vector<int_t>& A);
void poly_inv(const int_t* A, int_t n, int_t* result);
void poly_div(const int_t* A, int_t n, const int_t* B, int_t m, int_t* R);
std::vector<int_t> poly_eval(const std::vector<int_t>& poly,
                             const std::vector<int_t>& vals);

void poly_mul(const int_t* A, int_t n, const int_t* B, int_t m, int_t* A0);
int_t power(int_t base, int_t index) {
    int_t result = 1;
    base = (base % mod + mod) % mod;
    index = (index % (mod - 1) + mod - 1) % (mod - 1);
    while (index) {
        if (index & 1) result = (int_t)result * base % mod;
        index >>= 1;
        base = (int_t)base * base % mod;
    }
    assert(result >= 0);
    return result % mod;
}

int flips[20][LARGE];
const auto flip = [=](int x, int size2) {
    int result = 0;
    for (int i = 1; i < size2; i++) {
        result |= (x & 1);
        x >>= 1;
        result <<= 1;
    }
    return result | (x & 1);
};
std::vector<int_t> poly_dc_mul2(const std::vector<int_t>& A) {
    if (A.size() == 1) {
        return std::vector<int_t>{(int_t)((1 - A[0] + mod) % mod), A[0]};
    }
    std::vector<int_t> left, right;
    for (int i = 0; i < A.size(); i++) {
        if (i < A.size() / 2)
            left.push_back(A[i]);
        else
            right.push_back(A[i]);
    }
    auto leftr = poly_dc_mul2(std::move(left)),
         rightr = poly_dc_mul2(std::move(right));
    std::vector<int_t> result(leftr.size() + rightr.size() + 5);
    poly_mul(&leftr.front(), leftr.size() - 1, &rightr.front(),
             rightr.size() - 1, &result.front());
    while (result.empty() == false && result.back() == 0) result.pop_back();
    return result;
}

int main() {
    for (int i = 1; i < 19; i++) {
        for (int j = 1; j < (1 << i); j++) flips[i][j] = flip(j, i);
    }
    int_t n;
    static int_t pros[LARGE + 1], as[LARGE + 1], Fx[LARGE + 1];
    std::vector<int_t> F;
    scanf("%lld", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &as[i]);
    }
    for (int i = 1; i <= n; i++) {
        int_t x, y;
        scanf("%lld%lld", &x, &y);
        pros[i] = ((int_t)x * ((int_t)power(y, -1) % mod)) % mod;
        assert(pros[i] < mod);
        F.push_back(pros[i]);
    }
    F = poly_dc_mul2(F);
    int_t oneans = 0;
    for (int i = 1; i <= n; i++) {
        oneans = (oneans + (int_t)F[i] * as[i - 1] % mod) % mod;
    }
    F.push_back(0);
    std::reverse(F.begin(), F.end());
    poly_mul(as, F.size() - 1, &F.front(), F.size() - 1, Fx);
    std::copy(Fx + F.size() - 1, Fx + F.size() - 1 + n, Fx);
    std::vector<int_t> poly(Fx, Fx + n);
    std::vector<int_t> point_ts;
    for (int i = 1; i <= n; i++) {
        point_ts.push_back(
            (mod - (int_t)pros[i] * (int_t)power(1 - pros[i] + mod, -1) % mod) %
            mod);
    }
    auto res = poly_eval(poly, point_ts);
    for (int i = 1; i <= n; i++) {
        if (pros[i] == 1) {
            printf("%lld ", oneans);
        } else {
            printf("%lld ",
                   (int_t)res[i - 1] * power(1 - pros[i] + mod, -1) % mod);
        }
    }
    return 0;
}

void poly_mul(const int_t* A, int_t n, const int_t* B, int_t m, int_t* A0) {
    static int_t Ax[LARGE + 1], Bx[LARGE + 1];
    int size2 = 0;
    while ((1 << size2) < n + m + 1) size2++;
    int len = 1 << size2;
    for (int i = 0; i < len; i++) {
        if (i <= n)
            Ax[i] = A[i];
        else
            Ax[i] = 0;
        if (i <= m)
            Bx[i] = B[i];
        else
            Bx[i] = 0;
    }
    transformNTT(Ax, size2, 1);
    transformNTT(Bx, size2, 1);
    for (int i = 0; i < len; i++) Ax[i] = (int_t)Ax[i] * Bx[i] % mod;
    transformNTT(Ax, size2, -1);
    const int_t inv = power(len, mod - 2);
    for (int i = 0; i <= n + m; i++) A0[i] = (int_t)Ax[i] * inv % mod;
}
void transformNTT(int_t* A, int_t size2, int_t arg) {
    for (int i = 0; i < (1 << size2); i++) {
        int x = flips[size2][i];
        if (x > i) std::swap(A[i], A[x]);
    }
    for (int i = 2; i <= (1 << size2); i *= 2) {
        int_t mr = power(g, (mod - 1) + (mod - 1) / i * arg);
        for (int j = 0; j < (1 << size2); j += i) {
            int_t curr = 1;
            for (int k = 0; k < i / 2; k++) {
                int_t u = A[j + k] % mod,
                      t = (int_t)A[j + k + i / 2] * curr % mod;
                A[j + k] = (u + t) % mod;
                A[j + k + i / 2] = (int_t)((int_t)u - t + mod) % mod;
                curr = (int_t)curr * mr % mod;
            }
        }
    }
}
void poly_inv(const int_t* A, int_t n, int_t* result) {
    if (n == 1) {
        result[0] = power(A[0], mod - 2);
        return;
    }
    poly_inv(A, n / 2 + n % 2, result);
    static int_t temp[LARGE + 1];
    std::fill(temp, temp + 2 * n, 0);
    int prev = n / 2 + n % 2;
    poly_mul(result, prev - 1, result, prev - 1, temp);
    poly_mul(A, n - 1, temp, n - 1, temp);
    for (int i = 0; i < n; i++)
        result[i] = (2 * result[i] % mod - temp[i] + 2 * mod) % mod;
}
//计算n次多项式A整除B次多项式m的余数
void poly_div(const int_t* A, int_t n, const int_t* B, int_t m, int_t* R) {
    while (n >= 0 && A[n] == 0) n--;
    while (m >= 0 && B[m] == 0) m--;
    if (n < m) {
        std::copy(A, A + n + 1, R);
        return;
    }
    static int_t AR[LARGE + 1], BR[LARGE + 1];
    for (int i = 0; i <= n; i++) AR[i] = A[n - i];
    for (int i = 0; i <= m; i++) BR[i] = B[m - i];
    for (int i = m + 1; i <= n - m; i++) BR[i] = 0;
    static int_t inv[LARGE + 1], Q[LARGE + 1], C[LARGE + 1];
    std::fill(inv, inv + n - m + 1, 0);
    poly_inv(BR, n - m + 1, inv);
    poly_mul(AR, n - m, inv, n - m, Q);
    std::reverse(Q, Q + n - m + 1);
    poly_mul(Q, n - m, B, m, C);
    for (int_t i = 0; i < m; i++) R[i] = (A[i] - C[i] + mod) % mod;
}
std::vector<int_t> poly_dc_mul(const std::vector<int_t>& A) {
    if (A.size() == 1) {
        return std::vector<int_t>{(int_t)mod - A[0], 1};
    }
    std::vector<int_t> left, right;
    for (int i = 0; i < A.size(); i++) {
        if (i < A.size() / 2)
            left.push_back(A[i]);
        else
            right.push_back(A[i]);
    }
    auto leftr = poly_dc_mul(std::move(left)),
         rightr = poly_dc_mul(std::move(right));
    std::vector<int_t> result(leftr.size() + rightr.size() + 5);
    poly_mul(&leftr.front(), leftr.size() - 1, &rightr.front(),
             rightr.size() - 1, &result.front());
    while (result.empty() == false && result.back() == 0) result.pop_back();
    return result;
}

// vals是求值点
std::vector<int_t> poly_eval(const std::vector<int_t>& poly,
                             const std::vector<int_t>& vals) {
    if (vals.size() <= 300) {
        std::vector<int_t> result;
        for (auto x : vals) {
            int_t curr = 0, pow = 1;
            for (auto y : poly) {
                curr = ((int_t)curr + (int_t)y * pow % mod) % mod;
                pow = (int_t)pow * x % mod;
            }
            result.push_back(curr);
        }
        return result;
    }
    std::vector<int_t> left, right;
    for (int i = 0; i < vals.size(); i++)
        if (i < vals.size() / 2)
            left.push_back(vals[i]);
        else
            right.push_back(vals[i]);
    auto leftres = poly_dc_mul(left);
    auto rightres = poly_dc_mul(right);
    std::vector<int_t> pleft(leftres.size() - 1), pright(rightres.size() - 1);
    poly_div(&poly.front(), poly.size() - 1, &leftres.front(),
             leftres.size() - 1, &pleft.front());
    poly_div(&poly.front(), poly.size() - 1, &rightres.front(),
             rightres.size() - 1, &pright.front());
    auto leftx = poly_eval(pleft, left);
    auto rightx = poly_eval(pright, right);
    // assert(leftres.size())
    for (auto x : rightx) leftx.push_back(x);
    return leftx;
}

2019年4月28日

CTSC2018 假面

$$ \text{设}f\left( n,k \right) \text{表示第}n\text{个人，剩余血量为}k\text{的概率。} \\ \text{显然初始时}f\left( n,m_n \right) =\text{1,}f\left( n,m_k \right) =0\left( k\ne n \right) \\ \text{每一次操作1可以进行以下转移} \\ f\left( n,i \right) \gets \left( 1-p \right) f\left( n,i \right) +p\times f\left( n,i+1 \right) \left( i\ge 1 \right) \\ \text{特别的，}f\left( n,0 \right) \gets \left( 1-p \right) f\left( n,0 \right) +p\times \left( f\left( n,1 \right) +f\left( n,0 \right) \right) =f\left( n,0 \right) +p\times f\left( n,1 \right) \left( \text{此时再怎么扣血也还是}0 \right) \\ \text{单次操作1复杂度为}O\left( m_i \right) \\ \text{考虑操作}2 \\ \text{考虑生成函数}F\left( x \right) ,\text{其中}i\text{次项的意义是集合内还活着}i\text{个人的概率。} \\ \text{对于集合内的第}i\text{个人}\left( \text{设其为}a_i \right) ,\text{构造一个多项式}F_i\left( x \right) =\left( f\left( a_i,0 \right) +\left( 1-f\left( a_i,0 \right) \right) x \right) \\ \text{显然,}\prod{F_i\left( x \right)}\text{就是集合内还活着}i\text{个人的概率生成函数。} \\ \text{考虑如何对于每一个人统计答案} \\ \frac{\prod{F_i\left( x \right)}}{F_i\left( x \right)}\text{是除了集合内第}i\text{个人之外，剩下的人还活了}n\text{个的生成函数。} \\ \text{求出来这个多项式后，设其}j\text{次项前次数为}b_j,\text{则第}i\text{个人被命中的概率为} \\ \left( 1-f\left( a_i,0 \right) \right) \sum_{0\le j\le k-1}{\frac{b_j}{j+1}},\text{即保证这个人活着的前提下，依次枚举剩下还有几个人活着，从这些人中} \\ \text{选中第}i\text{个人。} \\ \text{实际由于涉及到的多项式次数较小，不需要}NTT\text{，直接暴力乘除即可。} \\ \\ $$

#include <assert.h>
#include <algorithm>
#include <cstring>
#include <iostream>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int mod = 998244353;
const int_t LARGE = 205;
int power(int base, int index) {
    const int phi = mod - 1;
    int result = 1;
    index = (index % phi + phi) % phi;
    while (index) {
        if (index & 1) result = 1ll * result * base % mod;
        index >>= 1;
        base = 1ll * base * base % mod;
    }
    return result;
}
int_t health[LARGE + 1];
int_t f[LARGE + 1][102];
int n, q;
void poly_multipy(const int_t* A, int_t n, const int_t* B, int_t m, int_t* C) {
    static int_t D[LARGE + 1];
    // std::fill(D, D + n + m + 1, 0);
    memset(D, 0, sizeof(int_t) * (n + m + 1));
    for (int_t i = 0; i <= n; i++) {
        for (int_t j = 0; j <= m; j++) {
            D[i + j] = (D[i + j] + A[i] * B[j] % mod) % mod;
        }
    }
    // std::copy(D, D + n + m + 1, C);
    memcpy(C, D, sizeof(int_t) * (n + m + 1));
}
void poly_divide(const int_t* A, int_t n, const int_t* B, int_t m, int_t* Q) {
    while (n >= 0 && A[n] == 0) n--;
    while (m >= 0 && B[m] == 0) m--;
    static int_t C[LARGE + 1];
    // std::copy(A, A + n + 1, C);
    memcpy(C, A, sizeof(int_t) * (n + 1));
    const int_t inv = power(B[m], -1);
    for (int_t i = n - m; i >= 0; i--) {
        int_t x = C[i + m] * inv % mod;
        Q[i] = x;
        for (int_t j = m; j >= 0; j--) {
            C[i + j] = (C[i + j] - B[j] * x + 2 * mod) % mod;
        }
    }
}
int main() {
    scanf("%d", &n);
    for (int_t i = 1; i <= n; i++) {
        scanf("%lld", &health[i]);
        f[i][health[i]] = 1;
    }
    scanf("%d", &q);
    for (int _i = 1; _i <= q; _i++) {
        int opt;
        scanf("%d", &opt);
        if (opt == 0) {
            int target;
            int_t u, v;
            scanf("%d%lld%lld", &target, &u, &v);
            int_t p = u * power(v, -1) % mod;
            static int_t fx[102];
            auto& f = ::f[target];
            fx[0] = (f[0] + f[1] * p) % mod;
            for (int_t i = 1; i <= health[target]; i++) {
                fx[i] = ((mod + 1 - p) * f[i] + p * f[i + 1]) % mod;
            }
            for (int_t i = 0; i <= health[target]; i++) f[i] = fx[i];
        } else {
            // assert(false);
            int k;
            scanf("%d", &k);
            static int_t targets[LARGE + 1];
            for (int_t i = 1; i <= k; i++) {
                scanf("%lld", &targets[i]);
            }
            static int_t g[LARGE + 1], gx[10];
            memset(g, 0, sizeof(g));
            memset(gx, 0, sizeof(gx));
            g[0] = 1;
            //乘到一起
            for (int_t i = 1; i <= k; i++) {
                gx[0] = f[targets[i]][0];
                gx[1] = (1 - gx[0] + mod) % mod;
                poly_multipy(g, k, gx, 1, g);
            }
            //除掉第i个
            for (int_t i = 1; i <= k; i++) {
                int_t result = 0;
                gx[0] = f[targets[i]][0];
                gx[1] = (1 - gx[0] + mod) % mod;
                static int_t Q[LARGE + 1];
                //Q数组没清空导致上一次的结果影响到这一次
                memset(Q, 0, sizeof(Q));
                poly_divide(g, k, gx, 1, Q);
#ifdef DEBUG
                cout << "query " << _i << endl;
                for (int_t i = 0; i <= k - 1; i++) cout << Q[i] << " ";
                cout << endl;
#endif
                for (int_t j = 0; j <= k - 1; j++) {
                    result = (result + Q[j] * power(j + 1, -1) % mod) % mod;
                }
                result = result * (1 - f[targets[i]][0] + mod) % mod;
                printf("%lld ", (result % mod + mod) % mod);
            }
            printf("\n");
        }
    }
    for (int_t i = 1; i <= n; i++) {
        int_t sum = 0;
        for (int_t j = 0; j <= health[i]; j++) {
            sum = (sum + j * f[i][j]) % mod;
#ifdef DEBUG
            cout << "f " << i << " " << j << " = " << f[i][j] << endl;
#endif
        }
        printf("%lld ", sum);
    }
    return 0;
}

2019年2月26日

SDOI2017 龙与地下城

$$ \text{题意:} \\ \text{若干个随机变量}x_1,x_2…x_Y \\ \text{每个随机变量在}\left[ \text{0,}X-1 \right] \text{内等概率随机取值} \\ \text{求}\sum_{1\le i\le Y}{x_i}\text{落在区间}\left[ A,B \right] \text{内的概率} \\ \text{考虑概率生成函数}F\left( x \right) =\sum_{0\le i\le X-1}{x^i\times \frac{1}{X}} \\ \left( F\left( x \right) \right) ^Y\text{中,}k\text{次项前的系数即为这些随机变量的和为}k\text{的概率。} \\ \,\,\text{把次数在}\left[ A,B \right] \text{之间的系数加起来即可} \\ \text{但这样的复杂度是}O\left( XY\log n \right) \text{的} \\ \text{考虑中心极限定理} \\ \text{设随机变量}\overline{x}=\frac{\sum_{1\le i\le Y}{x_i}}{Y} \\ \text{每个随机变量}x_i\text{的期望为}a=\frac{X-1}{2},\text{方差为}\sigma ^2=\frac{X^2-1}{12} \\ \text{在}Y\text{足够大的时候，可以近似认为}\overline{x}\text{服从正态分布}N\left( a,\frac{\sigma ^2}{Y} \right) \\ \text{所以大力辛普森积分}\int_{\frac{A}{Y}}^{\frac{B}{Y}}{\frac{e^{-\frac{\left( x-a \right) ^2}{2\sigma ^2}}}{\sqrt{2\pi \sigma ^2}}}dx,\text{其中}a=\frac{X-1}{2},\sigma ^2=\frac{X^2-1}{12Y} \\ \text{但是注意对于一些正态分布函数,其在大部分位置取值为0，只在少部分位置取值非0,这时候我们} \\ \text{可以强行让辛普森积分函数递归若干层来保证结果正确} \\ $$

#include <assert.h>
#include <algorithm>
#include <cmath>
#include <complex>
#include <iomanip>
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
using int_t = long long int;
using real_t = long double;
using cpx_t = std::complex<real_t>;
const real_t PI = std::acos(-1);
const int_t LARGE = 1 << 22;
const real_t EPS = 1e-5;
template <int_t arg = 1>
void transform(cpx_t* A, int_t size);
int_t upper2n(int_t x) {
    int_t res = 1;
    while (res < x) res *= 2;
    return res;
}
template <class Func>
real_t S(real_t a, real_t b, Func f) {
    return (b - a) / 6 * (f(a) + 4 * f((a + b) / 2) + f(b));
}
template <class Func>
real_t Simpson(real_t a, real_t b, Func f, int_t depth = 0) {
    real_t mid = (a + b) / 2;
    if (std::abs(S(a, b, f) - S(a, mid, f) - S(mid, b, f)) / 15 < EPS &&
        depth > 10)
        return S(a, b, f);
    return Simpson(a, mid, f, depth + 1) + Simpson(mid, b, f, depth + 1);
}
void process1(real_t x, real_t y) {
    static cpx_t A[LARGE + 1];
    static real_t prefix[LARGE + 1];
    int_t size = upper2n(x * y);
    std::fill(A, A + size, cpx_t(0));
    for (int_t i = 0; i <= x - 1; i++) A[i] = (real_t)1 / x;
    transform(A, size);
    for (int_t i = 0; i < size; i++) {
        A[i] = std::pow(A[i], y);
    }
    transform<-1>(A, size);
    for (int_t i = 0; i < size; i++) A[i] /= size;
    prefix[0] = A[0].real();
    for (int_t i = 1; i <= x * y; i++) prefix[i] = prefix[i - 1] + A[i].real();
    for (int_t i = 1; i <= 10; i++) {
        int_t a, b;
        cin >> a >> b;
        if (a > 0)
            cout << prefix[b] - prefix[a - 1] << endl;
        else
            cout << prefix[b] << endl;
    }
}
void process2(real_t x, real_t y) {
    real_t a = (x - 1) / 2;
    real_t sigmap2 = (x * x - 1) / 12 / y;
    for (int_t i = 1; i <= 10; i++) {
        real_t A, B;
        cin >> A >> B;
        cout << Simpson(A / y + EPS, B / y + EPS,
                        [=](real_t x) -> real_t {
                            return expl(-(x - a) * (x - a) / (2 * sigmap2)) /
                                   sqrtl(2 * M_PI * sigmap2);
                        })

             << endl;
    }
}
void process() {
    int_t x, y;
    cin >> x >> y;
    if (x * y <= 3e5)
        process1(x, y);
    else
        process2(x, y);
}
int main() {
    int_t T;
    cin >> T;
    for (int_t i = 1; i <= T; i++) {
        cout.setf(std::ios::fixed);
        cout << std::setprecision(10);
        process();
    }
    return 0;
}
int_t bitRev(int_t x, int_t size2) {
    int_t result = 0;
    for (int_t i = 1; i < size2; i++) {
        result |= (x & 1);
        x >>= 1;
        result <<= 1;
    }
    return result | (x & 1);
}
template <int_t arg = 1>
void transform(cpx_t* A, int_t size) {
    int_t size2 = log2(size);
    for (int_t i = 0; i < size; i++) {
        int_t x = bitRev(i, size2);
        if (x > i) std::swap(A[i], A[x]);
    }
    for (int_t i = 2; i <= size; i *= 2) {
        auto mr = cpx_t(cosl(2 * PI / i), arg * sinl(2 * PI / i));
        for (int_t j = 0; j < size; j += i) {
            cpx_t curr(1, 0);
            for (int_t k = 0; k < i / 2; k++) {
                auto u = A[j + k];
                auto t = curr * A[j + k + i / 2];
                A[j + k] = u + t;
                A[j + k + i / 2] = u - t;
                curr *= mr;
            }
        }
    }
}

2018年12月29日

标签： 概率生成函数

CometOJ 37F 真实无妄她们的人生之路

题意：

题解

CTSC2018 假面

SDOI2017 龙与地下城

标签：概率生成函数