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

题意:
给你两个序列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;
}
Categories: 思维

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

思维

HDU 5486 Difference of Clustering

这种题目就是专门针对我的…… 思路简单,所需注意细节多。 题意: 给你 Read more…

思维

CodeForces 853 B Jury Meeting

思维题,老实说我并没有想出来,应该说是我想歪了…… 看了一个大佬的代码 Read more…

思维

CodeForces 279C Ladder

比赛的时候又被数学题坑到了…… 最后一场个人赛,并不知道是好是坏,但该 Read more…