[ TCO2016 Round 2B DIV1 Easy ] TriangleTriples

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

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

考虑\(x \geq y+z\),由于\(y+z \leq a\),那么显然有\begin{aligned}1 \leq x \leq a \\ 1 \leq y \leq a \\ 1 \leq z \leq 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 \leq x_0<x_1<x_2 \leq a\),取\(x=x_2,y=x_2-x_1,z=x_1-x_0\),这样构成一种方案。这里就把\(x \geq y+z\)的情况给算完了。

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

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

同理,\(z \geq x+y\)的方案数也可用上述方法计算。如果\(c \leq 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;
	}
};

Leave a Reply

Your email address will not be published.