#P13293. [PA2018] Wielokąty

    ID: 12477 传统题 10000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3200NOI/NOI+/CTS双射计数边界格点 GCD 计数自定义排序规则0/1 背包计数 DP倒序更新避免重复使用前缀和优化 DP补集转化容斥原理扩大模数后精确整除

[PA2018] Wielokąty

题目描述

请求出满足以下条件的多边形的个数:

  • 记该多边形的第 ii 个顶点为(xi,yi)(x_i,y_i) ,则 xi,yi∈Zx_i,y_i \in \mathbb{Z} 且 1≤xi≤X1 \le x_i \le X , 1≤yi≤Y1 \le y_i \le Y 。
  • 该多边形的任意一条边(不包含端点)不能经过格点(即横纵坐标都为整数的点)。
  • 该多边形的每一条边的长度都是不超过 KK 的整数。
  • 该多边形是一个凸多边形,而且不能退化(至少有三个顶点,不自交,所有内角严格小于 180∘180 ^{\circ},因此任意三个顶点不共线)。
  • 该多边形的每一条边都是线段。

由于满足条件的多边形数量太大,你只需要输出其对 2322^{32} 取模后的值即可。

下图展示了三个不合法的多边形。第一个多边形的边经过了格点,第二个多边形退化了,第三个多边形不是凸的。而且第一,三个有的边长不是整数。

两个多边形不同,当且仅当存在一个点只属于其中一个多边形的顶点集合。

输入格式

输入只有一行,包含三个正整数 X,Y,KX,Y,K。

输出格式

输出一行一个整数,即为满足条件的多边形的数量对 2322^{32} 取模后的值。

输入输出样例 #1

输入 #1

6 5 5

输出 #1

42

样例解释

四边形 (2,1),(2,2),(6,5),(3,1)(2,1),(2,2),(6,5),(3,1) 是 4242 个合法多边形中的一个。

可以验证,该多边形满足每一个条件。

数据范围

1≤X,Y≤1091 \le X,Y \le 10^9,1≤K≤2501 \le K \le 250。时间限制 1010 秒,内存限制 512512 MB。

原赛每个测试组至少满足以下一项条件。

  1. K≤15K\le15。
  2. X,Y≤150X,Y\le150。
  3. 2000≤X,Y≤24002000\le X,Y\le2400,且 K≤100K\le100。
  4. X,YX,Y 都是 10610^6 的倍数。

PA 2018 主办方原题