まず、この問題の条件は次のようなものに言い換えられます。
- M 以下の素数を p1,p2,⋯,pK とする。また、「M 以下の最大の pi の整数乗」を pimi とする。
- それぞれの要素を p1n1×p2n2×⋯pKnK と素因数分解する。 1 以上 K 以下の全ての i に対し、全ての要素に対する ni の最大値が mi と等しい。
ここで、 ni=mi とならないような整数についてはその i に対する条件に関係しません。
また、 1 以上 M 以下の全ての整数について、 ni=mi となるような i は最大でも 1 つしか存在しないことが、次の事実が成り立つことから証明できます。
- 全ての i について、M<pimi が成り立つ。
これは、次のように証明できます。
- M<pi である場合、mi=1 である。そのため、この i について成り立つ。
- pi≤M である場合、もしある M 以下の整数 x が存在し pimi=x である場合、 x×pi が M 以下であり、かつより大きい mi が取れるため、矛盾する。そのため、この i について成り立つ。
そのため、次のようなDPを考えることができます。
- DP[i][j]=pi までに対し pimi の倍数であるような数列の要素を選び終わり、残りの要素の個数が j であるような選び方の個数。
ただし、DP[K][j] まで遷移しきった後、最後に答えを求めるための計算が必要なことに注意してください。
これは次のような初期値および遷移になります。
- DP[0][N]=1
- DP[i+1][j−k]+=DP[i][j]×(kj)×floor(M/(pimi))k ただし、 k>0
ここで、 DP[0][N] の初期値を N! にし、 (kj) を (k!)−1 で置き換えることを考えます。このようにすることで、全ての j に対し同じ遷移をすることができ、NTTで遷移を高速化することができるようになります。そのため、答えを O(π(M)NlogN) で求めることができます。
ここで、制約が N≤2000 であるため、 2001 番目の素数である 17393 以上の M に対しては常に答えが 0 になります。これに対し場合分けを行うことで、制約の範囲内で答えを時間内に求めることができます。