らての精進日記

修行をします

aoj2182:Eleven Lover

解法

dp[i+1][j] : i文字目を末尾とする部分文字列で、11で割った余りがjであるようなものの数、とする。

i文字目の数がdだったとすると、下記の2つの遷移
dp[i+1][(j*10+d)%11]=dp[i][j]; (末尾にdを加える)
if(d)dp[i+1][d]++; (新たに長さ1の文字列を加える)
を行えばいい。

#include<bits/stdc++.h>
using namespace std;
 
string S;
int dp[80010][11];
 
int main(){
    while(cin>>S,S!="0"){
        int ans=0;
        for(int i=0;i<S.size();i++){
            int d=S[i]-'0';
            for(int j=0;j<11;j++)dp[i+1][(j*10+d)%11]=dp[i][j];
            if(d)dp[i+1][d]++;
            ans+=dp[i+1][0];
        }
        cout<<ans<<endl;
    }
    return 0;
}