学步园

不好写思路....比赛的时候有个地方想错了，搞得只会求不是圈的....最后看了http://www.cnblogs.com/kuangbin/archive/2013/08/13/3255856.html  的在圈那一部分的实现...哎...当时差一点就出来了............

AC代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int number[50005];
int digits[50005];
int counts[2][202];
int N, K, now, pre;
__int64 ans;
int iend[50005];
int Ten[10];

int getdigits( int n ){
	if( n == 0 ){
		return 1;
	}
	int cnt = 0;
	while( n ){
		cnt++;
		n /= 10;
	}
	return cnt;
}

int main(){
	while( scanf( "%d%d", &N, &K ) != EOF ){
		memset( counts, 0, sizeof( counts ) ); 
		ans = 0;
		Ten[0] = 1;
		for( int i = 1; i < 5; i++ ){
			Ten[i] = Ten[i-1] * 10 % K;
		}

		for( int i = 0; i < N; i++ ){
			scanf( "%d", &number[i] );
			digits[i] = getdigits( number[i] );
		}

		now = 1;
		pre = 0;
		for( int i = 0; i < N; i++ ){
			now ^= 1;
			pre ^= 1;
			memset( counts[now], 0, sizeof( counts[now] ) );
			counts[now][number[i]%K]++;
			int s = pow( 10, digits[i] );
			for( int j = 0; j < K; j++ ){
				counts[now][(s*j+number[i])%K] += counts[pre][j];
			}
			ans += counts[now][0];
		}

		iend[N-1] = number[N-1] % K;
		int temp = digits[N-1];
		int s = Ten[temp];
		for( int i = N - 2; i >= 0; i-- ){
			iend[i] = number[i] * s % K + iend[i+1];
			iend[i] %= K;
			temp += digits[i];
			s = s * Ten[digits[i]] % K;
		}

		temp = digits[0];
		s = Ten[digits[0]];
		int tt = number[0] % K;
		for( int i = 0; i < N - 1; i++ ){
			counts[now][iend[i]]--;
			for( int j = 0; j < K; j++ ){
				int ppp = ( j * s % K + tt ) % K;
				if( ppp == 0 ){
					ans += counts[now][j];
				}
			}
			tt = tt * Ten[digits[i+1]] + number[i+1];
			tt %= K;
			temp += digits[i+1];
			s = s * Ten[digits[i+1]] % K;
		}
		printf( "%I64d\n", ans );
	}
	return 0;
}