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; }