题解 P3166 数三角形
星沐
·
·
题解
这是道关于排列组合的题目
然后我们先来看排列组合的几个公式，如下
\frac{}{}
$\frac{}{}
###### ① 从n个不同元素中，任取m个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。
###### ② 从n个不同元素中，取出m个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数。
###### 即A（n,m）；
###### ① 从n个不同元素中，任取m个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。
###### ② 从n个不同元素中，取出m个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。
###### 即C（n,m）；
------------
##### 思路：用C（n，m)的公式，先求出全集，再来减去重复的，重复的有三种，在行上，在列上，在斜线上。
### 记得用long long不然会爆int，因为我这道题就爆int了。
## 考试时记得看数据范围。
```
```
------------
### 主代码如下
```
n++;
m++; //n乘以m，有n+1条线，有m+1条线，
ans=(n*m-2)*(n*m-1)*(n*m)/（1*2*3）;//因为是求C(n*m,3);
if(n>=3)//保证n-2>0;
ans-=m*n*(n-1)*(n-2)/（1*2*3）;//因为是求C(n,3)，且有m列，所以乘以m；
if(m>=3)//保证m-2>0;
ans-=n*m*(m-1)*(m-2)/（1*2*3）；//因为是求C(m,3)，且有n行，所以乘以n；
for(int i=1;i<n;++i)
for(int j=1;j<m;++j)
ans-=(n-i)*(m-j)*(__gcd(i,j)-1)*2;
//__gcd(i,j)-1为求斜线的点的选择方案。
//因为上下翻转都有，所以乘以2；
//最后输出ans的值。
```
##### 思路和其他题解差不多，但我加上了一些理解，如有不准确的地方，请指正，谢谢；