链接:https://ac.nowcoder.com/acm/contest/3002/A
如果要构成一个好三角形要么底为2高为1,要么底为1高为2
如果在m(x轴)中以2为底:
在每个以2为底的段中若顶部的高为1符合条件 我们可以找到m个
如图:

所以(m-2)*(n-1)*2 就是在m中底为2的好三角形个数
(m-2):m个点有(m-2)个底为2的段
(n-1):最多算到n-1,若在最顶上则没有高为1
*2:倒着求一遍
在m:中以1为底同理
算在n(y轴)中会有重复的好三角形会算进去 会重复一个 我们就少算一个就行了

AC代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include<iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)

inline int read() {
    int x = 0, neg = 1; char op = getchar();
    while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
    while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
    return neg * x;
}
inline void print(int x) {
    if (x < 0) { putchar('-'); x = -x; }
    if (x >= 10) print(x / 10);
    putchar(x % 10 + '0');
}

const int N = 1e6 + 5;
const ll M = (ll)1e9+7;
int main() {
    ll n,m;
    cin >> n >> m;
    ll res = 0;
    res += m%M*(m-2)%M*(n-1)%M*2;//m:以2为底
    res += n%M*(n-2)%M*(m-1)%M*2;//n:以2为底
    res += (m-2)%M*(m-1)%M*(n-2)%M * 2;//m:以1为底
    res += (n-2)%M*(n-1)%M*(m-2)%M * 2;//n:以1为底
    cout << res%M << endl;
}
Last modification:August 5th, 2020 at 01:21 am
如果觉得我的文章对你有用,请随意赞赏