题解 [SEERC2018]Broken Watch
xiaolilsq
·
·
题解
题目链接
如果 \LaTeX 炸了，请在博客页面内查看。
题目分析
不妨先求出所有表针长度相等时的答案。
分类讨论，当 n 为偶数时：
在该图中，不妨认为 \rm B,I,C,H 为上方的点， \rm D,F,E,G 为下方的点，那么一个合法的三角形必然有两个点在上方另一个点在下方或者两个点在下方另一个点在上方，由于上方和下方是对称的，所以我们只用求出两个点在上方一个点在下方的方案数再乘以二就行了。
枚举上方选哪两个点，当上方的两个点选 \rm B,H 时，下方可以选 \rm D,F,E,G ；上方选 \rm B,C 时，下方可以选 \rm D,F,E ；上方选 \rm B,I 时；下方可以选 \rm D,F ，…… 设 m=\dfrac{n}{2} ，不难发现，乘二后方案数为 2(\sum_{i=1}^{m-1}\sum_{j=i+1}^m(j-i+1)) 。
在该图中，不妨认为 \rm E,D,C,B 为上方的点， \rm F,G,A 为下方的点，同样的，一个合法的三角形必然有两个点在上方另一个点在下方或者两个点在下方另一个点在上方，但是需要注意的是，如果一个三角形的一个顶点是 \rm E ，那么对称后还是两个点在上方另一个点在下方，所以乘以二后要把这部分减去。
枚举上方选哪两个点，当上方的两个点选 \rm E,B 时，下方可以选 \rm F,G,A ；上方选 \rm E,C 时，下方可以选 \rm G,A ；上方选 \rm E,D 时，下方可以选 \rm A ；…… 设 m=\dfrac{n+1}{2} ，不难发现，答案为 2(\sum_{i=1}^{m-1}\sum_{j=i+1}^m(j-i))-\sum_{j=1+1}^m(j-1) 。
接下来就是愉快的推式子时间（注意一个公式： \sum_{i=1}^ni^2=\dfrac{n(n+1)(2n+1)}{6} ，如果忘了可以考场上用拉格朗日插值或者待定系数法求出qwq）：
$$
2(\sum_{i=1}^{m-1}\sum_{j=i+1}^m(j-i+1))
$$
$$
=2(\sum_{i=1}^{m-1}\sum_{j=2}^{m-i+1}j)
$$
$$
=2(\sum_{i=1}^{m-1}\dfrac{(m-i+3)(m-i)}{2})
$$
$$
=2(\sum_{i=1}^{m-1}\dfrac{(i+3)i}{2})
$$
$$
=2(\sum_{i=1}^{m-1}(\dfrac{1}{2}i^2+\dfrac{3}{2}i))
$$
$$
=2(\dfrac{1}{2}\dfrac{(m-1)m(2m-1)}{6}+\dfrac{3}{2}\dfrac{m(m-1)}{2})
$$
$$
=2(\dfrac{1}{6}m^3-\dfrac{1}{4}m^2+\dfrac{3}{4}m^2+\dfrac{1}{12}m-\dfrac{3}{4}m)
$$
$$
=2(\dfrac{1}{6}m^3+\dfrac{1}{2}m^2-\dfrac{2}{3}m)
$$
$$
=2(\dfrac{m^3+3m^2-4m}{6})
$$
$$
=\frac{(m-1)m(m+4)}{3}
$$
$n$ 为奇数，设 $m=(n+1)/2$ 。
$$
2(\sum_{i=1}^{m-1}\sum_{j=i+1}^m(j-i))-\sum_{j=1+1}^m(j-1)
$$
$$
=2(\sum_{i=1}^{m-1}\sum_{j=1}^{m-i}j)-\sum_{j=1}^{m-1}j
$$
$$
=2(\sum_{i=1}^{m-1}\dfrac{(m-i+1)(m-i)}{2})-\dfrac{(m-1)m}{2}
$$
$$
=2(\sum_{i=1}^{m-1}\dfrac{(i+1)i}{2})-\dfrac{(m-1)m}{2}
$$
$$
=2(\sum_{i=1}^{m-1}(\dfrac{1}{2}i^2+\dfrac{1}{2}i))-\dfrac{(m-1)m}{2}
$$
$$
=2(\sum_{i=1}^{m-1}(\dfrac{1}{2}i^2+\dfrac{3}{2}i)-\sum_{i=1}^{m-1}i)-\dfrac{(m-1)m}{2}
$$
$$
=2(\dfrac{1}{6}m^3+\dfrac{1}{2}m^2-\dfrac{2}{3}m-\dfrac{(m-1)m}{2})-\dfrac{(m-1)m}{2}
$$
$$
=\dfrac{1}{3}m^3-\dfrac{1}{2}m^2+\dfrac{1}{6}m
$$
$$
=\dfrac{2m^3-3m^2+m}{6}
$$
$$
=\dfrac{(m-1)m(2m-1)}{6}
$$
由于直接乘会溢出，逆元又不太好求，所以要先把除数分开除。
当表针长度并不都相等时，多重排列即可，当两根针长度相等时，答案要乘以 $\dfrac{3!}{2!1!}=3$ ，当所有针长度都不相等是，答案要乘以 $\dfrac{3!}{1!1!1!}=6$ 。
最后便得到了 $O(1)$ 求答案的方法。
## 参考代码
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ull unsigned long long
using namespace std;
#define ch() getchar()
#define pc(x) putchar(x)
template<typename T>inline void read(T&x){
int f;char c;
for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c<='9'&&c>='0';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>inline void write(T x){
static char q[64];int cnt=0;
if(!x)pc('0');if(x<0)pc('-'),x=-x;
while(x)q[cnt++]=x%10+'0',x/=10;
while(cnt--)pc(q[cnt]);
}
int main(){
ull A,B,C,N;
read(A),read(B),read(C),read(N);
if(N==2)puts("0");
else{
ull cnt=(A==B)+(B==C)+(A==C);
cnt=(cnt==3?1:cnt==1?3:6);
if(N&1){
N=(N+1)>>1;
A=N-1,B=N,C=N*2-1;
if(A&1)B>>=1;
else A>>=1;
}
else{
N=N>>1;
A=N-1,B=N,C=N+4;
}
if(A%3==0)A/=3;
else if(B%3==0)B/=3;
else C/=3;
write(A*B*C*cnt),pc('\n');
}
return 0;
}
```