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

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2182 Eleven Lover

AOJ

2進数における3の倍数の求め方と同じですよねこれ

問題文

Eleven Lover | Aizu Online Judge
80000文字以下の数字のみからなる文字列sが与えられる.
連続した部分文字列について,10進の数字として先頭が0でないかつ11の倍数であるようなものの個数を求めよという問題です.

解法

1 \equiv 1 (mod 11)
10 \equiv -1 (mod 11)
100 \equiv 1 (mod 11)
1000 \equiv -1 (mod 11)
10000 \equiv 1 (mod 11)
となることからも分かるように,各桁に-1^{桁数}をかけたものの総和が0(mod 11)であるかどうかを調べれば答えが求まる.
これについては99とか1001=990+11とかを考えていけばそのうち思いつけます.
O(N)でやる必要があるので,上の桁から順にみていき,dp(k)=k(mod11)である数字の組み合わせの数 としてDPしていきます.
今見ている数字dが0でないならdp(d)を1追加する みたいな処理をすることでleading zeroを回避できます.
今が奇数桁か偶数桁にいるかで遷移の符号が変わってきますので,配列を二つもって交代させながら遷移させていくとうまくいきます.