エクサウィザーズ 2019 : D - Modulo Operations

なんか似たようなの見たことあるな。
https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_d

問題

N個の異なる整数集合Sが与えられる。
Sを並べ替えた数列N!に対し、初期値Xに対して((X % S[0]) % S[1])...という演算を行った結果の総和を求めよ。

解法

Sはあらかじめ降順に並べておく。
f(n,x) := 前回S[n]を適用することでXが小さくなりxになった状態で、S[n+1]以降の要素の適用に得られる結果の総和
としてメモ化再帰する。

を考える。次にxを小さくするようなS[m]を選ぶことを考える。
すでにxより大きなS[i]かつi＞nの要素は以後いつ適用しても最終的な値に影響しない。
また、x以下のS[i]のうちi＜mの要素はS[m]以降であればいつ選んでもよい。
lを、S[l]がxより大きい最大の要素番号とする。

mを総当たりし、f(n,x) += f(m,x % S[m])*Perm(N-n,m-n)*Perm(N-l-1,m-l-1)
で計算していけばよい。

ll mo=1000000007;
int N,X;
int S[202];
ll memo[201][101010];
ll fact[202];

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}

ll dp(int c,int x) {
	if(c==N) return x;
	if(x<S[N-1]) return fact[N-c]*x%mo;
	if(memo[c][x]>=0) return memo[c][x];
	
	int num=0,el=0;
	int i;
	for(i=c;i<N;i++) if(S[i]>x) num++;
	
	ll ret=0;
	
	for(i=c;i<N;i++) if(S[i]<=x) {
		ret+=comb(N-c-num-1,el)*fact[el]%mo*dp(i+1,x%S[i])%mo;
		el++;
	}
	
	ret%=mo;
	ll pat=comb(N-c,num)*fact[num]%mo;
	return memo[c][x]=ret*pat%mo;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	fact[0]=1;
	for(i=1;i<=201;i++) fact[i]=fact[i-1]*i%mo;
	
	cin>>N>>X;
	FOR(i,N) cin>>S[i];
	MINUS(memo);
	sort(S,S+N);
	reverse(S,S+N);
	
	cout<<dp(0,X)<<endl;
	
	
}

まとめ

SRMで似たようなの見たような。