【今日の精進】EXAWIZARDS2019D - Modulo Operations

毎日格上の問題を倒すやつの34日目です。

問題リンク

atcoder.jp

問題概要

長さ の数列 と が与えられるよ。

長さ の全ての順列 に対して、 の総和を求めてね。

解法

見た目が見た目ですが、DPできます。

大きい順に見て行った時、 番目で余りをとる場合、かならず最も先頭に置かないと意味をなしません。

それ以外の場合は、先頭以外のどこかに置く遷移を考えれば良いです。

提出コード

MOD=10**9+7
N,X=map(int,input().split())
S=sorted(list(map(int,input().split())),reverse=True)
dp=[[0 for i in range(X+1)] for i in range(N+1)]
dp[0][X]=1
for i in range(N):
    for j in range(X+1):
        dp[i][j]%=MOD
        dp[i+1][j]+=dp[i][j]*(N-1-i)
        dp[i+1][j%S[i]]+=dp[i][j]
ans=0
for i in range(X+1):
    ans+=i*dp[-1][i]
    ans%=MOD
print(ans)

Submission #46888079 - ExaWizards 2019

感想

DPを疑え!!!

DPを疑え!!!