[Mathematics / polynomial / derivation] 200606Practice T3 square

In the exam room, I misspelled them directly into square. I can't help my poor English 😭

Algorithm 1

20pts, examination practice

fif_ifi: i × ii\times ii × i scheme number
ans=∑i=1min⁡{n,m}(n−i+1)(m−i+1)fi ans=\sum_{i=1}^{\min\{n,m\}}(n-i+1)(m-i+1)f_i ans=i=1∑min{n,m}​(n−i+1)(m−i+1)fi​
O(NT)O(NT)O(NT)
Try team Mo's optimization (but geese can't)

Research fif_ifi, observe the square of 5 × 55\times 55 × 5:

Consider symmetry and omit half of the squares:

It is found that the favorability of each square should be i2 − (the number of squares on the corner is cut by the side) i^2 - (the number of squares on the corner is cut by the side) i2 − (the number of squares on the corner is cut by the side)

Cut off the number of squares on the corner:


Easy to find:

For the line of a square in i × ii\times ii × i, abscissa and ordinate a,ba,ba,b (and satisfy a+b=ia+b=ia+b=i)
Let the vertical coordinate of the intersection of the line x=j,j ∈ N * x=j,j\in N^*x=j,j ∈ N * be yjy_jyj, then the number of squares on (j,j+1)(j,j+1)(j,j+1) is
⌊b−yj⌋ \lfloor b-y_j\rfloor ⌊b−yj​⌋

20pts code_slow

#include<bits/stdc++.h>
#define re register
#define in Read()
using namespace std;
inline int in{
	int i=0,f=1;char ch;
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')ch=getchar(),f=-1;
	while(isdigit(ch))i=(i<<1)+(i<<3)+ch-48,ch=getchar();
	return i*f;
}

const int NNN=1e6+10;
const int MOD=100000007;
const int eps=1e-6;
int T;
struct Query{
	int n,m;
	int id;
	int ans;
}q[NNN];

struct Point{
	int x,y;
	
	Point(){}
	Point(int _x,int _y){x=_x,y=_y;}
};

struct Line{
	double k,b;
	
	Line(){}
	Line(Point u,Point v){
		k=1.0*(u.y-v.y)/(u.x-v.x);
		b=u.y-k*u.x;
	}
	
	inline int y(int x,int h){
		double s=k*x+b;
		if(fabs(s-int(s))<eps)return h-int(s);
		else return int(h-s);
	}
}l;

int up;
int f[NNN];

inline int get_f(int len){
	int res=0;
//	For (re int x = ((len & 1)? ((len > > 1) + 1): (len > > 1)); x < = len; + + x) {/ / Note symmetry 
	for(re int x=1;x<=len;++x){
		int y=len-x,out/*For a small rectangle with (0,y),(x,0) diagonal, the cut / top right corner*/=0;
		l=Line(Point(0,y),Point(x,0));
//		printf("y=%lfx+%lf\n",l.k,l.b);
		for(re int i=0;i<x;++i){
			out+=l.y(i,y);
//			printf("%d ",l.y(i,y));
		}
		out/*For the whole square, the cut / four corners*/=4*(x*y-out);
//		if((!(x^y))||(!y))res=(res+(len*len-out))%MOD;
//		else
			res=((res+(len*len-out))/**2*/)%MOD;
	}
	return res;
}

int main(){
	
	freopen("sqare.in","r",stdin);
	freopen("sqare.out","w",stdout);
	
	T=in;
	for(re int i=1;i<=T;++i)
		q[i].n=in,q[i].m=in,q[i].id=i,
		up=max(up,max(q[i].n,q[i].m));
	
	for(re int i=1;i<=up;++i)
		f[i]=get_f(i);
	
	for(re int i=1;i<=T;++i){
		up=min(q[i].n,q[i].m);
		for(re int j=1;j<=up;++j)
			q[i].ans=(q[i].ans+(q[i].n-j+1)*(q[i].m-j+1)*f[j])%MOD;
		printf("%d\n",q[i].ans);
	}
	
	return 0;
}

//int main(){
//	for(re int i=1;i<=5;++i)
//		printf("%d\n",get_f(i));
//}

20pts code_a_little_bit_quicker

#include<bits/stdc++.h>
#define re register
#define in Read()
using namespace std;
inline int in{
	int i=0,f=1;char ch;
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')ch=getchar(),f=-1;
	while(isdigit(ch))i=(i<<1)+(i<<3)+ch-48,ch=getchar();
	return i*f;
}

const int NNN=1e6+10;
const int MOD=100000007;
const int eps=1e-6;
int T;
struct Query{
	int n,m;
	int id;
	int ans;
}q[NNN];

struct Point{
	int x,y;
	
	Point(){}
	Point(int _x,int _y){x=_x,y=_y;}
};

struct Line{
	double k,b;
	
	Line(){}
	Line(Point u,Point v){
		k=1.0*(u.y-v.y)/(u.x-v.x);
		b=u.y-k*u.x;
	}
	
	inline int y(int x,int h){
		double s=k*x+b;
		if(fabs(s-int(s))<eps)return (h-int(s))%MOD;
		else return (int(h-s))%MOD;
	}
}l;

int up;
int f[NNN];

inline int get_f(int len){
	int res=0;
	for(re int y=(len>>1);y>=0;--y){//Pay attention to symmetry 
//	for(re int x=1;x<=len;++x){
		int x=len-y,out/*For a small rectangle with (0,y),(x,0) as a diagonal, the cut / top right corner*/=0;
		l=Line(Point(0,y),Point(x,0));
//		printf("y=%lfx+%lf\n",l.k,l.b);
		for(re int i=0;i<x;++i){
			out=(out+l.y(i,y))%MOD;
//			printf("%d ",l.y(i,y));
		}
		out/*For the whole square, the cut / four corners*/=4*(x*y-out);
		if((!(x^y))||(!y))res=(res+(len*len-out))%MOD;
		else
			res=((res+(len*len-out)*2))%MOD;
	}
	return res%MOD;
}

int main(){
	
	freopen("square.in","r",stdin);
	freopen("square.out","w",stdout);
	
	T=in;
	for(re int i=1;i<=T;++i)
		q[i].n=in,q[i].m=in,q[i].id=i,
		up=max(up,max(q[i].n,q[i].m));
	
	for(re int i=1;i<=up;++i)
		f[i]=get_f(i);
	
	for(re int i=1;i<=T;++i){
		up=min(q[i].n,q[i].m);
		for(re int j=1;j<=up;++j)
			q[i].ans=(q[i].ans+(q[i].n-j+1)*(q[i].m-j+1)%MOD*f[j])%MOD;
		printf("%d\n",q[i].ans);
	}
	
	return 0;
}

Algorithm 2

It is noted that the geometric accuracy used in the above method is not correct and the geometric operation takes a long time
Consider mathematical derivation:

Contribution to "positive" squares:
∑i=1min⁡(n,m)i2(n−i+1)(m−i+1) \sum_{i=1}^{\min(n,m)}i^2(n-i+1)(m-i+1) i=1∑min(n,m)​i2(n−i+1)(m−i+1)
Contribution to "slanted" squares:
Consider subtracting the number of small squares cut by four sides from the "positive" square
For an edge, it may pass through a node. After considering gcd, it can be concluded that gcd nodes do not pass through nodes
It is found that a small square is cut off to the right of each intersection point with the vertical grid line (illegal), a GCD ⁡ (a,b) − 1\frac{a}{\gcd(a,b)}-1gcd(a,b)a − 1
At each intersection with the horizontal gridlines, a small square is cut (illegal), B GCD ⁡ (a,b) − 1\frac{b}{\gcd(a,b)}-1gcd(a,b)b − 1
Plus the one from the middle of the corner, gcd (a,b) x ((agcd (a,b) - 1)+(bgcd (a,b) - 1) + 1) gccd (a,b) times ((\ frac {a} {\ gccd (a,b)}-1) + (\ frac {a} {\ gccd (a,b)}-1) + 1) gccd (a,b) × ((gccd (a,b) A-1) + (gccd (a,b) a, b) b) B (a,b) 1) + (gccd (a,b) a, B (a,b) b) B (a,b) 1) + (gccd (a,b) B (a,b) B (a,b) 1) + (gccd (a,b) a (- 1) + 1)
∑i=1min⁡(n,m)(∑a=1b=i−ai−1i2−4×ab−gcd⁡(a,b)×((agcd⁡(a,b)−1)+(bgcd⁡(a,b)−1)+1)2)(n−i+1)(m−i+1) \sum_{i=1}^{\min(n,m)}(\sum_{a=1\\b=i-a}^{i-1}i^2-4\times\frac{ab-\gcd(a,b)\times((\frac{a}{\gcd(a,b)}-1)+(\frac{b}{\gcd(a,b)}-1)+1)}{2})(n-i+1)(m-i+1) i=1∑min(n,m)​(a=1b=i−a∑i−1​i2−4×2ab−gcd(a,b)×((gcd(a,b)a​−1)+(gcd(a,b)b​−1)+1)​)(n−i+1)(m−i+1)
Add up
KaTeX parse error: \cr valid only within a tabular/array environment

Posted on Sat, 06 Jun 2020 01:44:15 -0700 by dsartain