codeforces 933D A Creative Cutout

题目链接

正解:组合数学。

充满套路与细节的一道题。。

首先我们显然要考虑每个点的贡献(我就不信你能把$f$给筛出来

那么对于一个点$(x,y)$,我们设$L=x^{2}+y^{2}$,那么它的贡献就是$ans=\sum_{k=L}^{n}\sum_{j=L}^{k}j$

然后我们把后面那个$\sum$化成组合数的形式,即$ans=\sum_{k=L}^{n}\binom{k+1}{2}-\binom{L}{2}$(讲真连这一步我都没想到

注意一个等式$\sum_{i=L}^{R}\binom{i}{x}=\binom{R+1}{x+1}-\binom{L}{x+1}$,这个直接用杨辉三角的递推式即可证明。

把这个等式带进去,可得$ans=\binom{n+2}{3}-\binom{L+1}{3}-(n-L+1)\binom{L}{2}$

然后暴力拆开,可得$ans=\frac{1}{6}(n(n+1)(n+2)-L(L-1)(L+1)-3(n-L+1)(L-1)L)$

然后把$L=x^{2}+y^{2}$代入,可得$6ans=n(n+1)(n+2)+2x^{6}+6x^{4}y^{2}+6x^{2}y^{4}+2y^{6}-3(n+2)(x^{4}+2x^{2}y^{2}+y^{4})+(3n+4)(x^{2}+y^{2})$

枚举$x$,那么$y$的取值范围是一个区间。所以我们预处理出二次,三次和六次的幂和,直接算即可,复杂度$O(\sqrt{n})$。

 #include <bits/stdc++.h>
#define il inline
#define RG register
#define ll long long
#define N (1000005)
#define rhl (1000000007) using namespace std; ll sum2[N],sum4[N],sum6[N],n,m,lim,ans; il ll qpow(RG ll a,RG ll b){
RG ll ans=;
while (b){
if (b&) ans=ans*a%rhl;
if (b>>=) a=a*a%rhl;
}
return ans;
} int main(){
#ifndef ONLINE_JUDGE
freopen("cutout.in","r",stdin);
freopen("cutout.out","w",stdout);
#endif
cin>>n,m=n%rhl,lim=sqrt(n);
for (RG ll i=;i<=lim;++i){
sum2[i]=(sum2[i-]+i*i)%rhl;
sum4[i]=(sum4[i-]+qpow(i,))%rhl;
sum6[i]=(sum6[i-]+qpow(i,))%rhl;
}
for (RG ll x=-lim,y,x2,x4,x6,res;x<=lim;++x){
y=sqrt(n-x*x),x2=qpow(x,),x4=qpow(x,),x6=qpow(x,),res=;
(res+=m*(m+)%rhl*(m+)+*x6-*(m+)*x4+(*m+)*x2)%=rhl;
(ans+=*x4%rhl*sum2[y]+*x2%rhl*sum4[y]+*sum6[y])%=rhl;
(ans-=*(m+)%rhl*x2%rhl*sum2[y])%=rhl;
(ans-=*(m+)%rhl*sum4[y])%=rhl;
(ans+=*(*m+)*sum2[y]+res*(*y+))%=rhl;
}
cout<<(ans+rhl)*((rhl+)/)%rhl*((rhl+)/)%rhl; return ;
}
上一篇:[shell]关闭超时的进程


下一篇:H5播放器