F - Function

先找到数组A中的循环节，再找到数组B中的循环节，如果B中的循环节是A中循环节的循环因子，说明可以配对，结果累积起来。

#include<bits/stdc++.h>

using namespace std;

const int MAXN=1e6+10;

const int MOD=1e9+7;

#define LL long long

LL a[MAXN],b[MAXN];

LL num1[MAXN],num2[MAXN];

int main()

{

    LL n,m;

    LL ca=1;

    while(scanf("%lld%lld",&n,&m)==2)

    {

        memset(num1,0,sizeof(num1));

        memset(num2,0,sizeof(num2));

        for(int i=0;i<n;i++)scanf("%lld",&a[i]);

        for(int i=0;i<m;i++)scanf("%lld",&b[i]);

        //首先求a的循环节

        //i===f(a[i])

        //num[i]表示都i个循环节的长度

        LL tot=0;

        for(int i=0;i<n;i++)

        {

            if(a[i]==-1)continue;

            tot++;

            LL ii=i;

            while(a[ii]!=-1)

            {

                num1[tot]++;

                LL t=ii;

                ii=a[ii];

                a[t]=-1;

            }

        }

        //求b的循环节,num2[i]表示长度为i的循环节的数量

        for(int i=0;i<m;i++)

        {

            if(b[i]==-1)continue;

            LL len=0;

            LL ii=i;

            while(b[ii]!=-1)

            {

                len++;

                LL t=ii;

                ii=b[ii];

                b[t]=-1;

            }

            num2[len]++;

        }

        //开始匹配，如果长度相同则匹配成功，累积

        LL sum=1;

        for(int i=1;i<=tot;i++)

        {

            LL cnt =0;

            //cout<<num1[i]<<endl;

            for(int j=1;j<=num1[i];j++)

            {

                if(num1[i]%j==0)

                {

                    cnt=(cnt+num2[j]*j)%MOD;

                    //cout<<cnt<<num1[i]<<endl;

                }

            }

            sum=(sum*cnt)%MOD;

        }

        printf("Case #%lld: %lld\n",ca++,sum%MOD);

    }

    return 0;

}

巴特西

F - Function

最新文章

热门文章