BNU 34975 剪紙：折線劃分平面區域數大數模擬 + 規律公式

問題描述

平面上加入折線，每條折線由 X 段組成，第 i 段屬於類型 Y（方向）。求加入後平面被劃分的區域數模 MOD。多組操作，答案模 MOD 輸出。

規律推導

每次加入一條折線（X 段，類型 Y）：

• 新增直線段數 = X。
• 每段與現有所有直線相交（假設一般位置：無平行、無三線共點），產生交點數 = 當前總直線數。
• 每段被交點分成 (當前總直線數 + 1) 個小段，每小段將一個區域一分為二，新增區域數 = 當前總直線數 + 1。
• X 段總新增區域 = X * (當前總直線數 + 1) - (X-1) （首尾相連扣除重複）。
• 化簡後總區域數增量公式：Δ = X + Y * ( (2*curLines + (X-1)*Y) * X / 2 )。

大數處理

公式含除以 2，模 MOD 可能無逆元。但分子保證為偶數，用 Java BigInteger 精確計算後再取模。

參考代碼

BigInteger x1 = BigInteger.ONE, x2 = BigInteger.valueOf(2);
while (T--) {
    int n = in.nextInt(); long mod = in.nextLong();
    long curLines = 0, ans = 1 % mod;
    while (n--) {
        long X = in.nextLong(), Y = in.nextLong(); Y++;
        BigInteger now = BigInteger.valueOf(2*curLines + (X-1)*Y);
        now = now.multiply(BigInteger.valueOf(X)).divide(x2);
        now = now.mod(BigInteger.valueOf(mod));
        long tmp = now.longValue();
        tmp = (tmp * Y + X) % mod;
        ans = (ans + tmp) % mod;
        curLines = (curLines + X * Y) % mod;
    }
    System.out.println(ans);
}

總結

平面劃分區域數經典問題：每條新直線增加 (現有直線數+1) 區域。折線視為多段直線，利用等差數列求和推導 O(1) 增量公式。大數除法用 BigInteger 避免模逆元問題。數學推導是核心，代碼極簡。