AOJ 2182 Eleven Lover

問題のリンク

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2182

問題概要

ある自然数 N が与えられる．その連続部分文字列（0から始まるものを除く）で，11の倍数となるものはいくつあるか？

制約: N の桁数は 80000 以下．

解法

DP で解くことができる．dp[i][j] := 先頭から i 桁目まで見たときに，11 で割ったあまりが j となるものの総数，と定義する．
ここで，ある整数 n を 11 で割った余りの計算をたとえば 17891 を例にして考えてみる．
先頭から順番に見ていけばよく，まず 1 % 11 = 1 となる．
次に 1 * 10 + 7 % 11 = 6．
6 * 10 + 8 % 11 = 2．
2 * 10 + 9 % 11 = 7．
7 * 10 + 1 % 11 = 5．
となり，あまりは5となる．これを利用して dp で計算する．
つまり，dp[i+1][(j*10+d)%11] += dp[i][j] を計算していけば良い．ただし，d は現在見ている(i 桁目の)数字である．
また，dp[i+1][d] += 1 とすれば，i桁目を左端とした場合を含めることができる．ただし，0から始まるものは省かなければならない．
答えは dp[i][0] の総和である．

ソースコード

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string n;
    while(cin >> n, n != "0") {
        vector<vector<int>> dp(n.size()+1, vector<int>(11));
        int res = 0;
        for(int i=0; i<n.size(); ++i) {
            int m = n[i]-'0';
            if(m != 0) {
                dp[i+1][m] += 1;
            }
            for(int j=0; j<11; ++j) {
                dp[i+1][(j*10+m)%11] += dp[i][j];
            }
            res += dp[i+1][0];
        }
        cout << res << endl;
    }
}