#P2154. [SDOI2009] 虔诚的墓主人

    ID: 1172 远端评测题 800ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>各省省选山东2009树状数组排列组合数论数学

[SDOI2009] 虔诚的墓主人

题目描述

小W是一片新造公墓的管理人。公墓可以看成一块 N×MN×M 的矩形,矩形的每个格点,要么种着一棵常青树,要么是一块还没有归属的墓地。

当地的居民都是非常虔诚的基督徒,他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚,他们希望自己的墓地拥有着较高的虔诚度。

一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地,墓地的正上、正下、正左、正右都有恰好 kk 棵常青树。

小W希望知道他所管理的这片公墓中所有墓地的虔诚度总和是多少。

输入格式

输入文件 religious.in 的第一行包含两个用空格分隔的正整数 NNMM,表示公墓的宽和长,因此这个矩形公墓共有 (N+1)×(M+1)(N+1) ×(M+1) 个格点,左下角的坐标为 (0,0)(0, 0),右上角的坐标为 (N,M)(N, M)

第二行包含一个正整数 WW,表示公墓中常青树的个数。

第三行起共 WW 行,每行包含两个用空格分隔的非负整数 xix_iyiy_i,表示一棵常青树的坐标。输入保证没有两棵常青树拥有相同的坐标。

最后一行包含一个正整数 kk,意义如题目所示。

输出格式

输出文件 religious.out 仅包含一个非负整数,表示这片公墓中所有墓地的虔诚度总和。为了方便起见,答案对 2,147,483,6482,147,483,648 取模。

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

提示

图中,以墓地 (2,2)(2, 2)(2,3)(2, 3) 为中心的十字架各有 33 个,即它们的虔诚度均为 33。其他墓地的虔诚度为 00

对于 30%30\% 的数据,满足 1N,M1031 ≤ N, M ≤ 10^3

对于 60%60\% 的数据,满足 1N,M1061 ≤ N, M ≤ 10^6

对于 100%100\% 的数据,满足 1N,M1091 ≤ N, M ≤ 10^90xiN0 ≤ x_i ≤ N0yiM0 ≤ y_i ≤ M1W1051 ≤ W ≤ 10^51k101 ≤ k ≤ 10

存在 50%50\% 的数据,满足 1k21 ≤ k ≤ 2

存在 25%25\% 的数据,满足 1W1041 ≤ W ≤ 10^4