Call the number of steps that a permutation requires the period of the permutation. Every permutation can be partitioned into cycles of sizes such that . Then the period is equal to .
Subtask :
Maintain the number of possible permutations for each possible LCM of a permutation with elements for each . This number is quite small for (it ends up being 1056) but grows quite rapidly. The number of permutations for a single LCM should be stored because for all (Fermat's Little Theorem).
Subtask :
In general, we can calculate the period of a permutation as follows:
So we can essentially solve the problem independently for each distinct prime power . Doing this in for a single prime power is sufficient for this subtask.
Subtask :
If we can count the number of ways to create a permutation of length for each such that no cycle length is divisible by in time, then the solution runs in time.
Subtask :
The high bound on (hopefully) ensures that the above solution does not receive full credit. How can we do better?
Note that if then we can compute the number of permutations containing a cycle with length divisible by in time (assuming that we have precomputed some quantities in ). This is true because if there is a cycle with length divisible by , then there must be exactly one cycle with length equal to (and the rest can have arbitrary lengths).
Let's try to generalize. Define . Any permutation has between and cycles with length divisible by . So it suffices to count each of the following quantities for each .
Mark Chen's code:
#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); }
My code (which uses the principle of inclusion and exclusion):
#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 be the number of -permutations whose cycle lengths all belong to the set . Letting , it follows that
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 time, we can must compute this expression with respect to each prime power dividing , 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.