BZOJ3565 : [SHOI2014]超能粒子炮

超能粒子炮"/>

BZOJ3565 : [SHOI2014]超能粒子炮

若$a\leq 1000$，则整个$f$数列会形成$O(a)$段公差为$a$的等差数列。

否则$a^{-1}\leq 1000$，设$ai+b=f(i)$，那么有$i=a^{-1}f(i)-ba^{-1}$。

交换$i$和$f(i)$的地位，这将形成$O(a^{-1})$段公差为$a^{-1}$的等差数列。

暴力枚举两个等差数列，然后$O(1)$计算逆序对个数即可。

时间复杂度$O(\min(a,a^{-1})^2)$。

#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;
}