标签：链表+数论知识。

题解：

　　对于这道题，其实就是两个问题的拼凑，我们分开来看。
　　首先要求xi与yi。这个可以发现，x每增加1，则pos增加d；y每增加1，则pos增加1。然后，我们把x与y分别写在二维平面上，比如样例：
x= 0 1
y=0 {0 4}
y=1 {1 5}
y=2 {2 6}
y=3 {3 7}
　　发现行数=gcd(n,d)，列数=n/gcd(n,d)。
　　那么题目要求y尽量小，然后x尽量小。我们先求y，那么初始pos就是ci，把ci放入这张表，寻找最近的可以不重复的行，也就是y。找到之后我们再把ci+y代入，去找在第y行的哪一个数是最近的，这样就能找到x与y了。
　　具体的：我们使用rx[i]，代表x=i时，右边那个可用的是哪一个，rx_cnt[i]代表距离。同样ry[i]，与ry_cnt[i]分别表示y=i的下面的哪一个与距离。每次修改（也就是标记Val已经被使用）仅仅需要对于(Val+d)%n即可，然后rx[Val]=(Val+d)%n，rx_cnt[Val]=1。将Val%=gcd，即可完成对于y的修改。
　　修改那么简单，那么查询：类似并查集一样的进行路径压缩，即如果rx[Val]被使用，那么rx[Val]=find(rx[Val])，对应修改rx_cnt[Val]即可，然后返回rx_cnt[Val]为x的值，y同样如此。
　　解决了这个问题，下面求解最小步数就很简单了。我们在纸上将i与pos[i]连上一条边，发现会构成很多个环，如果这个环中有0，那么直接把0按照环的反方向依次移动，即可把整个环都归位，如果环中没有0，那么先把0移进去，归位之后再移出来，步数+2即可，这样是最优的方案。证明可以使用置换群什么的。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int MAXN=;

 bool vis[MAXN];

 int T,n,s,q,p,m,d,ans;

 int c[MAXN],pos[MAXN],cnt[MAXN],rx[MAXN],ry[MAXN],rx_cnt[MAXN],ry_cnt[MAXN];

 inline int gi(){int res; scanf("%d",&res); return res;}

 int gcd(int A,int B)

 {

   if(A%B==)return B;

   return gcd(B,A%B);

 }

 void insert(int x)

 {

   int tmp;

   if((tmp=x+d)>=n)tmp-=n;

   rx[x]=tmp;

   rx_cnt[x]=;

   x%=m;

   if(--cnt[x])return;

   if((tmp=x+)>=m)tmp-=m;

   ry[x]=tmp;

   ry_cnt[x]=;

 }

 int query(int *r,int *r_cnt,int x)

 {

   if(r[x]==x)return ;

   r_cnt[x]=r_cnt[x] + query(r,r_cnt,r[x]);

   r[x]=r[r[x]];

   return r_cnt[x];

 }

 int main()

 {

   T=gi();

   while(T--)

     {

       scanf("%d%d%d%d%d%d",&n,&s,&q,&p,&m,&d); pos[]=s;

       for(int i=;i<n;i++) c[i]=((LL)c[i-]*q+p)%m;

       d%=n;//insert()中没有使用取模，而是使用减法代替，所以这里先模一下。

       m=gcd(n,d);

       for(int i=;i<m;i++)

         {

           cnt[i]=n/m;

           ry[i]=i;

           ry_cnt[i]=;

         }

       for(int i=;i<n;i++) rx[i]=i,rx_cnt[i]=;

       insert(pos[]);

       for(int i=;i<n;i++)

         {

           int y=query(ry,ry_cnt,c[i]%m);

           int x=query(rx,rx_cnt,(c[i]+y)%n);

           pos[i]=((LL)d*x+y+c[i])%n;

           insert(pos[i]);

         }

       ans=; memset(vis,,sizeof vis);

       for(int i=;i<n;i++)

         if(!vis[i])

           {

             int now=i,Start=i,flag=,cnt=;

             do

               {

                 vis[now]=; cnt++;

                 if(now==)flag=;

                 now=pos[now];

               }while(now!=Start);

             if(cnt>)

               {

                 ans+=cnt-;

                 if(!flag)ans+=;

               }

           }

       printf("%d\n",ans);

     }

     return ;

 }

巴特西

[HNOI2010] 物品调度 fsk

题解：

最新文章

热门文章