A22500.大横幅

省选/NOI-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

贝茜从国外长途旅行回来根西岛,农夫约翰想为她的到来挂上一面漂亮的“欢迎回家”横幅。Farmer John 的田地具有整数维度 M x N(1 <= M,N <= 100,000),他在田地的每个可能点都安装了一个带有整数坐标的柱子(如果我们为田地分配一个坐标系,使 (0,0) 在左下角,(M,N) 在右上角)。在这些 (M+1) * (N+1) 点中,Farmer John 必须选择两个作为横幅的端点。

农民约翰是一个完美主义者,他坚持认为旗帜必须完全笔直。这意味着,对于他选择的两个帖子,横幅将在它们之间形成的线段上不能有任何其他帖子。此外,Farmer John 希望横幅的长度至少为 L,最多为 H (1 <= L <= H <= 150,000)。农夫约翰需要你的帮助来弄清楚他有多少种可能的方式可以悬挂横幅。横幅是可逆的,因此切换横幅的两个端点与悬挂横幅的方式相同。由于这个数字可能非常大,Farmer John 只是想知道它是什么模 B (1 <= B <= 1,000,000,000)。

考虑下面的示例,其中 M = 2 且 N = 2:

          • 农民约翰希望横幅的长度在 1 到 3 之间。任何帖子的选择都满足此长度要求,但请注意,不能选择八对:

(0, 0) 和 (2, 0): (1, 0) 在它们之间的线段上

(0, 1) 和 (2, 1): (1, 1) 位于它们之间的线段上

(0, 2) 和 (2, 2): (1, 2) 在它们之间的线段上

(0, 0) 和 (2, 2): (1, 1) 在它们之间的线段上

(0, 0) 和 (0, 2): (0, 1) 位于它们之间的线段上

(1, 0) 和 (1, 2): (1, 1) 位于它们之间的线段上

(2, 0) 和 (2, 2): (2, 1) 在它们之间的线段上

(0, 2) 和 (2, 0): (1, 1) 位于它们之间的线段上

因此,总共有 (9 选择 2) - 8 = 28 个可能的位置。
给出n,m,l,h,问有多少点A(ax,ay),B(bx,by)满足:ax,bx∈[0,n], ay,by∈[0,m],l<=AB<=h,且线段AB上除A,B外无整点。

输入格式

  • 第 1 行:五个空格分隔的整数:M、N、L、H 和 B。

输出格式

  • 第 1 行:一个整数,表示可能的横幅(模 B)的数量。

输入输出样例

  • 输入#1

    2 2 1 3 100 
    

    输出#1

    28 
    

说明/提示

  • 第 1 行:一个整数,表示可能的横幅(模 B)的数量。
首页