题解：P9827 [ICPC2020 Shanghai R] Sky Garden

题目链接

• 洛谷 P9827 [ICPC2020 Shanghai R] Sky Garden

解题思路

本题的 $O(n)$ 做法已有，不多说。

@lailai0916 在他的题解中给出了使用数学工具进行归纳的 $O(1)$ 做法，十分优雅，下面来看看人工队的表现。

设点 $a$ 在第 $a_i$ 个圆上，点 $b$ 在第 $b_i$ 个圆上，二者之间相隔 $x$ 条直线（包括点 $b$ 所在的直线，不包括点 $a$ 所在的直线），$p$ 为 $\left\lceil\dfrac{2m}{\pi}\right\rceil$。

因此 $dis({a,b})=\displaystyle\min_{i=1}^{n}|a_i-i|+|b_i-i|+\dfrac{\pi ix}{m}$

所以此时题目要求的就是：

$$\displaystyle\sum_{a_i=0}^{n}\sum_{b_i=0}^{n}\sum_{x=0}^{2m}\min_{i=0}^{n}(|a_i-i|+|b_i-i|+\dfrac{\pi ix}{m})\times 2m$$

我们注意到，$i$ 必定小于等于 $\min(a_i,b_i)$，并且两点之间的最短路一定是经过圆心或者只经过一条线段再经过一条圆弧（仅取决于两个点所在直线的角度大小）的，于是我们就得到：

$$\begin{aligned} ans &= 4m\times \sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=1}^{m-1}\begin{cases} a_i+b_i & \dfrac{\pi x}{m}>2 \\ b_i-a_i+\dfrac{\pi a_ix}{m} & \dfrac{\pi x}{m}<2 \end{cases} +2m\times\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}2b_i +\sum_{b_i=1}^{n}b_i\times2m +2m\times \sum_{a_i=1}^{n}\sum_{x=1}^{m-1}\begin{cases} 2a_i & \dfrac{\pi x}{m}>2 \\ \dfrac{\pi a_ix}{m} & \dfrac{\pi x}{m}<2 \end{cases} +2m\times\sum_{a_i=1}^{n}a_i \\ &= 2m\times( 2\times\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=1}^{m-1}\begin{cases} a_i+b_i & \dfrac{\pi x}{m}>2 \\ b_i-a_i+\dfrac{\pi a_ix}{m} & \dfrac{\pi x}{m}<2 \end{cases} +\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}2b_i +\sum_{b_i=1}^{n}b_i +\sum_{a_i=1}^{n}\sum_{x=1}^{m-1}\begin{cases} 2a_i & \dfrac{\pi x}{m}>2 \\ \dfrac{\pi a_ix}{m} & \dfrac{\pi x}{m}<2 \end{cases} +\sum_{a_i=1}^{n}a_i) \\ &= 2m\times( 2\times( \sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=1}^{p-1}(b_i-a_i+\dfrac{\pi a_ix}{m}) +\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=p}^{m-1}(a_i+b_i)) +\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}2b_i +\sum_{b_i=1}^{n}b_i +\sum_{a_i=1}^{n}\sum_{x=1}^{p-1}\dfrac{\pi a_ix}{m} +\sum_{a_i=1}^{n}\sum_{x=p}^{m-1}2a_i +\sum_{a_i=1}^{n}a_i) \\ \end{aligned}$$

• 然后开始化简：

$$\begin{aligned} \sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=1}^{p-1}(b_i-a_i+\dfrac{\pi a_ix}{m}) &= \sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=1}^{p-1}\dfrac{\pi a_ix} {m}+\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=1}^{p-1}(b_i-a_i)\\ &= \dfrac{\pi}{m}\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=1}^{p-1}a_ix +\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=1}^{p-1}(b_i-a_i)\\ &= \dfrac{\pi}{m}\sum_{a_i=1}^{n}a_i\sum_{b_i=a_i+1}^{n}\sum_{x=1}^{p-1}x +\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=1}^{p-1}(b_i-a_i)\\ &= \dfrac{\pi}{m}\sum_{a_i=1}^{n}a_i\dfrac{p(n-a_i)(p-1)}{2} +\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=1}^{p-1}(b_i-a_i)\\ \end{aligned}$$

• 分别化简：

$$\begin{aligned} \dfrac{\pi}{m}\sum_{a_i=1}^{n}a_i\dfrac{p(n-a_i)(p-1)}{2} &= \dfrac{\pi}{2m}\sum_{a_i=1}^{n}a_ip(n-a_i)(p-1) \\ &= \dfrac{\pi}{2m}\sum_{a_i=1}^{n}(a_in-a_i^2)(p^2-p) \\ &= \dfrac{\pi(p^2-p)}{2m}\sum_{a_i=1}^{n}a_in-a_i^2 \\ &= \dfrac{\pi(p^2-p)}{2m}(\sum_{a_i=1}^{n}a_in-\sum_{a_i=1}^{n}a_i^2) \\ &= \dfrac{\pi(p^2-p)}{2m}(\dfrac{n^2(n+1)}{2}-\dfrac{n(n+1)(2n+1)}{6}) \\ &= \dfrac{\pi(p^2-p)}{2m}(\dfrac{3n^2(n+1)-n(n+1)(2n+1)}{6}) \\ &= \dfrac{(p^2-p)(3n^2(n+1)-n(n+1)(2n+1))\pi}{12m} \\ &= \dfrac{(p^2-p)(3n^3+3n^2-n(2n^2+3n+1))\pi}{12m} \\ &= \dfrac{(p^2-p)(3n^3+3n^2-2n^3-3n^2-n)\pi}{12m} \\ &= \dfrac{(p^2-p)(n^3-n)\pi}{12m} \\ \end{aligned}$$ $$\begin{aligned} \sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=1}^{p-1}(b_i-a_i) &= (p-1)\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}(b_i-a_i)\\ &= (p-1)(\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}b_i-\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}a_i)\\ &= (p-1)(\sum_{a_i=1}^{n}\dfrac{(n-a_i)(a_i+n+1)}{2}-\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}a_i)\\ &= (p-1)(\dfrac{\sum_{a_i=1}^{n}(n^2+n-a_i^2-a_i)}{2}-\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}a_i)\\ &= (p-1)(\dfrac{\sum_{a_i=1}^{n}n^2+\sum_{a_i=1}^{n}n-\sum_{a_i=1}^{n}a_i^2 -\sum_{a_i=1}^{n}a_i}{2}-\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}a_i)\\ &= (p-1)(\dfrac{n^3+n^2-\dfrac{n(n+1)(2n+1)}{6} -\dfrac{n(n+1)}{2}}{2}-\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}a_i)\\ &= (p-1)(\dfrac{6n^3+6n^2-n(n+1)(2n+1) -3n(n+1)}{12}-\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}a_i)\\ &= (p-1)(\dfrac{6n^3+6n^2-n(n+1)(2n+1)-3n(n+1)}{12} -\sum_{a_i=1}^{n}a_i(n-a_i))\\ &= (p-1)(\dfrac{6n^3+6n^2-n(n+1)(2n+1)-3n(n+1)}{12} -\sum_{a_i=1}^{n}a_in-a_i^2)\\ &= (p-1)(\dfrac{6n^3+6n^2-n(n+1)(2n+1)-3n(n+1)}{12} -\sum_{a_i=1}^{n}a_in+\sum_{a_i=1}^{n}a_i^2)\\ &= (p-1)(\dfrac{6n^3+6n^2-n(n+1)(2n+1)-3n(n+1)}{12} -\dfrac{n^2(n+1)}{2}+\dfrac{n(n+1)(2n+1)}{6})\\ &= (p-1)(\dfrac{6n^3+6n^2-n(n+1)(2n+1)-3n(n+1)}{12} -\dfrac{6n^2(n+1)}{12}+\dfrac{2n(n+1)(2n+1)}{12})\\ &= (p-1)(\dfrac{6n^3+6n^2-n(n+1)(2n+1)-3n(n+1) -6n^2(n+1)+2n(n+1)(2n+1)}{12})\\ &= (p-1)(\dfrac{6n^3+6n^2-3n^2-3n-6n^3-6n^2+n(2n^2+3n+1)}{12})\\ &= (p-1)(\dfrac{6n^3+6n^2-3n^2-3n-6n^3-6n^2+2n^3+3n^2+n}{12})\\ &= (p-1)(\dfrac{n^3-n}{6})\\ \end{aligned}$$

• 合并回原式：

$$\begin{aligned} \sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=1}^{p-1}(b_i-a_i+\dfrac{\pi a_ix}{m}) &= \dfrac{(p^2-p)(n^3-n)\pi}{12m}+(p-1)(\dfrac{n^3-n}{6})\\ &= (p-1)(\dfrac{p(n^3-n)\pi}{12m}+\dfrac{n^3-n}{6})\\ &= (p-1)(\dfrac{p(n^3-n)\pi}{12m}+\dfrac{2m(n^3-n)}{12m})\\ &= (p-1)(\dfrac{p(n^3-n)\pi+2m(n^3-n)}{12m})\\ &= (p-1)(n^3-n)(\dfrac{p\pi+2m}{12m})\\ \end{aligned}$$

• 化简 $\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=p}^{m-1}(a_i+b_i))$：

$$\begin{aligned} \sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=p}^{m-1}(a_i+b_i) &= (m-p)\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}(a_i+b_i)\\ &= (m-p)(\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}a_i+\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}b_i)\\ &= (m-p)(\dfrac{n^2(n+1)}{2}-\dfrac{n(n+1)(2n+1)}{6}+\dfrac{6n^3+6n^2-n(n+1)(2n+1)-3n(n+1)}{12})\\ &= (m-p)(\dfrac{6n^2(n+1)}{12}-\dfrac{2n(n+1)(2n+1)}{12}+\dfrac{6n^3+6n^2-n(n+1)(2n+1)-3n(n+1)}{12})\\ &= (m-p)\dfrac{6n^2(n+1)-2n(n+1)(2n+1)+6n^3+6n^2-n(n+1)(2n+1)-3n(n+1)}{12}\\ &= (m-p)\dfrac{6n^3+6n^2-3n(2n^2+3n+1)+6n^3+6n^2-3n^2-3n}{12}\\ &= (m-p)\dfrac{6n^3+6n^2-3n(2n^2+3n+1)+6n^3+6n^2-3n^2-3n}{12}\\ &= (m-p)\dfrac{6n^3+6n^2-6n^3-9n^2-3n+6n^3+6n^2-3n^2-3n}{12}\\ &= (m-p)\dfrac{n^3-n}{2}\\ \end{aligned}$$

化简 $\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}2b_i$：

$$\begin{aligned} \sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}2b_i &= 2\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}b_i\\ &= \dfrac{6n^3+6n^2-n(n+1)(2n+1)-3n(n+1)}{6}\\ &= \dfrac{6n^3+6n^2-2n^3-3n^2-n-3n^2-3n}{6}\\ &= \dfrac{4n^3-4n}{6}\\ &= \dfrac{2n^3-2n}{3}\\ \end{aligned}$$

化简 $\sum_{b_i=1}^{n}b_i$：

$$\begin{aligned} \sum_{b_i=1}^{n}b_i &= \dfrac{n(n+1)}{2}\\ \end{aligned}$$

• 化简 $\sum_{a_i=1}^{n}\sum_{x=1}^{p-1}\dfrac{\pi a_ix}{m}$：

  $$\begin{aligned} \sum_{a_i=1}^{n}\sum_{x=1}^{p-1}\dfrac{\pi a_ix}{m} &= \dfrac{\pi}{m}\sum_{a_i=1}^{n}a_i\sum_{x=1}^{p-1}x\\ &= \dfrac{\pi}{m}\sum_{a_i=1}^{n}a_i\sum_{x=1}^{p-1}x\\ &= \dfrac{\pi}{m}\sum_{a_i=1}^{n}a_i\dfrac{p(p-1)}{2}\\ &= \dfrac{p(p-1)\pi}{2m}\sum_{a_i=1}^{n}a_i\\ &= \dfrac{n(n+1)p(p-1)\pi}{4m}\\ \end{aligned}$$

• 化简 $\sum_{a_i=1}^{n}\sum_{x=p}^{m-1}2a_i$：

  $$\begin{aligned} \sum_{a_i=1}^{n}\sum_{x=p}^{m-1}2a_i &= 2\sum_{a_i=1}^{n}\sum_{x=p}^{m-1}a_i\\ &= 2(m-p)\sum_{a_i=1}^{n}a_i\\ &= (m-p)n(n+1)\\ \end{aligned}$$

• 化简 $\sum_{a_i=1}^{n}a_i)$：

  $$\begin{aligned} \sum_{a_i=1}^{n}a_i &= \dfrac{n(n+1)}{2}\\ \end{aligned}$$

• 全部代入回原式：

  $$\begin{aligned} ans &= 2m\times( 2\times( \sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=1}^{p-1}(b_i-a_i+\dfrac{\pi a_ix}{m}) +\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}\sum_{x=p}^{m-1}(a_i+b_i)) +\sum_{a_i=1}^{n}\sum_{b_i=a_i+1}^{n}2b_i +\sum_{b_i=1}^{n}b_i +\sum_{a_i=1}^{n}\sum_{x=1}^{p-1}\dfrac{\pi a_ix}{m} +\sum_{a_i=1}^{n}\sum_{x=p}^{m-1}2a_i +\sum_{a_i=1}^{n}a_i) \\ &= 2m\times( 2\times((p-1)(n^3-n)(\dfrac{p\pi+2m}{12m}) +(m-p)\dfrac{n^3-n}{2}) +\dfrac{2n^3-2n}{3} +\dfrac{n(n+1)}{2} +\dfrac{n(n+1)p(p-1)\pi}{4m} +(m-p)n(n+1) +\dfrac{n(n+1)}{2})\\ &= 2m\times( (p-1)(n^3-n)(\dfrac{p\pi+2m}{6m}) +(m-p)(n^3-n) +\dfrac{2n^3-2n}{3} +\dfrac{n(n+1)}{2} +\dfrac{n(n+1)p(p-1)\pi}{4m} +(m-p)n(n+1) +\dfrac{n(n+1)}{2})\\ &= \dfrac{1}{6}( 2(p-1)(n^3-n)(p\pi+2m) +12m(m-p)(n^3-n) +4m(2n^3-2n) +6mn(n+1) +3n(n+1)p(p-1)\pi +12m(m-p)n(n+1) +6mn(n+1))\\ &= \dfrac{1}{6}( 2(p-1)(pn^3\pi+2mn^3-pn\pi-2mn) +12m(mn^3-mn-pn^3+pn) +8mn^3-8mn +6mn^2+6mn +3np(np-n+p-1)\pi +12mn(mn+m-pn-p) +6mn^2+6mn)\\ &= \dfrac{1}{6}( 2(p^2n^3\pi+2pmn^3-p^2n\pi-2pmn-pn^3\pi-2mn^3+pn\pi+2mn) +12m^2n^3-12m^2n-12pmn^3+12pmn +8mn^3-8mn +6mn^2+6mn +(3n^2p^2-3n^2p+3np^2-3np)\pi +12m^2n^2+12m^2n-12pmn^2-12pmn +6mn^2+6mn)\\ &= \dfrac{1}{6}( 2p^2n^3\pi +4pmn^3 -2p^2n\pi -4pmn -2pn^3\pi -4mn^3 +2pn\pi +4mn +12m^2n^3 -12m^2n -12pmn^3 +12pmn +8mn^3-8mn +6mn^2+6mn +(3n^2p^2-3n^2p+3np^2-3np)\pi +12m^2n^2 +12m^2n -12pmn^2 -12pmn +6mn^2 +6mn)\\ &= \dfrac{1}{6}( 4pmn^3 -4pmn -4mn^3 +4mn +12m^2n^3 -12m^2n -12pmn^3 +12pmn +8mn^3-8mn +6mn^2+6mn +12m^2n^2 +12m^2n -12pmn^2 -12pmn +6mn^2 +6mn +(3n^2p^2-3n^2p+3np^2-3np)\pi +2p^2n^3\pi -2p^2n\pi -2pn^3\pi +2pn\pi)\\ &= \dfrac{1}{6}(4mn^3-8pmn^3-4pmn+8mn+12m^2n^3+12mn^2+12m^2n^2-12pmn^2 +(3n^2p^2-3n^2p+np^2-np+2p^2n^3-2pn^3)\pi)\\ \end{aligned}$$

• 最后得出结论：

$$q=\dfrac{1}{6}(4mn^3-8pmn^3-4pmn+8mn+12m^2n^3+12mn^2+12m^2n^2-12pmn^2)$$ $$p=\dfrac{1}{6}(3n^2p^2-3n^2p+np^2-np+2p^2n^3-2pn^3)$$

参考代码

#include <bits/stdc++.h>
using namespace std;

long long n , m;
inline long long tw(long long x) return x * x;
inline long long th(long long x) return x * x * x;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    long long p = 2 * m / acos(-1) + 1 , p , q;
    q = ((4 * m * th(n) - 8 * p * m * th(n) - 4 * p * m * n + 8 * m * n + 12 * tw(m) * th(n) + 12 * m * tw(n) + 12 * tw(m) * tw(n) - 12 * p * m * tw(n)) / 6 - ((m * n) * (n + 1)) * (m == 1));
    p = ((3 * tw(n) * tw(p) - 3 * tw(n) * p + n * tw(p) - n * p + 2 * tw(p) * th(n) - 2 * p * th(n)) / 6);
    cout << fixed << setprecision(12) << p * acos(-1) + q << '\n';
    return 0;
}