BNU 34975 剪紙 折線劃分平面問題 大數模擬+規律

BNU 34975 剪紙 折線劃分平面問題 大數模擬+規律

題目鏈接：點擊打開鏈接

最多的情況就是每個直線和當前平面的所有直線都相交

設當前有x根直線

則加入一個type0的直線就能產生 x個交點，兩個交點間的線段可以把一個平面劃分成2個

就能增加x + 1個平面

再推廣 若加入typeY 的直線

先讓Y++，表示加入直線的根數

就能增加 (x + 1) * Y - (Y-1)

加完後 平面上的直線數就增加了Y ：即 x+=Y

所以每次加入 X 根 Y類型的直線

則答案增加的情況就是：

Y++;

ans += (x +1) *Y - (Y-1)

ans += (x +1 + Y) * Y - (Y-1)

·

·

·

ans += (x+1 + (X-1)*Y) * Y - (Y-1)

然後化簡一下就是

ans += x*Y +1

ans += (x+Y)*Y+1

·

·

·

ans+=(x+(X-1)*Y) *Y +1

發現ans一共加了 X 個1 然後第一部分是 Y * (等差數列）

再化簡成

ans += X + Y*( ( x + x+(X-1)*Y ) * X / 2);

這樣我們就能O(1) 算出 每增加一次 答案的增值

但是這裡取模會出現問題

/2 的情況逆元可能不存在，

但能保證 ( x + x+(X-1)*Y ) * X 一定是偶數，所以用個大數直接進行運算。

import java.math.*;
import java.util.*;
import java.io.*;
public class Main {
    static BigInteger x1 = new BigInteger("1");
    static BigInteger x2 = new BigInteger("2");
    public void work() {
        int T;
        T = cin.nextInt();
        while (T-- > 0) {
            int n = cin.nextInt();
            long mod = cin.nextLong();
            long x = 0;
            long ans = 1 % mod;
            while(n-->0)
            {
                long X = cin.nextLong(), Y = cin.nextLong();
                Y++;
                BigInteger now = BigInteger.valueOf(2*x + (X-1)*Y);
                now = now.multiply(BigInteger.valueOf(X));
                now = now.divide(BigInteger.valueOf(2));
                now = now.mod(BigInteger.valueOf(mod));
                long tmp = now.longValue();
                tmp *= Y; tmp%=mod;
                tmp += X; tmp%=mod;
                ans += tmp; ans %= mod;
                x += X*Y%mod;
                x %=mod;
            }
            ans = ans % mod;
            System.out.println(ans);
        }
    }
    Main() {
        cin = new Scanner(System.in);
    }
    public static void main(String[] args) {
        Main e = new Main();
        e.work();
    }
    public Scanner cin;
}