読者です 読者をやめる 読者になる 読者になる

AOJ 2182 Eleven Lover

競プロ AOJ

問題概要

ある自然数 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;
    }
}