Home » 国际竞赛 » Details

USACO 2020 US Open Contest, Gold Problem 3. Exercise

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月6日下午5:16

USACO 2020 US Open Contest, Gold Problem 3. Exercise

Farmer John has come up with a new morning exercise routine for the cows (again)!

As before, Farmer John's $N$ cows ( $1 \leq N \leq 10^{4}$ ) are standing in a line. The $i$ -th cow from the left has label $i$ for each $1 \leq i \leq N$ . He tells them to repeat the following step until the cows are in the same order as when they started.

Given a permutation $A$ of length $N$ , the cows change their order such that the $i$ -th cow from the left before the change is $A_{i}$ -th from the left after the change.

For example, if $A = (1, 2, 3, 4, 5)$ then the cows perform one step. If $A = (2, 3, 1, 5, 4)$ , then the cows perform six steps. The order of the cows from left to right after each step is as follows:

0 steps: $(1, 2, 3, 4, 5)$
1 step: $(3, 1, 2, 5, 4)$
2 steps: $(2, 3, 1, 4, 5)$
3 steps: $(1, 2, 3, 5, 4)$
4 steps: $(3, 1, 2, 4, 5)$
5 steps: $(2, 3, 1, 5, 4)$
6 steps: $(1, 2, 3, 4, 5)$

Find the sum of all positive integers $K$ such that there exists a permutation of length $N$ that requires the cows to take exactly $K$ steps.

As this number may be very large, output the answer modulo $M$ ( $10^{8} \leq M \leq 10^{9} + 7$ , $M$ is prime).

INPUT FORMAT (file exercise.in):

The first line contains $N$ and $M$ .

OUTPUT FORMAT (file exercise.out):

A single integer.

SAMPLE INPUT:

5 1000000007

SAMPLE OUTPUT:

There exist permutations that cause the cows to take $1$ , $2$ , $3$ , $4$ , $5$ , and $6$ steps. Thus, the answer is $1 + 2 + 3 + 4 + 5 + 6 = 21$ .

SCORING:

Test cases 2-5 satisfy $N \leq 10^{2}$ .
Test cases 6-10 satisfy no additional constraints.

Problem credits: Benjamin Qi

USACO 2020 US Open Contest, Gold Problem 3. Exercise 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Call the number of steps that a permutation takes the period of the permutation. Every permutation can be partitioned into cycles of sizes $c_{1}, c_{2}, c_{3}, \dots, c_{k}$ such that $c_{1} + c_{2} + \dots + c_{k} = N$ (see Swapity Swapity Swap from the last contest). Then the period is equal to $lcm (c_{1}, c_{2}, \dots, c_{k})$ .

Suppose that we want find the minimum $n$ such that there exists a permutation of length $n$ with period $K = \prod p_{i}^{e_{i}},$ where the right side denotes the prime factorization of $K$ . It turns out that $n = \sum p_{i}^{e_{i}}$ because

It is never optimal to have $gcd (c_{i}, c_{j}) > 1$ for $i \neq j$ because then we could divide each of $c_{i}, c_{j}$ by an appropriate factor. This would reduce the value of $\sum_{i = 1}^{k} c_{i}$ .
It is never optimal to have $c_{i} = p q$ for $min (p, q) > 1$ and $gcd (p, q) = 1$ because then $p + q < c_{i}$ .

Thus, we need to find the sum of all positive integers $K$ such that $\sum p_{i}^{e_{i}} \leq N$ .

Subtask $N \leq 100$ :

Just searching for all possible $K$ suffices (there are only $18663$ for $N = 100$ ). However, this number grows quite rapidly as $N$ increases.

Full Credit:

Maintain a DP table storing the sum of all possible $K$ for each prime power sum $n$ in $[0, N]$ . Then we can add prime powers in increasing order of $p$ and update the table in $O (N)$ for each of them.

Unfortunately, I was unaware that the sequence could be found on OEIS. I'll try to be more careful about this in the future ...

Mark Chen's code:

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;

const int MAXP = 1234;
const int MAXN = 10005;
 
LL res[MAXP][MAXN];  // result for permutations of length n restricted to using the first p primes
 
int n; LL m;
 
LL mul(LL x, LL y) {
    return (x * y) % m;
}
 
LL add(LL x, LL y) {
    x += y;
    if (x >= m) x -= m;
    return x;
}
 
LL sub(LL x, LL y) {
    x -= y;
    if (x < 0) x += m;
    return x;
}
 
int main() {
    freopen("exercise.in","r",stdin);
    freopen("exercise.out","w",stdout);
    cin >> n >> m;
 
    vector<int> composite(n+1);
    vector<int> primes;
 
    for (int i = 2; i <= n; i++) {
        if (!composite[i]) {
            primes.push_back(i);
            for (int j = 2*i; j <= n; j += i) {
                composite[j] = 1;
            }
        }
    }
 
    if (primes.size() == 0) {
        cout << "1\n";
        return 0;
    }
 
    for (int j = 0; j <= n; j++) res[0][j] = 1;  // identities
 
    for (int i = 1; i <= primes.size(); i++) {
        for (int j = 0; j <= n; j++) {
            res[i][j] = res[i-1][j];
 
            int pp = primes[i-1];
            while (pp <= j) {
                res[i][j] = add(res[i][j], mul(pp, res[i-1][j-pp]));
                pp *= primes[i-1];
            }
        }
    }
 
    cout << res[primes.size()][n] << "\n";
}

[/hide]