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は考察パートが難しい…
- 定式化が大事
