CF933D A Creative Cutout 题解

$\text{SYT}$ 学长在模拟赛中出了这道题，并把数据范围加到了 $n\leq 10^{14}$

与学长的式子相似，仍记 $a=x^2+y^2$ ，点 $(x,y)$ 最早被半径为 $\sqrt a$ 的第 $a$ 个圆包含

枚举每个点被包含圆的编号 $\times$ 在 $n$ 个圆中的出现次数，即能推出上面的式子

$$\frac{1}{2}(1+n)(n+a)(n-a+1)-\frac{1}{6}n(n+1)(2n+1)+\frac{1}{6}a(a-1)(2a-1)$$

但由于插值法常数过大，考虑继续将式子化简

将 $a=x^2+y^2$ 代入并以 $y$ 为主元，能得到：

$$\begin{aligned} 原式&=\frac{1+n}{2}(x^2+y^2+n)(n-x^2-y^2+1) \\ &\qquad+\frac{1}{6}n(n+1)(2n+1) \\ &\qquad+(\frac{1}{6}x^4+\frac{1}{6}x^2y^2+\frac{1}{6}x^2y^2+\frac{1}{6}y^4-\frac{1}{6}x^2-\frac{1}{6}y^2)\times(2x^2-2y^2-1) \\ &=\frac{1}{3} y^6 \\ &\qquad+(x^2-1-\frac{1}{2}n) y^4 \\ &\qquad+\left(\frac{1}{2}(1+n)(-2x^2+1)+x^4-x^2+\frac{1}{6} \right) y^2 \\ &\qquad+\left(\frac{1}{2}(1+n)(n+x^2)(n-xx^2+1)-\frac{1}{6}(n)(n+1)(n+2)+\frac{1}{6}x^2(x^2-1)(2x^2-1) \right) \\ \end{aligned}$$

该式的结果是点 $(x,y)$ 对答案的贡献，但还可以更加简化：在 $O(\sqrt n)$ 的时间内枚举正半轴上的每个 $x$ ，有 $max_y=\sqrt{n-x^2}$

对于每个 $x$ ，预处理所有的 $y$ 的六次方，四次方，二次方之和，$O(1)$ 求满足 $x^2+y^2\leq n$ 的所有 $y$ ，即，所有满足条件的 $(x,*)$ 点对答案的贡献和

以 $x=1$ 为例，红线部分就是所求的和

为了运算方便，实际上代码中求的是：

$$\begin{aligned} &2\times \frac{1}{3} y^6 \\ &+2\times (x^2-1-\frac{1}{2}n) y^4 \\ &+2\times \left(\frac{1}{2}(1+n)(-2x^2+1)+x^4-x^2+\frac{1}{6} \right) y^2 \\ &+(2\times max_y+1)\times \left(\frac{1}{2}(1+n)(n+x^2)(n-xx^2+1)-\frac{1}{6}(n)(n+1)(n+2)+\frac{1}{6}x^2(x^2-1)(2x^2-1) \right) \\ \end{aligned}$$

也就是

$y$ 的部分 $\times 2$ 是为了加上负半轴的贡献，常数项 $\times (2\times max_y+1)$ 中，$+1$ 是绿色点的部分，即在 $x$ 轴上时的情况

最终统计答案时，再用：

ans+=(!x) ? added : 2*added;

来处理 $x$ 的正负半轴情况以计算整个圆的情况

代码复杂度为 $O(\sqrt{n})$ ，其瓶颈在于取模(确信)，若取模过于频繁就会从 $900ms$ 掉到 $4s$

#include <bits/stdc++.h>
#define rei register int
#define ll long long
using namespace std;

const int mod=1e9+7;
const int inv2=500000004,inv3=333333336,inv6=166666668;
ll n,mod_n,ans;

int main(){
    scanf("%lld",&n);
    mod_n=n%mod;
    for(ll x=(ll) sqrt(n+0.1),i=1,sum2=0,sum4=0,sum6=0;~x;--x) {
        ll t=sqrt(n-x*x),x2=x*x%mod;
        for(;i<=t;++i){
            ll pow_2=i*i%mod;
            ll pow_4=pow_2*pow_2%mod;
            sum2=(sum2+pow_2)%mod;
            sum4=(sum4+pow_4)%mod;
            sum6=(sum6+pow_2*pow_4)%mod;
        }
        ll added=((ll)2*inv3*sum6%mod
                    +(2*x2-2-mod_n+2*mod)%mod *sum4%mod
                    +( (1+mod_n)*((mod-2)*x%mod*x%mod+1)%mod + 2*x2*x2%mod-2*x2+inv3+2*mod )%mod *sum2%mod
                    +   (inv2*(1+mod_n)%mod*(mod_n+x2)%mod*(mod_n-x2+mod+1)%mod
                        -inv6*mod_n%mod*(mod_n+1)%mod*(2*mod_n+1)%mod
                        +inv6*(x2-1)%mod*x2%mod*(2*x2-1)%mod
                        +mod
                        )%mod*(2*t+1)%mod
                )%mod;
        ans+=(!x) ? added : 2*added;
    }
    printf("%lld\n",ans%mod);
    getchar(),getchar();
    return 0;
}