エクサウィザーズ2019 D Modulo Operations
https://atcoder.jp/contests/exawizards2019/tasks
Dynamic programming. Look at the elements in ascending order.
Let dp[i][j] be the answer of the sub problem replacing a[0],...,a[N-1] with a[0],...,a[i-1] and replacing X with j. Suppose a[0] < a[1] < ... < a[N-1]. Insert a[i] into j%x%x%x%x, in which xs are a permutation of a[0],...,a[i-1]. (i+1) permutations are possible after this operation, which are
j%a[i]%x%x%x%x j%x%a[i]%x%x%x j%x%x%a[i]%x%x j%x%x%x%a[i]%x j%x%x%x%x%a[i]
Except the first, the values don't change because y < z implies x%y%z=x%y. Namely,
(j%a[i])%x%x%x%x => dp[i+1][j]+=dp[i][j%a[i]] j%x%a[i]%x%x%x = j%x%x%x%x => dp[i+1][j]+=dp[i][j] j%x%x%a[i]%x%x = j%x%x%x%x => dp[i+1][j]+=dp[i][j] j%x%x%x%a[i]%x = j%x%x%x%x => dp[i+1][j]+=dp[i][j] j%x%x%x%x%a[i] = j%x%x%x%x => dp[i+1][j]+=dp[i][j]
First,
Then,
Finally, the answer is dp[N][X]. It takes O(NX) time, which is fast enough.
排列的 DP 常常一样。