TopCoderOpen 2016 Round2B Easy TriangleTriples

TCOらしからぬ問題？
https://community.topcoder.com/stat?c=problem_statement&pm=14286

問題

正整数A,B,Cが与えられる。
1≦a≦A、1≦b≦B、1≦c≦Cを満たす整数(a,b,c)の組のうち、３辺がこの長さを持つ正の面積の三角形が存在できるものは何通りあるか。

解法

(a,b,c)の組み合わせA*B*C通りから、三角形が作れないものを除こう。
三角形を作るには、a+b＞c、b+c＞a、c+a＞bのすべてを満たさなければならない。
逆にa+b≦c、b+c≦a、c+a≦bのいずれか１つでも満たしたら三角形を作れない。
また、この３条件は３つ同時に満たすことはなく、満たせるのは１つである。
そこで上記条件に相当するものをそれぞれ取り除こう。

これには、立体図形を考えるとよい。
(1,1,1)-(A,B,C)を対角線とする直方体から、上記３条件に相当する部分を取り除き、その格子点を数えることになる。
例えばb+c≦aなら、(A,1,1),(2,1,1),(A,A-1,1),(A,1,A-1)を結んだ三角錐を取り除くことになる。
その際、三角錐と直方体の共通部分だけを取り除かなければならない。
これは包除原理の要領で三角錐の足し引きをすればよい。

ll mo=1000000007;

class TriangleTriples {
	public:
	ll tri(ll a) {
		if(a<1) return 0;
		return a*(a+1)%mo*(a-1)%mo*((mo+1)/6)%mo;
	}
	
	int count(int A, int B, int C) {
		if(A>B) swap(A,B);
		if(B>C) swap(B,C);
		if(A>B) swap(A,B);
		
		ll ret=1LL*A*B%mo*C%mo;
		ret -= tri(A);
		ret -= tri(B);
		ret += tri(B-A);
		ret -= tri(C);
		ret += tri(C-A);
		ret += tri(C-B);
		ret -= tri(C-A-B);
		
		return (ret%mo+mo)%mo;
		
	}
}

まとめ

本番は式をグリグリこねまわしてコーナーケースで落とした。