題目鏈接:點擊打開鏈接
最多的情況就是每個直線和當前平面的所有直線都相交
設當前有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; }