http://www.lydsy.com/JudgeOnline/problem.php?id=3505?(題目鏈接)

題意

　　給定一個n*m的網(wǎng)格，請計算三點都在格點上的三角形共有多少個。

Solution

$${ans=平面中選三個點的方案數(shù)-三點共線的方案數(shù)}$$

$${ans=C_{(n+1)*(m+1)}^{3}-(n+1)*C_{m+1}^{3}-(m+1)*C_{n+1}^{3}-斜的三點共線的方案數(shù)}$$

　　斜的三點共線方案數(shù)不會求。。左轉(zhuǎn)題解：http://blog.csdn.net/zhb1997/article/details/38474795

細節(jié)

　　LL

代碼

// bzoj3505 #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #define LL long long #define inf 10000000 #define Pi acos(-1.0) #define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); using namespace std;int n,m; LL c[2000010][4];int gcd(int a,int b) {return b==0 ? a : gcd(b,a%b); } int main() {scanf("%d%d",&n,&m);for (int i=0;i<=(n+1)*(m+1);i++) c[i][0]=1;for (int i=1;i<=(n+1)*(m+1);i++)for (int j=1;j<=min(3,i);j++) c[i][j]=c[i-1][j-1]+c[i-1][j];LL ans=c[(n+1)*(m+1)][3]-(n+1)*c[m+1][3]-(m+1)*c[n+1][3];for (int i=1;i<=n;i++)for (int j=1;j<=m;j++) {LL x=gcd(i,j)+1;if (x>2) ans-=(x-2)*2*(n-i+1)*(m-j+1);}printf("%lld",ans);return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/MashiroSky/p/6217010.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj3505】 Cqoi2014—数三角形的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。