HDU 4873 ZCC Loves Intersection：大數運算與概率期望的數學建模

題目大意

在 D 維坐標系中（每維範圍 0 ~ N-1），有 D 條線段分別平行於各坐標軸。每秒隨機生成線段位置。兩兩線段相交得 1 分。求每秒得分期望值，輸出不可約分數 p/q。

數學推導

總情況數：(N * C(2N, 2))^D（每維獨立選兩點定線段）。
兩條特定維度線段相交的情況數 s（二維情況）：

s = Σ_{i=1}^{N} (N-i+1)*(i-1) = (N^3 + 3N^2 + 4N) / 6

期望得分 = C(D, 2) * s * (N * C(2N, 2))^{D-2} / (N * C(2N, 2))^D
化簡得：

ans = C(D, 2) * (N+4)^2 / (9 * N^D)

大數處理策略

• 分子分母極大（N^D 超過 64 位），需高精度整數（bign 類）。
• 直接高精度除法效率低，改用質因子分解約分：

// 分解 N 的質因子
void divfact(int n) {
    for (int i=2; i*i<=n; i++) if (n%i==0) {
        num[cnt++] = i;
        while (n%i==0) n/=i;
    }
    if (n!=1) num[cnt++] = n;
}

// 主流程
bign q = power(N, D) * 9;
bign p = D*(D-1)/2 * (N+4) * (N+4);
divfact(N);
num[cnt++] = 3; // 分母額外因子 3^2

for (int i=0; i

struct bign {
    int len, num[MAXN];
    // 構造、賦值、比較、輸出
    void Put(); // 高位到低位輸出
    // 運算符重載
    bign operator+(const bign&);
    bign operator-(const bign&);
    bign operator*(int);      // 乘 int
    bign operator*(const bign&);
    bign operator/(int);      // 除 int
    int  operator%(int);      // 模 int
};

bign power(bign x, int d) {
    bign ans = 1;
    while (d) {
        if (d & 1) ans = ans * x;
        x = x * x;
        d >>= 1;
    }
    return ans;
}