hdu6038

分析

求函数 \(f\) 的构成方案，\(f\) 确定下来后，\(f\) 和 \(b\) 的值也是一一对应的了（ \(f(i)=b_{f(a_i)}\) ），观察 \(a\) 数组，代入 \(f\) 函数，存在循环节，比如 \(a[0] = 1, a[1] = 0\)，那么循环节长度为 2，代入后，\(f(0)=b_{f(1)}, f(1)=b_{f(0)}\)，也能形成类似的循环节，正好是前面循环节的长度（后面我们直接去考虑对应 \(a\) 数组的循环节就好了）。观察 \(b\) 数组，同样会存在一些循环节，如果 \(b\) 数组中有一个长度为 \(1\) 的和一个长度为 \(2\) 的循环节， \(a\) 数组中有一个长度为 \(2\) 的循环节，那么显然给 \(a\) 数组这个长度为 \(2\) 的循环节分别提供一种和两种方案（因为是循环，可以看做是一个环，那么可以调整所有数的位置，保持每个数的相对位置不变，所以长度 \(2\) 的能提供两种）。所有在 \(b\) 数组的循环节且长度是 \(a\) 中的某个循环节长度的因子，都能增加 \(a\) 中这个循环节的方案数，最后将 \(a\) 中所有循环节的方案数相乘即可。（把样例画画找下规律......）

code

#include<cstdio>

#include<cstring>

#include<queue>

#include<cmath>

#include<vector>

#include<algorithm>

#include<iostream>

typedef long long ll;

const ll MAXN = 1e5 + 10;

const ll INF = 1e8;

const ll MOD = 1e9 + 7;

using namespace std;

int kase = 1;

int a[MAXN], b[MAXN];

int vis[MAXN];

int loop_b[MAXN];

int loop_a[MAXN];

int main() {

    int n, m;

    while(~scanf("%d%d", &n, &m)) {

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

            scanf("%d", &a[i]);

        }

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

            scanf("%d", &b[i]);

        }

        memset(vis, 0, sizeof vis);

        memset(loop_b, 0, sizeof loop_b);

        memset(loop_a, 0, sizeof loop_a);

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

            if(!vis[i]) {

                int x = b[i];

                int cnt = 0;

                while(!vis[x]) {

                    cnt++;

                    vis[x] = 1;

                    x = b[x];

                }

                loop_b[cnt]++;

            }

        }

        memset(vis, 0, sizeof vis);

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

            if(!vis[i]) {

                int x = a[i];

                int cnt = 0;

                while(!vis[x]) {

                    cnt++;

                    vis[x] = 1;

                    x = a[x];

                }

                loop_a[cnt]++;

            }

        }

        ll ans = 1;

        for(int i = 1; i <= n; i++) {

            ll res = 0;

            for(int j = 1; j * j <= i; j++) { // 这里可以预处理一波

                if(i % j == 0) {

                    int k = j;

                    res += loop_b[j] * j;

                    if(j * j != i) {

                        k = i / j;

                        res += loop_b[k] * k;

                    }

                }

            }

            int C = loop_a[i];

            while(C--) {

                ans = (ans * res) % MOD;

            }

        }

        printf("Case #%d: %lld\n", kase++, ans);

    }

    return 0;

}

巴特西

hdu6038

hdu6038

分析

code

最新文章

热门文章