#P2154. [SDOI2009] 虔诚的墓主人
[SDOI2009] 虔诚的墓主人
题目描述
小W是一片新造公墓的管理人。公墓可以看成一块 的矩形,矩形的每个格点,要么种着一棵常青树,要么是一块还没有归属的墓地。
当地的居民都是非常虔诚的基督徒,他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚,他们希望自己的墓地拥有着较高的虔诚度。
一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地,墓地的正上、正下、正左、正右都有恰好 棵常青树。
小W希望知道他所管理的这片公墓中所有墓地的虔诚度总和是多少。
输入格式
输入文件 religious.in
的第一行包含两个用空格分隔的正整数 和 ,表示公墓的宽和长,因此这个矩形公墓共有 个格点,左下角的坐标为 ,右上角的坐标为 。
第二行包含一个正整数 ,表示公墓中常青树的个数。
第三行起共 行,每行包含两个用空格分隔的非负整数 和 ,表示一棵常青树的坐标。输入保证没有两棵常青树拥有相同的坐标。
最后一行包含一个正整数 ,意义如题目所示。
输出格式
输出文件 religious.out
仅包含一个非负整数,表示这片公墓中所有墓地的虔诚度总和。为了方便起见,答案对 取模。
5 6
13
0 2
0 3
1 2
1 3
2 0
2 1
2 4
2 5
2 6
3 2
3 3
4 3
5 2
2
6
提示
图中,以墓地 和 为中心的十字架各有 个,即它们的虔诚度均为 。其他墓地的虔诚度为 。
对于 的数据,满足 。
对于 的数据,满足 。
对于 的数据,满足 ,,,,。
存在 的数据,满足 。
存在 的数据,满足 。