AGC018 E : Sightseeing Plan(1600)
作成日：2017.07.28
最終更新日：2017.07.28
問題概要
2次元座標上において、3点$(p,q),(s,t),(u,v)$をこの順に最短で訪れるときの訪れ方を
$X_1 \leq p \leq X_2 , X_3 \leq s \leq X_4 , X_5 \leq u \leq X_6 ,$
$Y_1 \leq q \leq Y_2 , Y_3 \leq t \leq Y_4 , Y_5 \leq v \leq Y_6$を満たすものそれぞれ区別して総和を取り、
それを$10^9 + 7$で割った余りを求めよ。
制約
$1 \leq X_1 \leq X_2 \leq X_3 \leq X_4 \leq X_5 \leq X_6 \leq 10^6$
$1 \leq Y_1 \leq Y_2 \leq Y_3 \leq Y_4 \leq Y_5 \leq Y_6 \leq 10^6$
考え方
与えられた問題は(2次元の領域)$\rightarrow$(2次元の領域)$\rightarrow$(2次元の領域)であるが、難しいので次元が低いものから考える。
まず(0次元)$\rightarrow$(0次元)であるが、点$(0,0)$から点$(a,b)$(以下'点'は省略)への経路数は明らかに$a+b \choose a$である
（以下この値を$\langle a,b \rangle$で表す）。
次に(0次元)$\rightarrow$(1次元)を考える。
$(0,0)$から$(x,b)$への経路数は$0 \leq x \leq a$の時を求められれば、$x$が$0$から始まらない時も累積和のように求めることができる（このことは次元が上がっても同じ）。
これは下のような表を作って実際にいくつか計算してみることで$\sum_{0 \leq x \leq a}{\langle x,b \rangle} = \langle a,b+1 \rangle$であることに気付く。
このことは$(0,0)$から$(a,b+1)$へ行くためには必ず$(x,b) \rightarrow (x,b+1)$を通ることからも分かる。
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 2 | 3 | 4 | 5 |
| 2 | 1 | 3 | 6 | 10 | 15 |
| 3 | 1 | 4 | 10 | 20 | 35 |
| 4 | 1 | 5 | 15 | 35 | 70 |
さらに(0次元)$\rightarrow$(2次元)を考える。
つまり$(0,0)$から$(x,y)$(但し$0 \leq x \leq a , 0 \leq y \leq b$)の経路数の総和を考えれば良い。
これは(0次元)$\rightarrow$(1次元)の時の考察から
\[
\sum_{0 \leq y \leq b}{\sum_{0 \leq x \leq a}{\langle x,y \rangle}}
= \sum_{0 \leq y \leq b}{\langle a,y+1 \rangle}
= \sum_{0 \leq y \leq b+1}{\langle a,y \rangle} - 1
= \langle a+1,b+1 \rangle - 1
\]
である($\because \langle a,0 \rangle = 1 , \langle x,y \rangle = \langle y,x \rangle$)。
以上より、$(0,0)$から2次元の領域内$[(a_1,b_1),(a_2,b_2)]$の点に行く時の経路数は
\[
\langle a_2 + 1 , b_2 + 1 \rangle - \langle a_2 + 1 , b_1 \rangle - \langle a_1 , b_2 + 1 \rangle + \langle a_1,b_1 \rangle
\]
である($-1$は打ち消しあったことに注意)。
すなわち、2次元の領域の代わりに4点$(a_2 + 1 , b_2 + 1),(a_2 + 1 , b_1),(a_1 , b_2 + 1),(a_1 , b_1)$に行く経路数のみを考えれば良いことが分かる。
そこで$(s,t)$を基準にして、領域$[(X_1,Y_1),(X_2,Y_2)],[(X_5,Y_5),(X_6,Y_6)]$をそれぞれ4点に縮約する。
すると前者は$(X_1 + 1 , Y_1 + 1),(X_1 + 1 , Y_2),(X_2 , Y_1 + 1),(X_2 , Y_2)$、
後者は$(X_6 + 1 , Y_6 + 1),(X_6 + 1 , Y_5),(X_5 , Y_6 + 1),(X_5 , Y_5)$となる。
これにより$4 \times 4 = 16$通りの点の組み合わせにおいて、(1点) $\rightarrow$ (領域) $\rightarrow$ (1点)の経路数を求めれば良くなった。
このままでは計算量は$O((X_4 - X_3)(Y_4 - Y_3))$であり、間に合わない。
また、通過する領域に対してこれまでの議論を適用することはできないので、別の方法を考える。
そのために、領域を通過するためにはその領域に入った後、出る必要があるということに注目する。
条件を満たすある経路において、領域内で最初に通る点(入る点)、最後に通る点(出る点)をそれぞれ$(a,b),(c,d)$とする。
このとき領域内で通過する点の数は$(c-a)+(d-b)+1$である。
入る点と出る点で別に計算しないと計算量が落ちないことから、この数を$(c+d+1) - (a+b)$と変形して分けて計算できるようにする。
すなわち入る点に対しては$-(a+b)$、出る点に対しては$c+d+1$の重み付けをするということである。
これにより(1点) $\rightarrow$ (入る直前の点) $\rightarrow$ (入る点) $\rightarrow$ (1点) 及び
(1点) $\rightarrow$ (出る点) $\rightarrow$ (出た直後の点) $\rightarrow$ (1点)の経路数に重み付けしたものをを各入る点、出る点において計算すれば良いことが分かる。
また、この時の計算量は$O((X_4 - X_3) + (Y_4 - Y_3))$なので間に合う。
ソースコード
マクロ等はこちら
const int MC = 2000010;
const LL MOD = 1e9 + 7;
int X[6] , Y[6];
LL fct[MC]; //iの階乗
LL inv[MC]; //iの階乗の逆数
LL ans;
void build(){ //fct,invを計算
fct[0] = fct[1] = 1;
repp(i,2,MC){
fct[i] = fct[i-1] * i % MOD;
}
LL x = fct[MC-1];
inv[MC-1] = 1;
for(int i = MOD - 2 ; i > 0 ; i >>= 1){
if(i % 2 == 1) (inv[MC-1] *= x) %= MOD;
(x *= x) %= MOD;
}
repm(i,MC-1,0){
inv[i-1] = inv[i] * i % MOD;
}
}
LL comb(int x , int y){ //<x,y>
if(x < 0 || y < 0) return 0;
return fct[x+y] * inv[x] % MOD * inv[y] % MOD;
}
int main(){
repp(i,0,6) scanf("%d" , X + i);
repp(i,0,6) scanf("%d" , Y + i);
int p[2] = {X[0]-1 , X[1]};
int q[2] = {Y[0]-1 , Y[1]};
int u[2] = {X[4] , X[5]+1};
int v[2] = {Y[4] , Y[5]+1};
build();
repp(i,0,4){
repp(j,0,4){
LL z = abs(2*i-3) == abs(2*j-3) ? 1 : (MOD-1);
repp(s,X[2],X[3]+1){
(ans += comb(s-p[i/2] , Y[2]-1-q[i%2]) * comb(u[j/2]-s , v[j%2]-Y[2])
% MOD * (MOD-s-Y[2]) % MOD * z) %= MOD;
(ans += comb(s-p[i/2] , Y[3]-q[i%2]) * comb(u[j/2]-s , v[j%2]-Y[3]-1)
% MOD * (s+Y[3]+1) % MOD * z) %= MOD;
}
repp(t,Y[2],Y[3]+1){
(ans += comb(X[2]-1-p[i/2] , t-q[i%2]) * comb(u[j/2]-X[2] , v[j%2]-t)
% MOD * (MOD-X[2]-t) % MOD * z) %= MOD;
(ans += comb(X[3]-p[i/2] , t-q[i%2]) * comb(u[j/2]-X[3]-1 , v[j%2]-t)
% MOD * (X[3]+t+1) % MOD * z) %= MOD;
}
}
}
printf("%lld\n" , ans);
return 0;
}解法まとめ
$4 \times 4 = 16$の点対において、領域の出入口それぞれに対して重みづけした経路数を足し合わせていく。(37-53行)
この時、点対にも$\pm 1$の重みがついていることに注意する。