链接  http://acm.hdu.edu.cn/showproblem.php?pid=6038

题意: 
给你一个a序列,代表0到n-1的排列;一个b序列代表0到m-1的排列。问你可以找出多少种函数关系f,f的定义域内的i都满足f(i)=b[f(a[i])]; 
分析:这个主要是找循环节 循环节导致函数有多种情况 找到每段循环节的 取值 种数 相乘起来就是答案
比如说:如果 a 序列是 2 0 1 那么我们可以发现

对于这组数来说,假如我们先指定了f(0)对应的在b中的值,那么根据第2个式子,就可以得出f(1),根据f(1)就又可以得出f(2),最后根据f(2)就可以检验f(0)的值是否正确。

仔细观察左边的柿子 (定义域)i与a[ i ] 是循环的 如果想使上述成立,必须右边的柿子(值域)i与b[ i ] 也存在其约数长度的循环节。

如果不是约数长度的循环节会使上述假设矛盾    自己写一下就知道了 只有被整出才会成立。

每个定义域的循环节都可以与每个值域的循环节匹配(满足红字匹配成功)

那么就是找两个序列的不相交的循环节,对于定义域里面的每一个循环节都找出来有多少种情况。每一个循环节的情况数为它所能匹配的值域循环节的长度 和。每个循环节的情况数乘起来就是答案了

样例一  (1+1)*(1+1)=4; a两个环(长度 2 1)           b两个个环(长度 1 1)       2与1 1匹配   1与1 1 匹配

样例二  (1+3)=4;           a一个环(长度 3)                b两个环(长度 1 3)         3与1 3匹配

注   对于一个a循环节  若b循环节中没有能与之匹配的   答案为零   想想为什么  不用特判累积过程中可以处理掉

AC代码

 #include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
using namespace std;
const int maxn= 1e5+;
const int mod= 1e9+;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int n,m;
int a[maxn],b[maxn];
int vis[maxn],loop_a[maxn],loop_b[maxn]; //loop存循环节长度
int main()
{
int kase=;
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i=; i<n; i++)
scanf("%d",&a[i]);
for(int i=; i<m; i++)
scanf("%d",&b[i]);
memset(vis, , sizeof(vis));      //标记是否访问过 找不相交的循环节
memset(loop_b, , sizeof(loop_b));
memset(loop_a, , sizeof(loop_a));
int cnt1=,cnt2=; //cnt记录循环节个数
for(int i = ; i < n; i++)
{
if(!vis[i]) //过程自己模拟一下就明了了
{
int x = a[i];
int len = ;
while(!vis[x])
{
len++;
vis[x] = ;
x = a[x];
}
if(len!=)
loop_a[cnt1++]=len; //保存循环节
}
}
memset(vis, , sizeof vis);
for(int i = ; i < m; i++) //b同理
{
if(!vis[i])
{
int x = b[i];
int len = ;
while(!vis[x])
{
len++;
vis[x] = ;
x = b[x];
}
if(len!=)
loop_b[cnt2++]=len;
}
}
ll ans=;
for(int i=; i<cnt1; i++) //枚举a与b的循环节 试了不会超时 还有更快一些的做法
{
ll sum=;                //记录每个循环节的情况数
for(int j=; j<cnt2; j++)
{
if(loop_a[i]%loop_b[j]==)    //只有是约数才能匹配
{
sum=(sum+loop_b[j])%mod; //加进去 取模
}
}
ans=(ans*sum)%mod; //乘到答案里面
}
printf("Case #%d: %lld\n",++kase,ans);
}
return ;
}

作者水平有限 欢迎大佬纠错!

多校真jb难啊~~~~~QAQ

太菜了

05-11 11:31