[CQOI2014]数三角形(组合计数+容斥原理)
题意： 给一个n*m的网格，让你计算三角形三个顶点都在网格点上的三角形的数量。
思路： 首先我们可以知道，n * m的网格一共有 sum= (n+1)*(m+1) 个网格点。
然后在一个矩形的网格中，要想组成三角形，只需要满足三点不共线即可
我们预处理C[i][j]这样一个数组，表述从i个格点中抽取j个格点的数量。 那么ans = C[sum][3] - 三点共线
那么接着我们来考虑三点共线的情况： 1.横着共线 2.竖着共线 3.斜着共线
1.对于横着共线：C[n+1][3]*(m+1); 我们可以理解为一列中有n+1个网格点，我们从中拿出三个，然后一共有m+1列。
2.同上
3.对于斜着共线： 我们要有这样的一个理念：固定两个端点，然后以这两个点为坐标做直角三角形，那么覆盖整点数为gcd(直角边，直角边)+1
作图解释下：
在这里插入图片描述
如上图，我们现有AB两个端点，我们想在AB之间再找一个点，那么首先我们需要知道AB之间有多少个点，即为—gcd(AC,AB)+1 然后我们减去2个端点即为第三个点可选取的个数。
在得到这第三个点可选取个数后，我们这条斜线可不是只有这么一条啊。我们可以在网格里面上下左右移动。 作图解释如下：
在这里插入图片描述
其中，红色为初始。（其实图中三角形斜线就不够三个点是不符合的，但主要是作图不好画，大家理解即可）
我们枚举三角形两条直角边的长度，然后判断是否斜边覆盖>=3个端点，减去2个端点，乘以(n-i)乘以(m-j)。因为矩阵有主对角线跟副对角线，所以我们还得乘2。
到这里，我们把三点共线情况都减去，即得到ans。
code：
#include<bits/stdc++.h>
#define maxn 1000010
using namespace std;
typedef long long ll;
ll c[maxn][5];
ll n,m,sum,ans;
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
void init(){//因为只需要选择3个点，我们处理到3即可
c[0][0] = 1;
for(int i=1;i<=sum;i++){
c[i][0]=1;
for(int j=1;j<=3;j++){
c[i][j] = c[i-1][j] + c[i-1][j-1];
}
}
}
void solve(){
ll res;
ans = c[sum][3];
ans -= c[n][3]*m + c[m][3]*n;//减去横的竖的
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
res = gcd(i,j)+1;
if(res==2) continue;//不够三个点跳过
else ans -= (res-2)*(n-i)*(m-j)*2;//够上下左右移动后所有的数量
}
}
}
int main(){
cin>>n>>m;
n++,m++; //这里我直接让其自加，方便后续处理
sum = n*m;
init();
solve();
cout<<ans<<endl;
return 0;
} 本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-04-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读