「NOIP模拟赛」藏妹子之处

2014年9月6日3,7924

问题描述:

今天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)

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

 

avatar
2 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
Leonhzwer掠涛飞燕 Recent comment authors
  Subscribe  
提醒
Leon
Leon

神犇求解释一下,为何要*6?

掠涛飞燕

黄巨大解释一下,t1和t2两个数组什么意思啊?我比较逗。。写残了