文章目录

题目链接：

http://codeforces.com/problemset/problem/572/C
题意：给一个三角形的三条边（a,b,c），让给这个三角形的边加长度，总共加的长度不超过 L ，问有几种合法的三角形

首先就是枚举总共加了 len 这么长的长度，然后 len 怎么分给三边是个组合数学的问题，其实就是个阔以为0的隔板法
比如这里的 len 个数分成3 坨，如果每一坨都不能是0，那就是 len-1 个空 插入两个隔板，就是 C l e n − 1 2 C_{len-1}^2 Clen−12​ 个，但是阔以为0的话，就先把每一坨加1，总共就有 len+3 个数，然后 len+2 个空，所以就是 C l e n + 2 2 C_{len+2}^2 Clen+22​

思路就是这位童鞋滴：https://www.cnblogs.com/jerryRey/p/4752244.html

找到不满足条件的最大值，后要分，其实还是这个带0的隔板法的思路，我没有反应过来T_T
还有一个有点坑的就是
因为-1/2=0,而0会贡献答案
所以是用的移位来代替，哇简直牛皮了，要是叫我只用想的话，我想好久都发现不了这个bugT_T

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
LL calc(LL a,LL b,LL c,LL add)//a作为最长边,假如总共加add的长度,会有多少不满足条件 
{
	//计算出b+c这边最多能加多少 
	LL x=(a-b-c+add)>>1;//这里不要用除号,因为-1/2=0,而0会贡献答案 
	
	/*这x个阔以全部给b+c这边，也阔以只给x-1,或者x-2...或者0个 我一开始还想的是枚举,结果。。。。直接一个组合数就行了 相当于把这x个分成三份,每份阔以为0个,就跟那个思路一样滴*/
	
	if(x<0)return 0;//肯定能分,没有不符合的 
	if(x>add)x=add;//一共只有add个，所以最多分add个 
	return (x+2)*(x+1)/2;//C(x+2,2) 
}
int main()
{
	LL a,b,c,L;
	while(cin>>a>>b>>c>>L)
	{
		LL sum=0;
		for(LL i=0;i<=L;i++)//枚举总共i这么长分给3条边 
		{
			sum+=(i+2)*(i+1)/2;//C(i+2,2),表示总的方案数 
			sum-=calc(a,b,c,i);//减去计算以a为最长边不合法的方案数 
			sum-=calc(b,a,c,i);
			sum-=calc(c,a,b,i);
		}
		cout<<sum<<endl;
	}
}