editorial done on request
and as usual, the benq editorial was mathy and didn't explain much
i can't explain this problem succintly, so it's best if you just go read the thing for yourself
this is one of those "wth" problems where you have literally no clue how to do it except for the brutiest of brute forces
but anyways after some malding it's possible for us to figure out that each permutation can be decomposed into a series of "cycles"
take for example this permutation: ```py [1, 3, 2, 5, 4] ``` then we can take cows 4 & 5, put them in their own group, and do the same for cows 1-3
each step, the cows in each group rotate, and it takes `the_size_of_their_group` steps
for the cows to go back to their original position
so the amt of time it takes for this permutation to come together is just
the LCM (least common multiple) of all the group sizes
so this problem can be transformed into the following:
given a number `n`
what's the sum over all distinct values of the LCMs of all partitions of `n`?
one tiny problem
the number of partitions of a `n` increases EXPONENTIALLY as `n` increases
good thing we only have to count the # of distinct LCMs
because after some more malding, it's possible to notice
that there's a specific section of all the partitions that
can represent the entire class of LCMs
idk bout you, but when i think of LCMs i think of prime factors
so how about we think about (the transformed) problem from the perspective
of prime numbers?
so let's set our `n` to a medium number, say, `50`
let's also do a random partition, such as
```py
[36, 9, 7, 1]
```
the LCM of this is \( 36 \cdot 7 = 252 \)
but here's the thing
this partition here, consisting entirely of just prime powers:
```py
[4, 9, 7, 1, 1, (26 more 1's), 1, 1]
```
achieves the same LCM with less space taken up! (the 1's can be considered empty space to a certain degree)
so i have a proposal i'd like to make
no matter WHAT partition we use, there is always going to be a partition consisting only of prime powers and 1's that has the same LCM
not really sure how to prove this, it just comes kinda intuitively tbh
so just trust me on this
i mean you can just transform all partitions into a partition only of prime powers
with the same LCM by just taking the prime factors and putting them in
there's always going to be enough space btw trust me
ok so now we know that we only have to check prime powers
but here's the kicker
that observation was only like 1/3 of the actual problem
we now have to actually implement it
btw this problem is dp if you didn't know, to get this you have to just kinda feel it in your bones or look @ some problem tags
so uh let's let
```
dp[i] = sum of all the LCMs of the partitions whose relevant prime powers sum up to i
```
(for example, [64, 9, 1, 1, 1] would
have its LCM accounted for in `dp[73]`)
of course, we aren't just going to be only using this array- we're going to go through all prime powers and update the array accordingly
now comes the part of actually figuring out the relation
say we were to add a random prime power \( p^x \) to some partition.
how would this affect the LCM given that we know the partition knows
nothing of \( p \) initially?
well, it would just multiply the LCM by \( p^x \)!
so i guess for each prime power, we just go through all the existing elements of `dp`, and then multiply it by said prime power and then go?
hm
yeah that should work, since we know that none of the partitions we've considered
have whatever current prime power we're considering
so yeah that's it, the code follows:
```java import java.io.*; import java.math.BigInteger; import java.util.*; /** * 2020 us open gold * also this is slow mostly bc of the bigintegers * if you want like super speed, just switch to longs and do everything mod the mod idk */ public class Exercise { public static void main(String[] args) throws IOException { StringTokenizer initial = new StringTokenizer( new BufferedReader(new FileReader("exercise.in")).readLine() ); int cowNum = Integer.parseInt(initial.nextToken()); BigInteger mod = new BigInteger(initial.nextToken()); // the sum of all the LCMs of the prime powers that sum to i (the array index) BigInteger[] totalWithSum = new BigInteger[cowNum + 1]; Arrays.fill(totalWithSum, BigInteger.ZERO); totalWithSum[0] = new BigInteger("1"); for (int i = 2; i <= cowNum; i++) { if (!prime(i)) { continue; } /* * keep another array where we store the updates so the prime * powers of a single number don't go harrassing each other */ BigInteger[] updatedTotal = totalWithSum.clone(); for (int p = i; p <= cowNum; p *= i) { // go through all prime powers for (int from = 0; from + p <= cowNum; from++) { updatedTotal[from + p] = updatedTotal[from + p].add( totalWithSum[from].multiply(new BigInteger(String.valueOf(p))) ); } } totalWithSum = updatedTotal; } BigInteger total = BigInteger.ZERO; for (BigInteger prod : totalWithSum) { total = total.add(prod); } total = total.mod(mod); PrintWriter written = new PrintWriter("exercise.out"); written.println(total); written.close(); } // sauce: https://www.geeksforgeeks.org/primality-test-set-1-introduction-and-school-method private static boolean prime(int n) { if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } } ```