TopCoder SRM 765 : Div1 Medium NiceMultiples

まんまと引っかかった。
https://community.topcoder.com/stat?c=problem_statement&pm=15695&rd=17678

問題

　
正整数M,U,Bが与えられる。
U以下の整数のうちMの倍数であるもので、B進数表記したときに0を含まないのは何通りか。

解法

Mがある程度大きいとき、Mの倍数を総当たりしてしまってよい。

Mが小さい時だが、これはBで割った余りではなくMで割った余りを考えるとよい。
すなわち、B進数表記のうちU以下でかつMで割った余りが0となるものを上の桁から見ていく。

上の桁がすべて0の場合、ある桁が0でも構わないのでそこは注意。

ll mo=1000000007;
ll from[2][2][101010];
ll to[2][2][101010];

class NiceMultiples {
	public:
	int count(long long M, long long U, int B) {
		
		if(U/M<=10000000) {
			int ret=0;
			for(ll a=M;a<=U;a+=M) {
				int ok=1;
				ll v=a;
				while(v && ok) {
					if(v%B==0) ok=0;
					v/=B;
				}
				ret+=ok;
			}
			return ret;
		}
		
		vector<int> P;
		ll v=U;
		while(v) {
			P.push_back(v%B);
			v/=B;
		}
		
		ZERO(from);
		from[1][0][0]=1;
		reverse(ALL(P));
		FORR(p,P) {
			ZERO(to);
			int cap,pos,i,b;
			FOR(cap,2) FOR(pos,2) FOR(i,M) FOR(b,B) {
				if(cap && b>p) continue;
				if(pos&&b==0) continue;
				int npos=pos||b;
				int ncap=(cap&&(b==p));
				(to[ncap][npos][(i*B+b)%M]+=from[cap][pos][i])%=mo;
			}
			
			swap(from,to);
		}
		return (from[0][1][0]+from[1][1][0])%mo;
		
	}
}

まとめ

まんまとMの倍数の数に対してBで割った余りを考えて混乱した。
それでも解けるっちゃ解けそうだけどね。