AOJ 2182 Eleven Lover

Eleven Lover
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2182

問題概要

80000桁の数字から11で割り切れる連続した範囲の数を求めよ。
先頭桁の0は認めない。

解法

dp
dp[i][j][k]:: i 番目の数字までの合計が、奇数桁の合計の11のmodがj、偶数桁がkのものの、
合計開始する位置の種類数。

ソース

#include<iostream>
#include<string>


using namespace std;

int main(){
 string s;
 while(cin >>s){
   if(s == "0")break;
   
   int dp[11][11];
   for(int i = 0; i < 11; i++){
     for(int j = 0; j<11; j++){
       dp[i][j] = 0;
     }
   }
   int ans = 0;
   for(int i = 0; i<(int)s.length(); i++){
     int now = s[i]-'0';
     int nextDP[11][11];
     if(now !=0 )dp[0][0]++;
     for(int j = 0; j<11;j++){
       for(int k = 0; k<11; k++){
         nextDP[j][k] = 0;
       }
     }
     if(i % 2 == 0){
       for(int j = 0; j<11; j++){
         for(int k = 0; k<11; k++){
           nextDP[(j+now)%11][k] += dp[j][k];
         }
       }
     }
     else {
       for(int j = 0; j<11; j++){
         for(int k = 0; k<11; k++){
           nextDP[j][(k+now)%11] += dp[j][k];
         }
       }
     }
     for(int j = 0; j<11;j++){
       for(int k = 0; k<11; k++){
         dp[j][k] = nextDP[j][k];
         if(j == k)ans += nextDP[j][k];
       }
     }
   }
   cout << ans << endl;
 }

 return 0;
}