エクサウィザーズ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,

dp[i][j]=j

Then,

dp[i+1][j] = i*dp[i][j] + dp[i][j%a[i]]

Finally, the answer is dp[N][X]. It takes O(NX) time, which is fast enough.

排列的 DP 常常一样。