honoka和格点三角形
2024-10-20 18:51:05
题目:
honoka最近在研究三角形计数问题。
她认为,满足以下三个条件的三角形是“好三角形”。
1.三角形的三个顶点均为格点,即横坐标和纵坐标均为整数。
2.三角形的面积为 。
3.三角形至少有一条边和 轴或 轴平行。
honoka想知道,在平面中选取一个大小为 的矩形格点阵,可以找到多少个不同的“好三角形”?由于答案可能过大,请对 取模。
她认为,满足以下三个条件的三角形是“好三角形”。
1.三角形的三个顶点均为格点,即横坐标和纵坐标均为整数。
2.三角形的面积为 。
3.三角形至少有一条边和 轴或 轴平行。
honoka想知道,在平面中选取一个大小为 的矩形格点阵,可以找到多少个不同的“好三角形”?由于答案可能过大,请对 取模。
思路:
分两种情况讨论:
分两种情况讨论:
(1)两条边和两个坐标轴平行
(2)只有一条边和某个坐标轴平行
首先根据题中的条件可以看出三角型是低与高是1*2或是2*1.
第一种情况:
第一种情况:
如图,一共有4*(n-2)*(m-1)+4*(m-2)*(n-1)种。
第二种情况:
第二种情况:
可以分为底边为 2、高为 1 和底边为 1 、高为 2的情况。
①对于底边为2,高为1
①对于底边为2,高为1
若底边和x轴平行,那么底边在x方向上有 m−2 种可能,顶点在x方向上也有 m−2(顶点的位置一共有m个,减去第一种情况中的两种)种可能,在y方向上有 n-1 种可能;
故共有2*(m-2)*(m-2)*(n-1)
若底边和y轴平行,同理可推出2*(n-2)*(n-2)*(m-1)
②对于底边为1,高为2的情况
底边与x轴平行时 2*(m-1)*(m-2)*(n-2)
底边与y轴平行时2*(n-1)*(n-2)*(m-2)。
最后将所有的情况的都加起来最终解,注意用long long 存储,进行相加的时候要及时取模。
代码:
1 #include <map>
2 #include <set>
3 #include <list>
4 #include <stack>
5 #include <queue>
6 #include <deque>
7 #include <cmath>
8 #include <ctime>
9 #include <string>
10 #include <limits>
11 #include <cstdio>
12 #include <vector>
13 #include <iomanip>
14 #include <cstdlib>
15 #include <cstring>
16 #include <istream>
17 #include <iostream>
18 #include <algorithm>
19 #define ci cin
20 #define co cout
21 #define el endl
22 #define Scc(c) scanf("%c",&c)
23 #define Scs(s) scanf("%s",s)
24 #define Sci(x) scanf("%d",&x)
25 #define Sci2(x, y) scanf("%d%d",&x,&y)
26 #define Sci3(x, y, z) scanf("%d%d%d",&x,&y,&z)
27 #define Scl(x) scanf("%I64d",&x)
28 #define Scl2(x, y) scanf("%I64d%I64d",&x,&y)
29 #define Scl3(x, y, z) scanf("%I64d%I64d%I64d",&x,&y,&z)
30 #define Pri(x) printf("%d\n",x)
31 #define Prl(x) printf("%I64d\n",x)
32 #define Prc(c) printf("%c\n",c)
33 #define Prs(s) printf("%s\n",s)
34 #define For(i,x,y) for(int i=x;i<y;i++)
35 #define For_(i,x,y) for(int i=x;i<=y;i++)
36 #define FFor(i,x,y) for(int i=x;i>y;i--)
37 #define FFor_(i,x,y) for(int i=x;i>=y;i--)
38 #define Mem(f, x) memset(f,x,sizeof(f))
39 #define LL long long
40 #define ULL unsigned long long
41 #define MAXSIZE 100005
42 #define INF 0x3f3f3f3f
43
44 const int mod=1e9+7;
45 const double PI = acos(-1.0);
46
47 using namespace std;
48
49 int main(){
50 LL n,m;
51 //Sci2(n,m);
52 ci>>n>>m;
53 LL sum=(n-2)*(m-1)*4%mod+(n-1)*(m-2)*4%mod;
54 sum=(sum+2*(n-1)*(m-2)%mod*(m-2)%mod+2*(m-1)*(n-2)%mod*(n-2)%mod)%mod;
55 sum=(sum+2*(n-2)*(m-1)%mod*(m-2)%mod+2*(m-2)*(n-1)%mod*(n-2)%mod)%mod;
56 co<<sum;
57 return 0;
58 }
最新文章
- .NET中集合已修改;可能无法执行枚举操作 的解决办法
- python和数据科学(Anaconda)
- day1 初识Linux
- 驱动实现led,pwm和中断基础知识
- iOS 系统架构
- PHP解释器引擎执行流程 - [ PHP内核学习 ]
- Firefox SVG getBBox方法返回&#39;NS_ERROR_FAILURE&#39;错误分析
- Ajax与用户交互的存储格式JSON
- Liferay JSP中常用的标签
- Linux服务器集群系统(一)--转
- (十三)学习CSS之两个class连一起隔空格和逗号
- SAP HANA 中的决策表(Decision Table)
- YII2 运行概述(Overview)
- 【Xilinx-LVDS读写功能实现】-00-开始
- JavaScript函数补完:toString()
- CHECKDB内部:什么是BlobEater?
- git 相关学习
- Luogu P1654 OSU!
- KMP 求最小循环节
- samba 二进制包 tar.gz 安装