TopCoder SRM 729 Div1 Easy: MagicNumberThree

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

数字のみからなる、 文字の文字列が与えられる。この文字列の (連続とは限らない) 部分列であって、それを数字に直したときに の倍数になるものの総数を、 で割った余りを求めよ。

解説

典型 DP で解けます。leading zero の文字列も普通に数えてしまって良いらしいので罠らしい罠はありません。

注意することがあるとすれば、部分列なので前のインデックスの結果もそのまま伝搬することと、空文字列を答えとしてカウントしないように最後に 引くくらいですかね？

int dp[60][3];
class MagicNumberThree {
    public:
    int countSubsequences(string s) {
        int N = s.length();

        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int i=0; i<N; i++) {
            int val = s[i] - '0';
            for(int k=0; k<3; k++) {
                (dp[i+1][k] += dp[i][k]) %= MOD;
                (dp[i+1][(k+val)%3] += dp[i][k]) %= MOD;
            }
        }
        return dp[N][0] - 1;
    }
};