【Link】:http://codeforces.com/contest/834/problem/C
【Description】
給你兩個排列a和b;
a排列的長度為n,b排列的長度為m;
a∈[0..n-1],b∈[0..m-1];
然后讓你求一個函數f[i];
f[i]的定義域為0..n-1,值域為0..m-1
同時使得對于任意f[i],i∈[0..n-1];
f(i)=bf(a[i])成立;
【Solution】
原始可以遞推一下;
f(i)=bf(ai)=bbf(aai)
則可以一直寫下去f[i]=bbbbbf(aaaaa[i]);
注意到a是一個排列;
最后肯定能形成一個環,則aaaaa..a[i]肯定又能變回i
則
f(i)=b?bf(i)l?times?b
（這里L是第一次回到i的L);
這里的含義其實就相當于f[i]是一個x
要使得
x=b....bx
而b也是一個排列;
則也肯定有循環節;
這里從x開始的b數組的循環節長度一定得是上面的a的循環節的長度L的因子;
不然就不能在L次b之后回到x了;
于是,
在a數組里找循環節的長度,在b數組中也找循環節的長度;
看看有多少個長度在a中有,且b數組中,有它的因子長度的循環節;
直接累加因子循環節長度到temp中;
然后累乘所有temp即可;
根據上面的形式,每個a循環節中的某一個位置,f只要確定了,其他該循環節中的f值也就確定了,然后那個位置有temp種選擇;就是因子循環節中任意一個b[i]都可以;
找因子的時候,需要做些優化;
不然可能退成O(n2)的復雜度;
先枚舉a數組有哪些循環節,長度為i;
然后用O(i12)復雜度枚舉它可能的因子,(j是則n/j也是)
看看在b中有沒有這樣長度的;
【NumberOf WA】
0
【Reviw】
求因子的思想很好.
【Code】
#include <bits/stdc++.h>
using namespace std;
#define int long longconst int N = 1e5;
const int MOD = 1e9+7;int n,m;
int a[N+10],b[N+10],cnta[N+10],cntb[N+10];
bool flag[N+10];main(){int kk = 0;while (~scanf("%lld%lld",&n,&m)){for (int i = 1;i <= n;i++){scanf("%lld",&a[i]);a[i]++;}for (int i = 1;i <= m;i++){scanf("%lld",&b[i]);b[i]++;}memset(cnta,0,sizeof cnta);memset(cntb,0,sizeof cntb);memset(flag,0,sizeof flag);for (int i = 1;i <= m;i++)if (!flag[i]){int x = i,num = 0;while (!flag[x]){flag[x] = 1;num++;x = b[x];}cntb[num]++;}memset(flag,0,sizeof flag);for (int i = 1;i <= n;i++)if (!flag[i]){int x = i,num = 0;while (!flag[x]){flag[x] = 1;num++;x = a[x];}cnta[num]++;}int ans = 1;for (int i = 1;i <= n;i++)if (cnta[i]>0){int temp = 0;for (int j = 1;j*j <= i;j++)if (i%j==0){temp = (temp + j*cntb[j])%MOD;if (j != i/j)temp = (temp + (i/j)*cntb[i/j])%MOD;}while (cnta[i]--){ans = (ans*temp)%MOD;}}printf("Case #%lld: %lld\n",++kk,ans);}return 0;
}
)
)
