Codeforces Round #317 A. Lengthening Sticks（组合+容斥）
最后更新于：2022-04-01 15:52:42
之前也遇到过好几次这种类型的题目了， 但是这次还是没有在比赛中做出来。
因为输入只有4个数， 可变化的状态很少， 但是数据范围又很大， 所以不可能是DP之类的， 一定是一道数学题。 这种特点的题目我们很容易想到排列组合， 然而排列组合往往又会带来重复计数的问题， 所以往往这类题目又需要夹杂容斥定理， 可以说是约定俗称的题目类型。
那么不难想到， 用总的组合情况减去不成立的情况（不成立的情况往往好求）。 对于总的情况， 我们不妨从0枚举到l，枚举三根木棒增加长度的总和i。 那么我们可以将其想象成一根长i的木棒，要将其分成3份。 就行在木棒上切两刀。 但是由于增加的长度可以为0， 所以两刀可以切在一点。 例如： i = 5 那么如果两刀都切在3上， 三根木棒分别增加3、0、2； 所以假设第一刀切在0点， 那么第二刀有l+1种可能：0、1、2.....l 。假设第一刀在1，那么第二刀有l种可能， 以此类推。。。 所以总的方案数为（l+1)+l+（l-1)+（l-2）+......+1。一共（l+2）*（l+1)/2种可能。
接下来排除不可能的情况。 我们不妨假设a+i最长(i=0,1,2....l)。 那么该边最长，我们可以算出来该边和其他两边和的差值，那么这一段长度是可以像一开始一样求组合数的，因为无论怎么组合，a+i仍然是最长的。
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
ll a,b,c,l;
ll solve(ll a, ll b, ll c) {
ll cur = 0;
for(ll i=max(b+c-a,0ll);i<=l;i++) {
ll res = l - i;
ll v = min(res, a+i-b-c);
cur += (v+2)*(v+1)/2;
}
return cur;
}
int main() {
scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&l);
ll ans = 0;
for(ll i=0;i<=l;i++) {
ans += (i+2)*(i+1)/2;
}
ans -= solve(a,b,c);
ans -= solve(b,a,c);
ans -= solve(c,a,b);
printf("%I64d\n",ans);
return 0;
}
~~~