题解：P9827 [ICPC2020 Shanghai R] Sky Garden

原题链接

• 洛谷 P9827 [ICPC2020 Shanghai R] Sky Garden

解题思路

@Nuyoah_awa 的 题解 提供了 $O(n)$ 的做法。

观察他的代码，发现其中的 DP 都是线性的。

经过数学软件的整理优化，可以 $O(1)$ 实现。设：

$$t=\left\lfloor\frac{2m}{\pi}\right\rfloor$$

则有：

$$p=\frac{t(t+1)\times n(n+1)(2n+1)}{6}$$ $$q=\frac{mn(n+1)(6mn-4tn-2t-2n-1+3\times[m\ne 1])}{3}$$ $$S=p\pi+q$$

至此，已成艺术。

$$O(n^3)\to O(1)$$

接下来，我们来看看 @sintle 的 人工队 表现。

参考代码

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

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