CF 449E Jzzhu and Squares解题报告

题目大意


给定一个N*M的网格。对一个顶点为格点的正方形R(不一定与格线平行),计算出其中有多少个单位格被R完全包含(记作F(R))。求所有正方形的F(R)之和。

题解

首先画一个“勾股图”:



粉色是我们的正方形(不和格线平行),设其外接正方形的边长为L,四周直角三角形的短边为a,则长边为L-a。设其中完整包含了F(L,a)个单位格。

可以发现,其中完全包含的单位正方形分成两部分:第一部分是中间小正方形里的个,第二部分是周边直角三角形里包含的。

我们这么计算第二部分:一红一白两个直角三角形拼成的矩形内有(L-a)*a个单位格,而对角线穿过了L-gcd(L,a)格,再除以2,就得到了一个三角形内的单位格数。将其乘以4,总共加起来得到:



没错,“斜线下方的格点数”没有简单公式,但“单位格数”有!

可以发现,F(L,a)即使当a>L-a时也成立,所以我们可以直接用a枚举到底,整道题目的答案就是:



我们把展开:



这分成两部分:第一部分是一个关于L的多项式,第二部分是gcd(L,a)的前缀和。

可以想象,也是如此分成两部分:第一部分是一个关于L的多项式(确切地说,是5次多项式),第二部分也是一个关于L的“多项式”,但其“未知数项”不是这种形式,而是这种形式。

至于怎么得到这个多项式呢,如果你数学好可以手推……作为一名数学技能荒废一年的咸鱼选手,我就直接用vector当低配版多项式类,让电脑推了……

不要忘了,我们要求的是上面那个玩意的前缀和。因此,只需要求出来这两种形式关于L的“前缀和”,然后乘以多项式中相应的系数,就可以完成任务。

前者很简单:L不超过10^6,暴力递推即可。后者也差不多,只需要先递推出来phi函数,然后枚举gcd(a,L)的值,就可以把Σgcd的表都打出来,详见代码。

代码

#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
typedef vector Poly;
const LL MOD=1000000007;
const int H=6;
LL gcd(LL a,LL b){
	return !b?a:gcd(b,a%b);
}
LL lcm(LL a,LL b){
	return a*b/gcd(a,b);
}
LL quickpow(LL a,LL n){
	LL ans=1;
	while(n){
		if(n&1) ans=(ans*a)%MOD;
		a=(a*a)%MOD;
		n>>=1;
	}
	return ans;
}
LL inverse(LL a){
	return quickpow(a,MOD-2);
}
void print(Poly a){
	for(int i=0;iM) swap(N,M);
	//N是较小者
	A[0]=M+1,A[1]=-1;Poly D(A,A+2);
	A[0]=N+1,A[1]=-1;D=D*Poly(A,A+2);
	Poly F=give_Fsum_L();
	Poly F1=D*F;
	LL ans=0;
	ans+=calc_presum_with(F1,P[N]);
	ans%=MOD;
	A[0]=2;
	Poly F2=D*Poly(A,A+1);
	ans+=calc_presum_with(F2,PG[N]);
	ans%=MOD;
	ans=(ans+MOD)%MOD;
	printf("%I64d\n",ans);
}
void prepare(void){
	for(int i=1;i

发表评论

电子邮件地址不会被公开。 必填项已用*标注