Contest Results

Call the number of steps that a permutation requires the period of the permutation. Every permutation can be partitioned into cycles of sizes

c_{1}, c_{2}, c_{3}, \dots, c_{k}

$c_1,c_2,c_3,\ldots,c_k$ such that

c_{1} + c_{2} + \dots + c_{k} = N

$c_1+c_2+\ldots+c_k=N$ . Then the period is equal to

lcm (c_{1}, c_{2}, \dots, c_{k})

$\text{lcm}(c_1,c_2,\ldots,c_k)$ .

Maintain the number of possible permutations for each possible LCM of a permutation with

n

$n$ elements for each

1 \leq n \leq N

$1\le n\le N$ . This number is quite small for

N = 50

$N=50$ (it ends up being 1056) but grows quite rapidly. The number of permutations for a single LCM should be stored

(\mod M - 1)

$\pmod{M-1}$ because

a^{M - 1} \equiv 1 (\mod M)

$a^{M-1}\equiv 1\pmod{M}$ for all

0 < a < M

$0<a<M$ (Fermat's Little Theorem).

So we can essentially solve the problem independently for each distinct prime power

D

$D$ . Doing this in

O (N^{2})

$O(N^2)$ for a single prime power is sufficient for this subtask.

If we can count the number of ways to create a permutation of length

n

$n$ for each

n \in [1, N]

$n\in [1,N]$ such that no cycle length is divisible by

D

$D$ in

O (\frac{N^{2}}{D})

$O\left(\frac{N^2}{D}\right)$ time, then the solution runs in

O (N^{2} \cdot \sum_{D = 1}^{N} \frac{1}{D}) = O (N^{2} \log N)

$O\left(N^2\cdot \sum_{D=1}^N\frac{1}{D}\right)=O\left(N^2\log N\right)$ time.

The high bound on

N

$N$ (hopefully) ensures that the above solution does not receive full credit. How can we do better?

Note that if

2 D > N

$2D>N$ then we can compute the number of permutations containing a cycle with length divisible by

D

$D$ in

O (1)

$O(1)$ time (assuming that we have precomputed some quantities in

O (N^{2})

$O(N^2)$ ). This is true because if there is a cycle with length divisible by

p^{k}

$p^k$ , then there must be exactly one cycle with length equal to

p^{k}

$p^k$ (and the rest can have arbitrary lengths).

Let's try to generalize. Define

D = p^{k}

$D=p^k$ . Any permutation has between

0

$0$ and

⌊ \frac{N}{D} ⌋

$\left\lfloor\frac{N}{D}\right\rfloor$ cycles with length divisible by

D

$D$ . So it suffices to count each of the following quantities for each

k \in [0, ⌊ \frac{N}{D} ⌋]

$k\in \left[0,\left\lfloor\frac{N}{D}\right\rfloor\right]$ .

#include <bits/stdc++.h> using namespace std; typedef long long LL; int n; LL m; typedef unsigned long long ull; typedef __uint128_t L; struct FastMod { ull b, m; FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {} ull reduce(ull a) { ull q = (ull)((L(m) * a) >> 64); ull r = a - q * b; // can be proven that 0 <= r < 2*b return r >= b ? r - b : r; } }; FastMod f(2); LL mul(LL x, LL y) { return f.reduce(x * y); } 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; } LL powmod(LL a, LL b) {LL res=1; a %= (m+1); for(;b;b>>=1) {if (b&1) res = res*a % (m+1); a = a*a % (m+1);} return res;} const int MAXN = 7505; LL factorial[MAXN], c[MAXN][MAXN]; int main() { freopen("exercise.in","r",stdin); freopen("exercise.out","w",stdout); cin >> n >> m; m--; f = FastMod(m); factorial[0] = 1; for (int i = 1; i < MAXN; ++i) factorial[i] = mul(factorial[i-1], i); c[1][0] = c[1][1] = 1; for (int i = 2; i < MAXN; i++) { c[i][0] = c[i][i] = 1; for (int j = 1; j < i; j++) c[i][j] = add(c[i-1][j-1], c[i-1][j]); } vector<int> composite(MAXN); LL ans = 1; for (int i = 2; i <= n; i++) { if (!composite[i]) { for (int j = i; j <= n; j *= i) { // count permutations of length j*k where ALL cycles are divisible by j vector<LL> aj(n/j+1); aj[0] = 1; for (int k = 1; k < n/j+1; k++) { for (int l = 1; l <= k; l++) { aj[k] = add(aj[k], mul(mul(c[j*k-1][j*l-1], factorial[j*l-1]), aj[k-l])); } } // count permutations of length n-j*k where NO cycle is divisible by j vector<LL> nj(n/j+1); for (int k = n/j; k >= 0; k--) { nj[k] = factorial[n-j*k]; for (int l = k+1; l <= n/j; l++) { nj[k] = sub(nj[k], mul(c[n-j*k][n-l*j], mul(aj[l-k], nj[l]))); } } ans = (ans * powmod(i, sub(factorial[n], nj[0]))) % (m+1); } for (int j = 2*i; j <= n; j += i) { composite[j] = 1; } } } printf("%lld\n", ans); }

#include <bits/stdc++.h> using namespace std; void setIO(string s) { ios_base::sync_with_stdio(0); cin.tie(0); freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } typedef long long ll; const int MX = 7501; typedef unsigned long long ul; typedef __uint128_t L; struct ModFast { ul b, m; ModFast(ul b) : b(b), m(ul((L(1)<<64)/b)) {} ul reduce(ul a) { ul q = (ul)((L(m)*a)>>64), r = a-q*b; return r>=b?r-b:r; } }; ModFast MF(1); int M,MOD,n; int ad(int a, int b) { a += b; if (a >= M) a -= M; return a; } int sub(int a, int b) { a -= b; if (a < 0) a += M; return a; } int mul(int a, int b) { return MF.reduce((ul)a*b); } int choose[MX][MX]; int with(int z) { // # of permutations with z dividing some cycle length int res = 0; vector<int> dp(n/z+1); dp[0] = sub(0,1); for (int i = 1; i <= n/z; ++i) for (int j = 1; j <= i; ++j) dp[i] = sub(dp[i],mul(choose[i*z-1][j*z-1],dp[i-j])); for (int i = 1; i <= n/z; ++i) res = ad(res,mul(choose[n][n-i*z],dp[i])); return res; } ll mpow(ll a, ll b) { return !b?1:mpow(a*a%MOD,b/2)*(b&1?a:1)%MOD; } int main() { setIO("exercise"); cin >> n >> MOD; M = MOD-1; MF = ModFast(M); for (int i = 0; i <= n; ++i) { choose[i][0] = 1; for (int j = 0; j < i; ++j) choose[i][j+1] = mul(choose[i][j],i-j); } vector<bool> comp(n+1); ll ans = 1; for (int i = 2; i <= n; ++i) if (!comp[i]) { for (int j = 2*i; j <= n; j += i) comp[j] = 1; for (int j = i; j <= n; j *= i) ans = ans*mpow(i,with(j))%MOD; } cout << ans << "\n"; }

It is possible to solve this problem more quickly if you are familiar with exponential generating functions (EGF). This comment gives an explicit formula, which I'll try to explain here. From KACTL, we have the following fact. Let

g_{S} (n)

$g_S(n)$ be the number of

n

$n$ -permutations whose cycle lengths all belong to the set

S

$S$ . Letting

S (x) = \sum_{n \in S} \frac{x^{n}}{n}

$S(x)=\sum_{n\in S}\frac{x^n}{n}$ , it follows that

\sum_{n = 0} g_{S} (n) \frac{x^{n}}{n!} = \exp (S (x)) = \sum_{k = 0}^{\infty} \frac{S (x)^{k}}{k!} .

$\sum_{n=0}g_S(n)\frac{x^n}{n!}=\exp(S(x))=\sum_{k=0}^{\infty}\frac{S(x)^k}{k!}.$

S (x) = \sum_{n = 1}^{\infty} \frac{x^{n}}{n} = - \ln (1 - x)

$S(x)=\sum_{n=1}^{\infty}\frac{x^n}{n}=-\ln(1-x)$

\exp (S (x)) = \frac{1}{1 - x} = 1 + x + x^{2} + \dots,

$\exp(S(x))=\frac{1}{1-x}=1+x+x^2+\cdots,$

S (x) = - \ln (1 - x) - \frac{1}{z} \cdot \sum_{k = 1}^{\infty} \frac{x^{z k}}{k} = - \ln (1 - x) + \frac{1}{z} \cdot \ln (1 - x^{z}) .

$S(x)=-\ln(1-x)-\frac{1}{z}\cdot \sum_{k=1}^{\infty}\frac{x^{zk}}{k}=-\ln(1-x)+\frac{1}{z}\cdot \ln(1-x^z).$

\exp (S (x)) = \frac{(1 - x^{z})^{1 / z}}{1 - x} .

$\exp(S(x))=\frac{(1-x^z)^{1/z}}{1-x}.$

[x^{n}] \frac{(1 - x^{z})^{1 / z}}{1 - x} = [x^{z d}] \frac{(1 - x^{z})^{1 / z}}{1 - x^{z}} = [x^{z d}] (1 - x^{z})^{1 / z - 1} .

$[x^n]\frac{(1-x^z)^{1/z}}{1-x}=[x^{zd}]\frac{(1-x^z)^{1/z}}{1-x^z}=[x^{zd}](1-x^z)^{1/z-1}.$

g_{S} (n) = n! \cdot (- 1)^{d} (\binom{1 / z - 1}{d}) = \frac{n!}{d!} \prod_{i = 1}^{d} (i - 1 / z) = \frac{n!}{d! z^{d}} \cdot \prod_{i = 1}^{d} (z i - 1) .

$g_S(n)=n!\cdot (-1)^d\binom{1/z-1}{d}=\frac{n!}{d!}\prod_{i=1}^d(i-1/z)=\frac{n!}{d!z^d}\cdot \prod_{i=1}^d(zi-1).$

int without(int z) { int res = 1; for (int i = 1; i <= n; ++i) { if (i%z != 0) res = mul(res,i); else res = mul(res,i-1); } return res; } int with(int z) { // # of permutations with z dividing some cycle length return sub(choose[n][n],without(z)); }

although this isn't actually faster. Please let me know if there's a simpler explanation for this formula.

To solve this problem in

\tilde{O} (n)

$\tilde{\mathcal{O}}(n)$ time, we can must compute this expression with respect to each prime power dividing

M - 1

$M-1$ , and then the results can be combined with the Chinese Remainder Theorem. Obviously it wasn't intended to do this in contest, considering that computing combinations modulo a non-prime modulus is already annoying enough.