【题目描述】：

吃饭是自古以来令人头疼的问题，最后天天决定写一个程序来替他做决定。

现在已知有n个餐厅，编号从0到n-1。记ai表示第i天决定吃什么，令

t[i][0]=(A×a[i-1]+B×a[i-2])%n，(其实就是一个随机数)

t[i][j]=(t[i][j-1]+1)%n，j≥1

天天不想去最近吃过的餐厅，所以如果在前n/2(整除)天中吃过某个餐厅，就不想再去这个餐厅。所以我们要找一个最小的k，使得t[i][k]不为前n/2(整除)天去过的餐厅。那么天天第i天就想去t[i][k]餐厅。

现在已知a1和a2，想让你输出a3…am，即接下来m-2天，天天会去哪里吃饭。

【输入描述】：

第一行两个正整数n和m。其中2≤n≤10^5，3≤m≤2×10^5；

第二行两个整数，分别为A和B。其中0≤A,B≤10^9；

第三行两个整数，为a[1]和a[2]。0≤a[1],a[2]＜n，且a[1]≠a[2]；

【输出描述】：

一行m-2个整数，表示接下来m-2天里，天天去哪里吃饭。

【样例输入】：

3 47 112 0

【样例输出】：

1 2

【样例说明】：

t[3][0]=(7×a[2]+11×a[1])%n=1，前面n/2=1天没有出现，所以第三天去1号餐厅。

t[4][0]=1，前面1天已经出现，所以第四天去t[4][1]=2号餐厅。

【时间限制、数据范围及描述】：

时间：1s 空间：256M

对于60% 的数据：2≤n,m≤10^4；

对于100% 的数据：2≤n≤10^5，3≤m≤2×10^5；且保证A,B为随机的两个素数，所以可以认为t[i][0]为一个随机数。

 

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;long long n,m,A,B,a[200610],t,f[200610];long long read(){ long long a=0,b=1; char ch=getchar(); while((ch<48||ch>57)&&ch!='-'){ ch=getchar(); } if(ch=='-'){ b=-1; ch=getchar(); } while(ch<48||ch>57){ ch=getchar(); } while(ch>47&&ch<58){ a=a*10+ch-48; ch=getchar(); } return a*b;}int main(){ n=read();m=read(),A=read();B=read(),a[1]=read(),a[2]=read(); memset(f,0,sizeof(f)); f[a[1]]=1,f[a[2]]=1; for(long long i=3;i<=m;i++){ if(i>n/2){ long long s=i-n/2-1; if(i==3&&s>1)f[a[s-1]]=0; if(s>0)f[a[s]]=0; } t=(a[i-1]*A+a[i-2]*B)%n; while(f[t]==1)t=(t+1)%n; a[i]=t;f[t]=1; } for(long long i=3;i<=m;i++){ printf("%lld ",a[i]); } return 0;}