思路:首先每个蚂蚁移速相同,而且碰到就转头,这其实等价于擦肩而过!
看到2n个数互不相同就觉得方便多了:枚举每个数字往左或者往右作为最慢,然后考虑其他蚂蚁有多少种走路方向。
(1),走的距离大于m/2
假如红色描述的是一个蚂蚁的移动轨迹,那么蓝色部分左边的蚂蚁只能向左走,蓝色右边的蚂蚁只能向右走。
而蓝色部分中的蚂蚁可以向左也可以向右,方案数为2^n,n为蓝色部分蚂蚁数量。
(2),走的距离小于m/2
如图,则蓝色部分左边的蚂蚁只能向左,蓝色部分右边的蚂蚁只能向右。而蓝色部分中间不能有蚂蚁!,这个方案数只能为1
(一开始很2B,打了nlogn的二分找位置,考完试才发现只有60分,其实应该利用A,B数组的单调性O(N)做的。
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=,Mod=1e9+,p=;
int n,ans,bin[maxn+],x,a,b,c;
ll m,A[maxn+],B[maxn+],C[maxn+];
inline int myrand(){
x=(1ll*a*x+b)%c;
return x;
}
inline void Init(){
cin>>n>>x>>a>>b>>c;
for(int i=;i<=(n+)/;i++)B[i]=B[i-]+myrand()+;
m=B[(n+)/]<<|;
for(int i=;i<=n-(n+)/;i++)C[i]=m-(myrand()%(B[i]-B[i-]-)+B[i-]+);
reverse(C+,C+(n-(n+)/)+);
for(int i=;i<=(n+)/;i++)A[i]=B[i];
for(int i=;i<=n-(n+)/;i++)A[i+(n+)/]=C[i];
for(int i=;i<=n;i++) B[i]=m-A[i];
}
void updata(int i,int j){
if (i-j>=) ans=(ans+(std::max(A[i],B[j])%Mod)*bin[i-j]%Mod)%Mod;
if (j==i+) ans=(ans+std::max(A[i],B[j]))%Mod;
}
void solve(){
bin[]=;for (int i=;i<=n;i++) bin[i]=(bin[i-]*)%Mod;
int i=,j=n;
while (i<n||j>){
if (i<n){
if (j==||A[i+]<B[j-]) i++;
else j--;
}else j--;
updata(i,j);
}
printf("%d\n",ans);
}
int main(){
Init();
solve();
}