HDU 6038 Function

多校第一场没有怎么想的题，然而实际上是很简单的……就是题意在理解上有点绕。

题意：
给你两个序列a和b，每个序列中的每个元素各不相同，且分别为 [0,num)
要你求满足如下函数的数量。( f ( i ) = b_{ f(a_i) } )

思路：
一般人一眼就可以看出是一个递归的函数过程。
每次当我们知道了 ( f(i) ) ,我们就可以很顺利地得出 ( f(a_i) ) ，知道了 ( f(a_i) ) ,我们就可以很顺利的知道 ( f( a_{a_i} ) )

又因为序列的特性，则对于这个函数，在a序列上必定会存在一个环。
而相应的，在a序列上的一个环与b序列上的元素相对应起来，只有在b序列上存在a序列环的因子才能成立。这个真的只要随便意淫一下就可以了，你要我证明我想还真有点烦

因此只要求出两个序列的环，对于每一对a序列的环与b序列的环，如果b序列环是a序列环的因子，则加上b序列环长度，因为对于a序列上的一个固定点，每一个b序列环上的点都可以对应与a序列固定点，且对应关系必不相同。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

int a[maxn], b[maxn];
bool vis[maxn];
vector<int> xa, xb;

int dfs(int pos, int ary[], int len)
{
    if (vis[pos])
        return len;
    vis[pos] = true;
    return dfs(ary[pos], ary, len + 1);
}

int main()
{
    int n, m, cas = 0;
    while (scanf("%d%d", &n, &m) != EOF) {
        each(i, n) scanf("%d", a + i);
        each(i, m) scanf("%d", b + i);
        fill(vis, false), xa.clear(), xb.clear();
        each(i, n) if (!vis[i]) xa.push_back(dfs(i, a, 0));
        fill(vis, false);
        each(i, m) if (!vis[i]) xb.push_back(dfs(i, b, 0));
        int sa = xa.size(), sb = xb.size();
        ll ans = 1;
        each(i, sa)
        {
            ll tmp = 0;
            each(j, sb) if (xa[i] % xb[j] == 0)(tmp += xb[j]) %= mod;
            ans = (ans * tmp) % mod;
        }
        printf("Case #%d: %lld\n", ++cas, ans);
    }
    return 0;
}