yukicoder : No.372 It's automatic

1回目のSubmitでACが取れた僕。
http://yukicoder.me/problems/598

問題

とても大きな整数Sが与えられる。
Sを文字列と見なしたとき、その部分文字列のうち、Mの倍数であるものが何通りあるか答えよ。
なおleading zeroは許可されない。

解法

S	,Mが微妙に大きいけど、オーソドックスな手段で通ってしまった。

dp[i][p] := 上位i文字の部分文字列のうち、Mで割った余りがpであるものの数
とする。S[i+1]=cとする。
以下のようなDPを行う。

• cを部分文字列の末尾に加える場合: dp[i+1][(p*10+c)%M] += dp[i][p]
• cを部分文字列の末尾に加えない場合: dp[i+1][p] += dp[i][p]

またleading zeroの対策で以下の処理を加えた。

• c=0の場合、cが1桁目となることはできるが、以後に値が続いてはいけないので答えに1を加える。
• c＞0の場合、cが1桁目となるケースを考慮してdp[i+1][c%M] += 1

上記変数dpをそのまま|S|*M個とるとMLEするのでうまく同じ領域を使いまわそう。

string S;
int M;
ll mo=1000000007;

ll from[20202];
ll to[20202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>M;
	ll ret=0;
	FORR(r,S) 
	from[0]=0;
	FORR(r,S) {
		ZERO(to);
		FOR(i,M) {
			to[(i*10+r-'0')%M]+=from[i];
			to[i]+=from[i];
		}
		if(r=='0') ret++;
		else to[(r-'0')%M]++;
		
		FOR(i,M) while(to[i]>=mo) to[i]-=mo;
		swap(from,to);
	}
	cout<<(from[0]+ret)%mo<<endl;
}

まとめ

S	,Mが微妙に大きいから、O(	S	M)解が通るとは思わなかった。