[SHOI2014]超能粒子炮

邪恶的巨型宇宙怪物 CCM(Crazy Code Monster)即将对美丽的地球发动攻击! 在这千钧一发的时刻,地球联合军决定使用地球最先进的能量武器——由发明家 SHTSC 设计的超能粒子炮彻底摧毁 CCM。

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

f(i) = (a * i + b) mod m + 1

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

然而,出于某种不可告人的目的,N 财团不希望 CCM 被超能粒子炮彻底消灭。

于是 N 财团以远程精神控制了超能粒子炮的操作员——你来阻止地球军消灭 CCM。

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

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

#include<cstdio> typedef long long ll; int n,m,lim,a,b,i,j,cnt;ll ans; struct E{int s,l;}e[3000]; int pow(int a,int b){int t=1;for(;b;b>>=1,a=1LL*a*a%m)if(b&1)t=1LL*t*a%m;return t;} void add(int s,int l){ if(lim){ if(s>lim)return; if(!s){ s+=a,l--; if(s>lim||l<0)return; } int t=(lim-s)/a; if(l>t)l=t; } e[++cnt].s=s;e[cnt].l=l; } inline ll cal(const E&A,const E&B){ int L=(B.s-A.s)/a; if(L<0)L=0; while(1LL*a*L+A.s<=B.s)L++; if(L>A.l)return 0; int F=(a*L+A.s-B.s)/a; while(1LL*a*(F+1)+B.s<a*L+A.s)F++; if(F>B.l)F=B.l; F++; int R=(a*B.l+B.s-A.s)/a; if(R<0)R=0; while(1LL*a*R+A.s<=a*B.l+B.s)R++; if(R>A.l)R=A.l; int G=(a*R+A.s-B.s)/a; while(1LL*a*(G+1)+B.s<a*R+A.s)G++; if(G>B.l)G=B.l; G++; return 1LL*(F+G)*(R-L+1)/2+1LL*G*(A.l-R); } int main(){ scanf("%d%d%d%d",&n,&m,&a,&b); if(a>1000)a=pow(a,m-2),b=1LL*(m-b)*a%m,lim=n,n=m-1; if(lim)add(b,0); while(n){ b=(b+a)%m; i=(m-b-1)/a; while(1LL*a*(i+1)+b<m)i++; if(i>=n)i=n-1; add(b,i); n-=i+1; b=(1LL*a*i+b)%m; } for(i=1;i<=cnt;i++)for(j=i+1;j<=cnt;j++)ans+=cal(e[i],e[j]); return printf("%lld",ans),0; }

详情