CF571A题解
262620zzj
·
·
题解
前置知识
\Delta f(x)=f(x+1)-f(x)
\sum_{x=a}^{b}\Delta f(x)=f(b+1)-f(a)
x^{\underline{n}}=x(x-1)(x-2)\dots(x-n+1)
x^{\underline{n}}=\Delta (\frac{x^{\underline{n+1}}}{n+1})
基础思路
容斥原理，先计算出所有情况，再减去不合法的情况。（也就是不符合两边之和大于第三边这个三角形规律）。
三边分别当作最长边，枚举分配给最长边的长度，可以轻松算出不合法方案数，时间复杂度 O(L)。
代码其他题解写的非常清楚。
优化
可以发现这个算法瓶颈就在于有一个循环枚举了一遍长度。可以发现循环内的运算是很具有规律的，所以尝试一下简化。
记 A=a+b-c
for(int x=max(0,A);x<=L;x++){
int y=min(L-x,x-A);
ans-=(y+1)*(y+2)/2;
}
这段代码中把 x 看成自变量，-x+L,x-A 看成一次函数，y 取值的变化过程画在一个坐标系内，可以有所发现。
红色是 x-A，蓝色是 -x+L。
- $L<x\Rightarrow A>L$，循环一次也不会执行，所以无事发生，答案不会有任何变化。
- $\frac{L}{2}\le x<L\Rightarrow 0\le A<L$，图象是这样的。
根据 $x=\frac{L+A}{2}$ 记 $lim=\frac{L-A}{2}$ 为转折点的纵坐标。可以分两段求和，先看上升段。
$$\sum_{y=0}^{lim}\frac{(y+1)(y+2)}{2}$$
$$=\sum_{y=2}^{lim+2}\frac{y(y-1)}{2}$$
$$=\sum_{y=2}^{lim+2}\frac{y^{\underline{2}}}{2}$$
$$=\sum_{y=2}^{lim+2}\Delta(\frac{x^{\underline{3}}}{6})$$
$$=\frac{(lim+3)^{\underline{3}}}{6}-\frac{2^{\underline{3}}}{6}$$
$$=\frac{(lim+3)^{\underline{3}}}{6}$$
下降段反着看其实就是上升段，所以最终不合法方案数翻倍，再减重复计算的点 $lim$，不合法数量是
$$\frac{(lim+3)^{\underline{3}}}{3}-\frac{(lim+1)(lim+2)}{2}$$
- $0\le x<\frac{L}{2}\Rightarrow -L\le A<0$，图象是这样的。
所有的减去黄色点就是绿色点。所有点刚才已经求出了，黄色点的求法类似。
$$\sum_{y=0}^{-1-A}\frac{(y+1)(y+2)}{2}$$
$$\cdots$$
$$=\frac{(2-A)^{\underline{3}}}{6}$$
那么不合法方案数只需在上一条基础上减去它即可。
- $x<0\Rightarrow -A<L$ 最长边与其余两边的和之差大于 $L$，无论怎么分配也不可能构成一个三角形。所以直接 $ans\gets0$。
---
接下来就是 $x$ 不是整数的情况了。显然只对 $0\le x<L$ 的两种情况有影响。
可以发现其他不变，只是 $lim$ 变成了它的上一个点。并且，也不用担心 $lim$ 被重复计算了。所以 $x$ 不是整数的情况下，只需要对刚才第二、三种情况的式子稍加修改即可。
去掉
$$\frac{(lim+1)(lim+2)}{2}$$
再改 $lim$。
$$\frac{(lim+3)^{\underline{3}}}{3}\to \frac{(lim+2)^{\underline{3}}}{3}$$
理论时间复杂度 $O(1)$，可以通过大约 $L\le 10^{12}$ 的数据。因为太大会爆 `__int128`。
# 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll _3(ll x){return x*(x-1)*(x-2);}//3次下降幂
ll a,b,c,L,ans;
void figure(ll A,ll L){
ll lim=(L-A+1)/2;//上取整
double x=1.0*(L+A)/2;
if(x<0){ans=0;return;}
if(x>L)return;
if((L+A)%2)ans-=_3(lim+2)/3;//判断x是否是整数
else{
ans-=_3(lim+3)/3;
ans+=(lim+1)*(lim+2)/2;
}
if(x<1.0*L/2)ans+=_3(2-A)/6;
}
int main(){
scanf("%lld%lld%lld%lld",&a,&b,&c,&L);
ans=_3(L+3)/6;
figure(a+b-c,L);
figure(b+c-a,L);
figure(c+a-b,L);
printf("%lld\n",ans);
return 0;
}
```