KRECT  Counting KRectangle
English  Vietnamese 
Given a M*N square board. Each square contains a letter of the English alphabet ('A' .. 'Z').
A Krectangle of the board is a rectangle whose sides are parallel to the sides of the board, and contains exactly K different types of letter.
For example, with this 4*3 board:
CED CEB CBC DDA
The rectangle [(1,1), (2,2)] is a 2rectangle of the board because it contains 2 different letters: C and E.
Given M, N, K and the M*N board. Determine how many Krectangles there are in the board.
Input
The first line contains 3 integers M, N and K. (1 ≤ M, N ≤ 100, 1 ≤ K ≤ 26)
The following M lines, each contains N letters of the English alphabet ('A' .. 'Z')
Output
Write one integer  the number of Krectangles in the given board.
Example
Input: 4 3 3 CED CEB CBC DDA Output: 12
hide comments
xxbloodysantaxx:
20150703 08:45:51
@Rafail it was informative , I never knew it but rather building up table was faster! O(1) queries you see. 

Rafail Loizou:
20150414 16:42:34
to avoid counting the 1s in the binary representation in O(A) linear time you should just use a builtin function. Search and you shall find! 

Nivin :
20140331 06:25:21
strict time limit :) 

aristofanis:
20140214 15:09:51
Got AC with O(n^4)


himalay:
20140213 23:04:54
How is number of rectangles in given test case 12, mine answer is 7. 

rishabhshinghal:
20140118 11:30:16
my solution of complexity O(n^2*m^2*26) is not getting accpeted 

Eternia:
20091127 03:30:14
it's weird.. when I submitted my code(O(n^4)) and with LANG C++ 4.3.2 it passed all the test cases in 4.62 sec but when I submitted the same code with LANG C++ 4.0.08, the result it TLE...


Jelle van den Hooff:
20091002 05:48:01
O((NM)^2) works great, but you have to keep the constant factor _low_. 

stjepan:
20091002 05:48:01
My solution is a O(n^2*m^2) algorithm and it is the fastest at the moment. Last edit: 20090603 19:22:36 

Robert Gerbicz:
20091002 05:48:01
I think no.

Added by:  Race with time 
Date:  20090505 
Time limit:  0.343s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JS NODEJS PERL 6 VB.net 
Resource:  Based on problem CRECT  @vnoi 