Description

windy 学会了一种游戏. 对于 \(1\) 到 \(n\) 这 \(n\) 个数字, 都有唯一且不同的 1 到 \(n\) 的数 字与之对应. 最开始 windy 把数字按顺序 \(1, 2, 3, \ldots, n\) 写一排在纸上. 然后再在 这一排下面写上它们对应的数字. 然后又在新的一排下面写上它们对应的数字. 如此反复, 直到序列再次变为 \(1, 2, 3, \ldots n\).

如:\(1, 2, 3, 4, 5, 6\) 对应的关系为:\(1 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 1, 4 \rightarrow 5, 5 \rightarrow 4, 6 \rightarrow 6\)

windy 的操作如下:

1 2 3 4 5 6
2 3 1 5 4 6
3 1 2 4 5 6
1 2 3 5 4 6
2 3 1 4 5 6
3 1 2 5 4 6
1 2 3 4 5 6

这时, 我们就有若干排 \(1\) 到 \(n\) 的排列, 上例中有 \(7\) 排. 现在 windy 想知道, 对于 所有可能的对应关系, 有多少种可能的排数.

Input

包含一个整数 \(n\).

Output

包含一个整数, 可能的排数.

Sample Input

10

Sample Output

16

Data Range

对于所有的数据, 满足 \(1 \leq n \leq 1000\).

Explanation

首先把一个映射看成一条边, 然后发现整个图一定不是一条链, 也不是一个仙人掌图, 抑或 是一个仙人掌图的集合, 也不是一个森林, 只能是一堆环 (具体证明参见黄学长博客:)

这道题可以转换一下.

试想每一个对应关系 \(a - b\) 为从 \(a \rightarrow b\) 的一条边,

那么图中一定存在 n 条边且每个点入度出度都为 1,

易证一定存在一个或几个环.

然后整个图需要转换的次数就是所有环的长度之最小公倍数.

原题就转化成为了求和为 \(n\) 的数的集合的最小公倍数有多少种.

简单动归一下就可以了.

顺带说一下, 最开始看错题了, 以为是给定一个序列求需要多少次变换回到原来的状态, 然后以为是一道水题就开开心心地写完了, 结果输入样例的时候发现写错了 QAQ...... 不过 下面这个代码大概是对的:


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 2010;

int n, to[maxn];
int belong[maxn], bcnt;
int l_size[maxn]; // Loop size

int gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}

int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}

void dfs(int p, int loop_root, int depth)
{
    if (to[p] == loop_root) {
        l_size[++bcnt] = depth + 1;
        belong[p] = bcnt;
        return ;
    }
    dfs(to[p], loop_root, depth + 1);
    belong[p] = belong[to[p]];
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &to[i]);
    // Deep first search the cycles
    for (int i = 1; i <= n; i++)
        if (!belong[i])
            dfs(i, i, 0);
    int res = 1;
    for (int i = 1; i <= bcnt; i++)
        res = lcm(res, l_size[i]);
    printf("%d\n", res);
    return 0;
}

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 1010;

int n, primes, prime[maxn];
lli dp[maxn][maxn];

bool not_prime[maxn];
void proc_primes(void)
{
    for (int i = 2; i <= 1000; i++) {
        if (!not_prime[i])
            prime[++primes] = i;
        for (int j = 1; j <= primes && i * prime[j] <= 1000; j++) {
            not_prime[i * prime[j]] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    proc_primes();
    // Dynamic programming procedures:
    dp[0][0] = 1;
    for (int i = 1; i <= primes; i++) {
        // Copy from last state
        for (int j = 0; j <= n; j++)
            dp[i][j] = dp[i - 1][j];
        for (int j = prime[i]; j <= n; j *= prime[i])
            for (int k = 0; k <= n - j; k++)
                dp[i][k + j] += dp[i - 1][k];
    }
    lli res = 0;
    for (int i = 0; i <= n; i++)
        res += dp[primes][i];
    printf("%lld\n", res);
    return 0;
}