時間限制 1s 空間限制 512MB

3.1 題目描述

“Geronimo～”
時間還很多,讓我們慢慢來。
不如聽首開心的歌再看題?…… 算了,直接看題吧。
給定一個整數(shù) n,以及一個 n 階的排列 p 1 , p 2 , …, p n 。
我們定義重組過程如下:如果當(dāng)前的排列是 a 1 , a 2 , …, a n ,經(jīng)過一次重組,就會
變成 p a 1 , p a 2 , …, p a n 。
問一個排列至少要經(jīng)過多少次重組才會恢復(fù)成重組前的狀態(tài)。
由于答案可能很大,輸出其對一個給定的正整數(shù) q 取模的值即可。

3.2 輸入格式

第一行兩個正整數(shù) n, q。
第二行一共 n 個整數(shù),依次表示 p 1 , p 2 , …, p n 。
同一行相鄰的數(shù)間用一個空格隔開。

3.3 輸出格式

一行一個整數(shù),表示答案對 q 取模的值。

3.4 樣例輸入

7 1000000207
2651347

3.5 樣例輸出

4

3.6 數(shù)據(jù)規(guī)模和約定

對于全部的數(shù)據(jù),q ≤ 2 × 10 9
對于 10% 的數(shù)據(jù),q = 1
對于另外 20% 的數(shù)據(jù),n ≤ 9
6對于另外 40% 的數(shù)據(jù),n ≤ 10 3
對于剩下 30% 的數(shù)據(jù),n ≤ 5 × 10 5

【題解】

這道題就是找出每個點恢復(fù)初始狀態(tài)的步數(shù)（或者稱為找個環(huán)），再求出這些步數(shù)的最大公約數(shù)即可。
（然而我考試時打了個愚蠢的10分暴力）
但注意有幾點優(yōu)化：
1、一個環(huán)上所有點恢復(fù)初始狀態(tài)的步數(shù)相同（解決TLE問題）
2、求一群數(shù)的最大公約數(shù)，可以一一找出每一對數(shù)，求出兩個數(shù)的最大公約數(shù)，再用后一個數(shù)除掉（用前一個數(shù)的話就是改掉當(dāng)前搜索的數(shù)，會wa7個點），最后把剩下的數(shù)連乘即可。（另一種思路是線性篩打表出素數(shù)，看每個數(shù)的質(zhì)因子）
3、恢復(fù)初始狀態(tài)的步數(shù)相同的點的步數(shù)可去重，這里我用的是map（和vis一樣）。

#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<vector> #include<map> #define ll long long #define re register #define il inline #define fp(i,a,b) for(re ll i=a;i<=b;i++) #define fq(i,a,b) for(re ll i=a;i>=b;i--) using namespace std; ll a[500005]={},c[500005]={},total=0; bool vis[500005]={}; map<ll,ll>b; il ll gi() { re ll x=0;re ll t=1;re char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();if(ch=='-') t=-1,ch=getchar();while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*t; } ll gcd(ll x,ll y) {if(y==0) return x;return gcd(y,x%y); } int main() {freopen("geronimo.in","r",stdin);freopen("geronimo.out","w",stdout);ll n=gi(),q=gi();if(q==1) {printf("0\n");return 0;}fp(i,1,n)a[i]=gi();fp(i,1,n)if(vis[i]==0){ll j=a[i],sum=1;while(j!=i) sum++,j=a[j];j=a[i];while(j!=i) vis[j]=1,j=a[j];if(b[sum]==0) b[sum]=1,c[++total]=sum;}fp(i,1,total-1)fp(j,i+1,total){ll x=c[i],y=c[j];if(x<y) swap(x,y);ll r=gcd(x,y);c[j]/=r;//beach,c[i]/=i會wa7個點，因為不能改當(dāng)前數(shù)}ll ans=1;fp(i,1,total)ans=(1ll*ans*c[i])%q;printf("%lld\n",ans);fclose(stdin);fclose(stdout);return 0; }

總結(jié)

以上是生活随笔為你收集整理的geronimo的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。