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