#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; void Main() { int H,W,K; cin >> H >> W >> K; int L = 1; while((1 << L) < min(H,W)) { L++; } vector>> dp(H,vector>(W,vector(L))); for(int i = 0;i < H;i++) { string S; cin >> S; for(int j = 0;j < W;j++) { dp[i][j][0] = 1 << (S[j] - 'a'); } } for(int k = 1;k < L;k++) { int t = 1 << (k - 1); for(int i = 0;i + 2 * t <= H;i++) { for(int j = 0;j + 2 * t <= W;j++) { dp[i][j][k] = dp[i][j][k - 1] | dp[i + t][j][k - 1] | dp[i][j + t][k - 1] | dp[i + t][j + t][k - 1]; } } } vector A(min(H,W) + 1); for(int i = 1;i < (int)A.size();i++) { while(1 << (A[i] + 1) <= i) { A[i]++; } } long long ans = 0; for(int i = 0;i < H;i++) { for(int j = 0;j < W;j++) { int lo = 0,up = 0; { int ng = 0,ok = min(H - i,W - j) + 1; while(ok - ng > 1) { int mid = (ok + ng) / 2; int a = A[mid]; int cur = 0; int ni = i + mid - (1 << a); int nj = j + mid - (1 << a); cur |= dp[i][j][a]; if(__builtin_popcount(cur) >= K) { ok = mid; continue; } cur |= dp[ni][j][a]; if(__builtin_popcount(cur) >= K) { ok = mid; continue; } cur |= dp[i][nj][a]; if(__builtin_popcount(cur) >= K) { ok = mid; continue; } cur |= dp[ni][nj][a]; if(__builtin_popcount(cur) >= K) { ok = mid; continue; } ng = mid; } lo = ok; } { int ng = 0,ok = min(H - i,W - j) + 1; while(ok - ng > 1) { int mid = (ok + ng) / 2; int a = A[mid]; int cur = 0; int ni = i + mid - (1 << a); int nj = j + mid - (1 << a); cur |= dp[i][j][a]; if(__builtin_popcount(cur) > K) { ok = mid; continue; } cur |= dp[ni][j][a]; if(__builtin_popcount(cur) > K) { ok = mid; continue; } cur |= dp[i][nj][a]; if(__builtin_popcount(cur) > K) { ok = mid; continue; } cur |= dp[ni][nj][a]; if(__builtin_popcount(cur) > K) { ok = mid; continue; } ng = mid; /* cur |= dp[i][j][a]; */ /* cur |= dp[ni][j][a]; */ /* cur |= dp[i][nj][a]; */ /* cur |= dp[ni][nj][a]; */ /* if(__builtin_popcount(cur) > K) */ /* { */ /* ok = mid; */ /* } */ /* else */ /* { */ /* ng = mid; */ /* } */ } up = ok; } ans += up - lo; } } cout << ans << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; /* cin >> tt; */ while(tt--) Main(); }