TopCoderOpen 2015 Round2A Easy ModModMod

EasyはTLEするし、Challengeは取り消されるし散々な回。
http://community.topcoder.com/stat?c=problem_statement&pm=13614

問題

N要素の数列Mが与えられる。
関数fはMを用いてf(x)=x % M[0] % M[1] % .. % M[N-1]で定義される。

整数Rに対し、f(1)+f(2)+f(3)+...+f(R)を求めよ。

解法

f(x)では、xに対し% M[i]を実行するたびに、xの値がM[i]以上の時にはmod M[i]を取った値になる。

この考察から、初期状態で1～Rの数字が1個ずつあり、ある場合、%M[i]を実行するたびに各数字の数が変化する様子を計算していけば良い。
数字yの数をG(y)とする。
各M[i]に対し、M[i]≦y≦Rとなるy、G(y%M[i]) += G(y)を計算した上でR=M[i]-1で更新していけば良い。

Rは結構大きいが、こうするとO(|M|+R)で解ける。
コードにすると非常に簡潔。

class ModModMod {
	public:
	long long findSum(vector <int> m, int R) {
		vector<int> V(R+1,1);
		FORR(r,m) for(;R>=r;R--) V[R%r]+=V[R];
		ll ret=0;
		for(ll x=1;x<=R;x++) ret += x*V[x];
		return ret;
	}
}

まとめ

無駄にDFSしてMLE/TLEしてしまった。