#P3565. [SHOI2014]超能粒子炮

    ID: 2763 传统题 2000ms 256MiB 尝试: 87 已通过: 33 难度: 8 上传者: 标签>难度分类提高+/省选-多项式与生成函数分段多项式模拟与实现技巧坐标变换数论模逆元费马小定理快速幂向下取整与向上取整线性代数与代数等差数列求和CF2400

[SHOI2014]超能粒子炮

[SHOI2014] 超能粒子炮

题目背景

shoi2014 day1t3

题目描述

邪恶的巨型宇宙怪物 CCM (Crazy Code Monster) 即将对美丽的地球发动攻击!

在这千钧一发的时刻,地球联合军决定使用地球最先进的能量武器——由发明家 SHTSC 设计的超能粒子炮彻底摧毁 CCM。

超能粒子炮由垂直方向从上到下共 nn 个超能粒子发射管构成,编号 1∼n1 \sim n。所有的发射管都会在开火的一瞬间同时发射出强大的超能粒子流。
为了彻底摧毁再生能力极强的邪恶宇宙怪物 CCM,地球联合军将 CCM 从上到下分为 mm 个区域,编号 1∼m1 \sim m,分别进行打击。其中超能粒子炮的第 ii 号发射管将会对准 f(i)f(i) 号区域发射。f(i)f(i) 的公式如下:

f(i)=(ai+b) mod m+1.f(i)=(ai+b)\bmod m+1.

其中 a,ba, b 都是给定的常数。

然而,出于某种不可告人的目的,N 财团不希望 CCM 被超能粒子炮彻底消灭。于是 N 财团以远程精神控制了超能粒子炮的操作员——你来阻止地球军消灭 CCM。

你发现,超能粒子炮的开火模式会使得不同的粒子流的运动轨迹发生交叉,而在所有这些交叉点处部署一种名为折跃棱镜的能量反射装置就能使得超能粒子炮因过载而自爆。这样,你就可以阻止地球联合军使用超能粒子炮摧毁 CCM 而成为下一代 N 财团金牌的获得者。

为了实现这个计划,你需要知道有多少对粒子流 i,ji, j,满足 i<ji<j 且 f(i)>f(j)f(i) > f(j)。

输入格式

一行四个整数 n,m,a,bn,m,a,b,依次表示发射管数、区域数和公式中的两个常数。

输出格式

输出一行一个整数,为运动轨迹交叉的粒子流的对数。

样例 #1

2 3 2 2
1

样例 #2

5 5 2 0
7

数据范围

  • 对于 10%10\% 的数据,n≤5×103n\le5\times10^3。
  • 对于 20%20\% 的数据,n≤m≤106n\le m\le10^6。
  • 对于额外 20%20\% 的数据,b=0b=0。
  • 对于 80%80\% 的数据,1≤a≤10001\le a\le1000。
  • 对于 100%100\% 的数据,1≤n≤m≤1091\le n\le m\le10^9,mm 是质数,1≤a<m1\le a<m,0≤b<m0\le b<m。存在 a′a' 满足 aa′≡1(modm)aa'\equiv1\pmod m,且 min⁡(a,a′)≤1000\min(a,a')\le1000。