SRM600D1Hard LotsofLines

D1Hardを埋めます

問題概要(原文)

整数 $A,B (1 \leq A,B \leq 1{,}200)$ が与えられる.$2$ 次元平面上に $a x + b$ という直線を $0 \leq a < A, 0 \leq b < B$ を満たす $a, b$ すべてについて追加する. いくつの領域(面積が有限でも無限でもよい)に区切られるか?

考察

適当に直線 $a x + b$ を入れたときに,いくつ領域が増えるか考える. $1+$ {すでに存在する直線たちと,この直線 $ax + b$ との交点の数} ,となることが分かる. さて, $(a,b)(0 \leq a <A, 0 \leq b < B)$ それぞれについて,交点の数を求められればよくなった. 愚直にやると $O(A^2 B^2)$ ぐらいになり,険しい.

ここで直線 $a x + b$ と $\alpha x + \beta$ の交点がどこになるか考える.

\[ \begin{aligned} ax + b & = \alpha x + \beta \\ x & = \frac{\beta - b}{a - \alpha} \end{aligned} \]

となる.$\frac{p}{q} = \frac{\beta - b}{a - \alpha}$ とすると, $-b \leq p < B-b,1 \leq q \leq a$ を満たす. $\frac{p}{q}$ が一意な値となるのは $gcd(p,q) = 1$ のときのみである.

$dp(x,y) = $ $(1 \leq i \leq x, j \leq 1 \leq j \leq y)$ を満たす $i,j$ のうち $gcd(i,j) = 1$ を満たすものの総数,とする. これは二次元累積和を用いて簡単に埋めることができる.

直線 $a x + b$ を追加するとき, $a \neq 0$ において,交点の数は $dp(a,|-b|) + 1 + dp(a,B-b-1)$ となる.これで $(p,q) (-b \leq p < B-b, 1 \leq q \leq a)$ を重複なく数えることができる. $a = 0$ において,交点はない.

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
using Number = System.Int64;
public class LotsOfLines
{
    public long countDivisions(int A, int B)
    {
        long ans = 1;
        var dp = new long[1250, 1250];
        for (int i = 1; i < 1220; i++)
            for (int j = 1; j < 1220; j++)
            {
                if (MathEx.GCD(i, j) == 1) dp[i, j] += 1;
                dp[i, j] += dp[i - 1, j] + dp[i, j - 1] - dp[i - 1, j - 1];
            }

        for (int a = 0; a < A; a++)
            for (int b = 0; b < B; b++)
            {
                ans++;
                if (a != 0)
                    ans += 1 + dp[a, b] + dp[a, B - b - 1];
            }
        return ans;
    }

}

#region gcd
static public partial class MathEx
{

    static public Number GCD(Number x, Number y)
    {
        byte i = 0;
        while (x != 0 && y != 0)
        {
            if (i == 0)
                y %= x;
            else x %= y;
            i ^= 1;
        }
        return x == 0 ? y : x;
    }
}
#endregion

コメント

  • Div1Hardは考察パートが難しい…
  • 定式化が大事