首页 > 编程学习 > HDU-6038 Function(思维)

HDU-6038 Function(思维)

发布时间:2022/12/10 17:05:40

传送门:点这里~


首先将A,B序列划分成若干循环节
循环节的定义是:Ax=y,Ay=z,Az=x类似于这样的循环对应关系

为什么要找出A的循环节呢?
首先看样例:f[0]=B[f[A[0]]]=B[f[1]],
            f[1]=B[f[A[1]]]=B[f[0]],
            f[2]=B[f[A[2]]=B[f[2]]
对于这组数据,0和1在一个循环节,2在一个循环节
对于第一个循环节:我们只要确定了f[0]的值,f[1]的值也就确定了,又因为他是一个循环,
因此可以用f[1]的值来验证f[0]的值是否正确

为什么要找出B的循环节呢?
我们先假设[0,2]是一段循环节且A[i]=(i+1)%2 (i∈[0,2])
f[0]=B[f[A[0]]] = B[B[f[ A[A[0]] ]]] = B[B[f[A[1]]]]
                = B[B[B[f[ A[A[2]] ]]]] = B[B[B[f[A[0]]]]]
因此B也需要找出循环节,且循环节A的长度lenA必须是循环节B的长度lenB的倍数,否则B[f[A[0]]]!=B[B[B[f[A[0]]]]]
由于f[0]可以等于循环节B中任何一个值,因此长度为lenB的循环节贡献为lenB

最后枚举序列A的每个循环节,找出B中所有长度为lenA的约数的循环节,并求出长度之和t,ans=ans*t

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
const int MX = 1e5 + 5;
void solve(int a[],int vis[], int n,vector<int>& ver) {for (int i = 0; i < n; i++) {if (vis[i]) continue;int cnt = 1,index=i;vis[i]=1;while (a[index] != i) {index = a[index];vis[index]=1;cnt++;}ver.push_back(cnt);}
}
int a[MX], b[MX], vis1[MX], vis2[MX];
vector<int>ver[2];
int main() {//freopen("in.txt","r",stdin);int n, m, cas = 0;while (~scanf("%d%d", &n, &m)) {for (int i = 0; i < n; i++) scanf("%d", &a[i]), vis1[i] = 0;for (int i = 0; i < m; i++) scanf("%d", &b[i]), vis2[i] = 0;ver[0].clear(); ver[1].clear();solve(a,vis1,n,ver[0]);solve(b,vis2,m,ver[1]);LL ans=1;for(int i=0;i<ver[0].size();i++){LL tmp=0;for(int j=0;j<ver[1].size();j++){if(ver[0][i]%ver[1][j]==0) tmp+=ver[1][j];}ans=(ans*tmp)%mod;}printf("Case #%d: %lld\n",++cas,ans);}return 0;
}



本文链接:https://www.ngui.cc/el/2314424.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000