TopCoder SRM 805 : Div1 Medium SubmultiplesOfN

これまた典型的なものが出てきたな。
https://community.topcoder.com/stat?c=problem_statement&pm=16969&rd=18678

問題

数字で構成された文字列Sが与えられる。
Sの部分列を抜き出して数値とみなしたとき、Nの倍数となるものは何通りか。
なお、抜き出した文字列はdistinctなもののみ数え上げる。

解法

dp(i,k) := S中i文字目を処理し、i文字目を抜き出した場合に、そこまでの文字列を数値とみなすとNで割った余りがkとなる場合の数
とすると、dp(*,0)の総和が解となる。
dp(i,k)からは、遷移先を数字0～9で総当たりしよう。数字dが表れる最寄の添え字がS[j]=dであるならば、dp(j,(k*10+d)%N) += dp(i,k)のように遷移する。

ll dp[5050][1010];
const ll mo=1000000007;
int nex[5050][10];

class SubmultiplesOfN {
	public:
	int count(string B, int N) {
		int i,j,x;
		int L=B.size();
		FOR(i,10) nex[L][i]=L;
		for(i=L-1;i>=0;i--) {
			FOR(j,10) nex[i][j]=nex[i+1][j];
			nex[i][B[i]-'0']=i;
		}
		
		ZERO(dp);
		dp[0][0]=1;
		ll ret=0;
		FOR(i,L) FOR(j,N) FOR(x,10) if(nex[i][x]!=L) {
			if(i==0&&x==0) continue;
			(dp[nex[i][x]+1][(j*10+x)%N]+=dp[i][j])%=mo;
			if((j*10+x)%N==0) (ret+=dp[i][j])%=mo;
		}
		
		return ret%mo;
	}
}

まとめ

Easyの方が神経使う問題だったな。