「NOIP模拟赛」藏妹子之处

2014年9月6日3,8304

问题描述：

今天CZY又找到了三个妹子，有着收藏爱好的他想要找三个地方将妹子们藏起来，将一片空地抽象成一个R行C列的表格，CZY要选出3个单元格。但要满足如下的两个条件：

（1）任意两个单元格都不在同一行。

（2）任意两个单元格都不在同一列。

选取格子存在一个花费，而这个花费是三个格子两两之间曼哈顿距离的和（如(x1,y1)和(x,y2)的曼哈顿距离为|x1-x2|+|y1-y2|）。狗狗想知道的是，花费在minT到maxT之间的方案数有多少。

答案模1000000007。所谓的两种不同方案是指：只要它选中的单元格有一个不同，就认为是不同的方案。

输入格式：

一行，4个整数，R、C、minT、maxT。3≤R,C≤4000, 1≤minT≤maxT≤20000。

对于30%的数据, 3 ≤ R, C ≤ 70。

输出格式:

一个整数，表示不同的选择方案数量模1000000007后的结果。

输入输出样例：

输入样例	3 3 1 20000	3 3 4 7	4 6 9 12	7 5 13 18	4000 4000 4000 14000
输出样例	6	0	264	1212	859690013

题解

对于曼哈顿距离。。。可以行列分开考虑。。。

而对于一条直线上的三点，俩俩之间的曼哈顿距离和为2*(最大值-最小值)

行之间的曼哈顿距离为2x的方案即在n行内选取距离x的俩点，另一点在这俩点中间任取

易得方案数为(n-x)*(x-1)

枚举行列分别对答案的贡献，统计答案

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define inf 1000000000
#define mod 1000000007
#define ll long long
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,mn,mx;
int t1[10005],t2[10005];
void cal()
{
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(2*(i+j)>=mn&&2*(i+j)<=mx)
				ans=(ans+(ll)t1[i]*t2[j]*6%mod)%mod;
	printf("%d\n",ans);
}
int main()
{
	//freopen("excel.in","r",stdin);
	//freopen("excel.out","w",stdout);
	n=read();m=read();mn=read();mx=read();
	for(int i=1;i<=n;i++)t1[i]=(n-i)*(i-1);
	for(int i=1;i<=m;i++)t2[i]=(m-i)*(i-1);
	cal();
	return 0;
}