競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2638 Hyperrectangle

考察に3時間ぐらいかかった気がするのでコンテスト中に解けなさそう...

解法

まず,全てのiについてs \le l_iの場合について考えると,2次元なら長さsの正三角形,3次元なら正三角錐,,,d次元の正三角錐三角錐かどうかは怪しい)になります.
次に,十分に大きいsについて,l_i =s-1である場合を考えると,先ほどの長さsのd次元の三角錐から長さ1の三角錐をd個削った形になります.
イメージとしては,長さsの正三角錐のそれぞれ角からs-l_iの長さの正三角錐を削り取った形が最終的に削り取る形になります.
角から削っていくと,重複して削られる部分が出てきます.ちょっと考えると重複して削られる部分の形も正三角錐になることがわかります.

また,d次元長さsの三角錐の体積(?)は\frac{s^d}{d!}となります.

これらを冷静になって一般化すると,包除原理を使って,
V=(a_1+a_2+a_3+...+a_d \le sの部分の体積)
-(l_1 \le a_1 \le sかつa_2+a_3+...+a_d \le s-l_1の部分の体積)
-(l_2 \le a_2 \le sかつa_1+a_3+...+a_d \le s-l_2の部分の体積)
-...

+(l_1 \le a_1 \le sかつl_2 \le a_2 \le sかつa_2+a_3+...+a_d \le s-l_1-l_2の部分の体積)
+(l_1 \le a_1 \le sかつl_3 \le a_3 \le sかつa_2+a_4+...+a_d \le s-l_1-l_3の部分の体積)
+...

となることがわかります.
このままだと状態数が2^dなのですが,
落ち着いて考えると,dp(K,L):=lをK個選んでL=s-l_{i_1}-l_{i_2}...-l_{i_K}となる(i_1,...,i_K)の組み合わせとすると,このDPはO(d^3l)で求められ,答えは(-1)^K * dp(K,L) * L^dの総和となります.
このままだとTLEですが,Kの部分については偶奇にしか興味がないのでmod2の値のみ保持すればよいです.
ので,これを使うとO(d^2l)で答えが求められます.

ソースコード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1959399#1
考察中はこんなスッキリした包除原理の式が出てこなくて,無限に三角錐を書いていたら思いつきました.

d=3
l=1,2,3
s=4
のケースを紙に書いてみると三角錐うんぬんが分かりやすいかもしれません
こんな感じの図になります(黒い部分が重複している部分
f:id:NitCoder000:20160812002730j:plain