题目链接

思路

首先，因为这是曼哈顿距离，所以很容易就可以将这三个点之间的距离转化为一个矩形，那么这三个点在矩形上的分布只有六种可能。

假设当前矩形的长为n，宽为m。那么可以发现，无论是哪一种情况，这三个点在这个矩形里的摆放方案都是(n - 2) *( m - 2) 。并且这些摆放方案与这个矩形的位置无关，所以可以先不考虑位置，求出所有方案数之后，再去考虑这个矩形的位置。显然这个矩形可以摆放的位置可以有左上角的点确定。

代码

//https://www.luogu.org/problemnew/show/U48574

#include<cstdio>

#include<iostream>

#define fi(s) freopen(s,"r",stdin);

#define fo(s) freopen(s,"w",stdout);

using namespace std;

typedef long long ll;

const int N = 100000 + 100,mod = 1e9 + 7;

int vis[N],dis[N];

ll read() {

	ll x = 0,f = 1;char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') f = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		x = x * 10 + c - '0';

		c = getchar();

	}

	return x * f;

}

ll ans;

int main() {

	ll n = read(), m = read(),Min = read(),Max = read();

	for(int i = 3;i <= n;++i) {

		for(int j = 3;j <= m;++j) {

			if((i + j - 2) * 2 <= Max && (i + j - 2) * 2 >= Min) {

				ans += 1ll * (i - 2) * (j - 2) * 6 * (n - i + 1) * (m - j + 1) % mod;

				ans %= mod;

			}

		}

	}

	cout<<ans;

	return 0;

}

一言

失去的东西最终都会回到我们身边,虽然有时并不是以我们所期待的方式。 ——浮生物语

巴特西

[luoguU48574][藏妹子之处]

思路

代码

一言

最新文章

热门文章