ゆらのふなびと

競プロ, Python, C++

AOJ-ICPC 400 Eleven Lover

問題

Eleven Lover | Aizu Online Judge

10進数表記の数sが与えられる

sの部分文字列のうち、11の倍数であるものの個数を答えよ

ただし、部分文字列のうち先頭が0でないもののみをカウントする

制約

|s| <= 80000

解法

「11の倍数 ⇔ D = (奇数桁目の和) - (偶数桁目の和) が11の倍数」を使う

i桁目までのDをD_iとすると、i桁目を末尾とする11の倍数の個数は、D_1, ..., D_{i-1}のうちD_iから引いて0(mod11)になるものの個数

O(|s|)

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2041828#1