AOJ 2182 Eleven Lover

問題

Eleven Lover | Aizu Online Judge

数字のみからなる文字列 s が与えられる。この中に, 連続した文字列でその表す数が 11 の倍数であるようなものは何通りあるか。ただし, 先頭が 0 であるような数は数とみなさないことにする。

解法

区間 [i, j] が 11 の倍数である条件は,

S[i] - S[i+1] + ... + (-1)^(j-i)S[j] = 0 (mod 11) です。
manabi.matiralab.com

よって, sum[i] = S[0] - S[1] + ... + (-1)^(i-1)S[i-1] とすれば, 区間 [i, j] が 11 の倍数である条件は,

sum[j] - sum[i] = 0 (mod 11)
となります。

よって解法としては,

• sum を求める
• 各 i ごとに, 「i < j, sum[i] = sum[j] となる j の個数を求める」

とすれば良いです。

const int MAXN = 100000;
int sum[MAXN];
int cnt[11];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    while (cin >> s) {
        if (s == "0") break;
        int n = s.size();
        memset(cnt, 0, sizeof(cnt));
        cnt[0] = 1;
        for (int i = 0; i < n; i++) {
            int num = (s[i]-'0');
            sum[i+1] = sum[i] + (i%2==0 ? num : -num);
            sum[i+1] = (sum[i+1]+11)%11;
            cnt[sum[i+1]]++;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int num = sum[i];
            cnt[num]--;
            if (s[i] != '0') ans += cnt[num];
        }
        cout << ans << endl;
    }
    return 0;
}