エクサウィザーズ 2019 D - Modulo Operations (600)

D - Modulo Operations

概要

N項の数列Sと整数Xが与えられる。Xは黒板に書いてある。
N!通りあるSの順列のそれぞれについて、黒板に書いてある数をmod S[i] して黒板に書き直すことを繰り返してゆき、最後に黒板に残った数字を足してゆく。合計を求めよ。
(mod 10^9+7して出力)

制約

1 ≦ N ≦ 200
1 ≦ S[i], X ≦ 10^5

方針

重要な点として、今の黒板の数字より大きなS[i]でmodしても黒板の数字は変化しない。
なので、ある順列で操作する際は、その順列の中で減少している部分列だけを考えればよい。
つまり、部分列が等しい順列は最終的な黒板の数字が等しくなるので、計算をまとめることができる。

実際にどのように計算をまとめてゆくかについて、まずはSを降順ソートし、下記のようなDPを考える。
dp[i][j]：S[i-1]までの操作を終えて黒板の数字がjであるときの通り数
するとこのDPは以下のように遷移する。
①S[i-1]を使うとき
dp[i][j % S[i-1]] += dp[i-1][j]

②S[i-1]を使わないとき
dp[i][j] += dp[i-1][j] * (N - i)

感想

アルメリアさんのブログにすごく詳しい解説があります。
betrue12.hateblo.jp

エクサウィザーズのDの600はアルメリアさんのブログを超参考にして通せました。https://t.co/lDIVMKpHz4
コンテスト中は「昇順だと黒板の数字変わらない」という方針で頑張って再帰で組んでTLEでしたが、降順ソートで黒板の数字を保持するDPにするとすごく見通しがいいですね。

— misora192 (@misora192) 2019年4月3日

解答

Submission #4818580 - ExaWizards 2019

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll MOD = 1e9+7;
 
	int N, X;
	cin >> N >> X;
 
	vector<ll> S(N, 0);
	rep(i, N) cin >> S[i];
 
	sort(S.begin(), S.end(), greater<ll>());
 
	vector<vector<ll>> dp(N+1, vector<ll>(X+1, 0));
	dp[0][X] = 1;
 
	for(int i = 1; i <= N; i++){
		for(int j = 0; j <= X; j++){
			dp[i][j % S[i-1]] += dp[i-1][j];
			dp[i][j % S[i-1]] %= MOD;
			dp[i][j] += dp[i-1][j] * (N - i);
			dp[i][j] %= MOD;
		}
	}
 
	ll ans = 0;
	for(int i = 0; i <= X; i++){
		ans += i * dp[N][i] % MOD;
		ans %= MOD;
	}
 
	cout << ans << endl;
}