[TCO2016 Round 2B DIV1 Easy] TriangleTriples

    题意：给出\(a,b,c,1<=a,b,c<=10^9\)，求所有的满足\(1<=x<=a,1<=y<=b,1<=z<=c\)且由\(x,y,z\)为三边长能组成三角形的方案数。（\(a,b,c,x,y,z\)均为整数）

    题解：用容斥做这道题目会比较简单。首先设\(a<=b<=c\)。考虑容斥，答案即\(abc\)减去所有\(x>=y+z,y>=x+z,z>=x+y\)的方案数。由于\(x>=y+z,y>=x+z,z>=x+y\)是独立的，所以可以分别计算。

    考虑\(x>=y+z\)，由于\(y+z<=a\),那么显然有\begin{aligned}1<=x<=a \\ 1<=y<=a \\ 1<=z<=a \end{aligned}答案显然为\(\sum_{i=1}^{a-1}{\frac{i(i+1)}{2}}=\frac{a(a+1)(a-1)}{6}=C_{a+1}^{3}\)，后面的组合数可以理解为在\(0...a\)中选出三个点\(x_0,x_1,x_2,0<=x_0<x_1<x_2<=a\)，取\(x=x_2,y=x_2-x_1,z=x_1-x_0\)，这样构成一种方案。这里就把\(x>=y+z\)的情况给算完了。

    接下来令\(f(x)=C_{x+1}^{3}\)。

    考虑\(y>=x+z\)，如果用\begin{aligned}1<=x<=b \\ 1<=y<=b \\ 1<=z<=b \end{aligned}，即\(f(b)\)来计算，则会多算\(a+1<=x<=b\)的部分。不等式两边同时减去\(a\)，即\(y-a>=x-a+z\)，那么多算的部分为\begin{aligned}1<=x<=b-a \\ 1<=y<=b-a\\ 1<=z<=b-a \end{aligned}，即\(f(b-a)\)，该情况的方案数为\(f(b)-f(b-a)\)。

    同理，\(z>=x+y\)的方案数也可用上述方法计算。如果\(c<=a+b\)的话，方案数即\(f(c)-f(c-a)-f(c-b)\)，如果\(c>a+b)\)还要再加上一个\(f(c-a-b)\)。

    所以答案即为\[abc-f(a)-f(b)-f(c)-f(b-a)-f(c-a)-f(c-b)+f(c-a-b)[c>a+b]\]

#include <bits/stdc++.h>
using namespace std;
const int mo=1e9+7;

class TriangleTriples {
public:
	long long pow(long long a,long long b,long long mod_num=mo)
	{
		long long x=a,res=1;
		while (b)
		{
			if (b&1) (res*=x)%=mod_num;
			(x*=x)%=mod_num;
			b>>=1;
		}
		return res;
	}

	long long inv(long long a,long long mod_num=mo)
	{
		return pow(a,mod_num-2);
	}

	int f(int x)
	{
		return (long long)x*(x-1)%mo*(x+1)%mo*inv(6)%mo;
	}

	int count(int A, int B, int C) {
		if (A>B) swap(A,B);
		if (A>C) swap(A,C);
		if (B>C) swap(B,C);
		int res=(long long)A*B%mo*C%mo;
		res=(res-f(A)+mo)%mo;
		res=(res-f(B)+mo)%mo;
		res=(res-f(C)+mo)%mo;
		res=(res+f(B-A))%mo;
		res=(res+f(C-A))%mo;
		res=(res+f(C-B))%mo;
		if (C>A+B) res=(res-f(C-A-B)+mo)%mo;
		return res;
	}
};