【[CQOI2014]数三角形】

lx让做的题，其实很简单，难度评到紫令人吃惊

首先读进来\(n,m\)先\(++\)，之后就是一个格点数为\(n*m\)的矩阵了

我们直接求很那做，补集转化一下，我们容斥来做

首先所有的情况自然是\(C_{n*m}^3\)了

再算出不合法的情况

之后有\(m\)列，三个点在同一列上的方案数自然是\(m*C_n^3\)

有\(n\)行，三个点在同一行的方案数是\(n*C_m^3\)

最后还有斜线上的情况，由于一条方向向量为\((x,y)\)的直线，当两个端点在整点上的时候，直线上还有\(gcd(x,y)-1\)个整点，而这样的的直线一共有\((n-x)(m-y)\)条，这样只考虑了斜率为正的情况，自然还有斜率为负的情况，显然两种情况数量相等，最后还要再乘以二

所以斜线上三点共线的方案数为

\[2*\sum_{i=1}^n\sum_{j=1}^m(gcd(i,j)-1)*(n-i)*(m-j)
\]

那么最后的答案就是

\[C_{n*m}^3-m*C_n^3-n*C_m^3-2*\sum_{i=1}^n\sum_{j=1}^m(gcd(i,j)-1)*(n-i)*(m-j)
\]

显然这都是可以随便求得，如果\(n,m\)再大一些后面就需要反演啦

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#define LL long long

#define re register

LL n,m,ans;

inline LL C(LL n,LL m)

{

	LL T=1;

	for(re int i=n;i>=n-m+1;i--) T*=(LL)(i);

	for(re int i=1;i<=m;i++) T/=(LL)(i);

	return T;

}

inline LL read()

{

	char c=getchar();

	LL x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9')

	  x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

LL gcd(LL a,LL b)

{

	if(!b) return a;

	return gcd(b,a%b);

}

int main()

{

	n=read()+1,m=read()+1;

	ans=C(n*m,3);

	ans-=C(n,3)*m+C(m,3)*n;

	for(re int i=1;i<=n;i++)

	for(re int j=1;j<=m;j++)

		ans-=2ll*(gcd(i,j)-1)*(n-i)*(m-j);

	std::cout<<ans;

	return 0;

}

巴特西

【[CQOI2014]数三角形】

最新文章

热门文章