HHKB2020 D 题解

发布时间 2023-08-07 11:30:41作者: liangbowen

problem & blog

特判一下 \(a+b>n\) 时为 \(0\)

正难则反,计算重叠的方案数。重叠即 \(x,y\) 轴均有交集,于是转化为两条线段相交的方案数(两条线段认为是不同的)。

正难则反,计算不相交的方案数。第一条线段有 \((n-b+1)-a+1=n-a-b+2\) 种可能,第二条有 \((n-a-b+1)\) 种可能,故方案数为 \((n-a-b+2)(n-a-b+1)\)

故相交的方案数为 \(t=\color{red}(n-a+1)(n-b+1)\color{black}-\color{blue}(n-a-b+2)(n-a-b+1)\),答案即 \((n-a+1)^2(n-b+1)^2-t^2\)

代码,单组 case 时间复杂度 \(O(1)\)