CodeForces571A. Lengthening Sticks(组合数学-容斥）
CodeForces571A. Lengthening Sticks(组合数学-容斥）
题目大意：
a,b,c三根木棍可以增加三个不同的数字，aa,bb,cc,且aa+bb+cc<=L，问能构成三角形的木棒有多少种方案
题目思路：
如果我们直接考虑把L分配给aa,bb,cc好像不好下手
所以逆向考虑
合法的情况 = 所有情况 - 不合法的情况
step1:
首先计算所有的情况
假设L当时为l
我们把长度为l分配去的总的方案
这个问题我们等效为：有三个篮子，每个篮子放至少一个个物品，总共l个物品，问有多少种方案
我们用插板法解决这个问题
因为每个篮子放至少一个，而我们的目标是可以放0个，怎么办呢？
我们可以增加几个物品使初始每个篮子中就有一个，这里假设有m个篮子，n个物品
那我们的物品个数变为n+m,这时候会产生n+m-1个隔板
然后我们要选出m部分来，也就是放m-1个隔板
此时的方案为C（n+m-1,m-1)
回到这个题目
此时长度为l时，方案为C(l+3-1,3-1)
然后我们枚举一遍l，求和算出总的方案
所以得到为l的时候方案为C（l+2,2)
step2:
求不合法的方案==
假设a+aa,b+bb,c+cc(aa,bb,cc分别为分配的增加的长度)
假设a+aa是那条最长的边
此时不合法需要满足如下条件：
b+bb+c+cc<=a+aa
bb+cc<=l-aa
得
bb+cc<=min(l-aa,a-b-c+aa)
令T=bb+cc
这个时候再进行一下问题转化
有T个物品，分配到三个篮子里（可以分配0个）
三个篮子分别是bb，cc和多余的部分
回到上面的插板法一样的解法C（t+3-1.3-1)
然后用总的减去不合法就ok了
CODE：
View Code