[Problem suggestion] Permutation group order

[adamant-pwn]

I have the problem prepared on polygon. How do I add it here?

===

You're given k permutations of length n. Find the order of permutation group generated by them.

input

N K
P_{11} P_{12} ... P_{1n}
P_{21} P_{22} ... P_{2n}
...
P_{k1} P_{k2} ... P_{kn}

output

ANS

Constraint

N <= 50, K <= 100.

[yosupo06]

Hello adamant! Before adding the problem, could you explain about some points?

• I think the answer may reach to 50!, that exceeds int128. How do you plan to handle it? (mod or bigint?)
• Is there any material about this problem? Actually I don't know how to solve this problem. At least, I want to know the time complexity of your solution.

Thanks for contributing!

[adamant-pwn]

Problem on polygon assumes bigint, but we may change it to mod if necessary, although only naive long addition and multiplication is enough to tackle it. As far as I know, author's solution is based on the algorithm from "Polynomial-Time Algorithms for Permutation Groups" article. I also implemented Schreier-Sims algorithm, but it needed some constant-time optimisations and randomisation to pass TL. Time complexity is polynomial and not easy to estimate exactly. Naive Schreier-Sims algorithm implementation has O(n^3*k+n^6) complexity, but randomisation makes it significantly faster and there are ways to improve theoretical bounds as well.

[yosupo06]

OK I see, thanks!

I think mod 998244353 is good because we can restore the actual answer by CRT(and we should separate CRT part).

At first, I have to apologize for you that we don't prepare english documents about problem settings yet. I'm translating now. Basically, you can refer 'library-checker-problems/sample/aplusb' to everything (and of course, you may have some trouble, I'll help you).

[yosupo06]

https://github.com/yosupo06/library-checker-problems/blob/master/docs/guideline.en.md You can notice that I don't correction of this document...

[yosupo06]

Problem ID: permutation_group_order