【NOIP模拟赛】藏妹子之处

2014年9月6日1,7394

问题描述:

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

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

 

  • 掠涛飞燕2014年9月8日 下午10:29 回复

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

    #1  
  • Leon2015年11月1日 下午3:19 回复

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

    #2  
    • hzwer2015年11月1日 下午10:57 回复

      比如选择1,2,3行的1,2,3列,每行每列放一个,有6种方案

      #21
      • Leon2015年11月2日 上午8:08 回复

        懂了,匹配数为6.。。。多谢神犇回复

        #22