Niitty

use std::collections::VecDeque;
use std::{cmp, io};
use std::cell::RefCell;
use std::rc::Rc;

fn main() {
    let stdin = io::stdin();

    let n: usize = {
        let mut input: String = String::new();
        stdin.read_line(&mut input).unwrap();
        input.trim().parse().unwrap()
    };

    let mut tree_last_row: Vec<Vec<u32>> = Vec::with_capacity(2 * n);
    for _ in 0..n {
        let mut row_columns: Vec<u32> = Vec::with_capacity(n);

        let mut input: String = String::new();
        stdin.read_line(&mut input).unwrap();
        let mut chars = input.trim().chars();
        for _ in 0..n {
            let char = chars.next().unwrap().to_ascii_uppercase();
            debug_assert!(char.is_ascii_alphabetic());

            let index = get_char_index(char);
            let flower = 1 << index;
            row_columns.push(flower);
        }

        let subtree = build_tree(row_columns, sum_flower_cells);
        tree_last_row.push(subtree);
    }

    let tree = build_tree(tree_last_row, sum_flower_rows);

    let all_flower_types: u32 = tree[0][0];
    let counter = Rc::new(RefCell::new(0u128));
    for start_y in 0..n {
        for end_y in start_y..n {
            let vertical = get_flowers(start_y, end_y, n, &tree, sum_flower_rows);
            process_tree(&vertical, 0, 1, 0, &all_flower_types, 0, Some(&counter));
        }
    }

    println!("{}", counter.take());
}


/// Returns a pair (left, right) where first two describe how many selections starting from that side can be made with all flower types included.
fn process_tree(tree: &Vec<u32>, root: usize, root_level_length: usize, root_level_start: usize, all_flower_types: &u32, provided_flower_types: u32, counter: Option<&Rc<RefCell<u128>>>) -> (u128, u128) {
    if tree[root_level_start + root] | provided_flower_types != *all_flower_types {
        return (0, 0);
    }

    let second_level_start = root_level_start + root_level_length;
    let second_level_len = root_level_length * 2;
    let third_level_start = second_level_start + second_level_len;

    let left_child_index = root * 2;
    let right_child_index = left_child_index + 1;

    if tree.len() > second_level_start && tree[second_level_start + right_child_index] == 0 {
        // There is only 1 real child (the left one). Calculations can be delegated to that one.
        return process_tree(&tree, left_child_index, second_level_len, second_level_start, all_flower_types, provided_flower_types, counter);
    }

    // Selecting the whole area represented by this node is guaranteed to yield all flowers, thus counters are 1 by default.
    let mut left_selections = 1;
    let mut right_selections = 1;
    if counter.is_some() {
        *counter.unwrap().borrow_mut() += 1;
    }

    if tree.len() > second_level_start {
        // This is not the last level.
        let left_child = process_tree(&tree, left_child_index, second_level_len, second_level_start, all_flower_types, provided_flower_types, counter);
        let right_child = process_tree(&tree, right_child_index, second_level_len, second_level_start, all_flower_types, provided_flower_types, counter);

        left_selections += left_child.0;
        right_selections += right_child.1;

        if tree.len() > third_level_start {
            // Root's children have children.
            let has_right_right = tree[third_level_start + right_child_index * 2 + 1] != 0; // Whether right has a right child. i.e. left + right's left child isn't the full area.
            if left_child.0 > 0 {
                // If the left child has all flowers, combining it with the right child's left child will also have all flowers.
                let addition = if !has_right_right {
                    // Deduct full area so it isn't counted twice.
                    left_child.0 - 1
                } else {
                    left_child.0
                };
                if counter.is_some() {
                    *counter.unwrap().borrow_mut() += addition;
                }
                left_selections += addition;
            } else {
                // Try the left child and the right child's left child.
                let right_left_child_index = right_child_index * 2;
                let right_left_child_node = &tree[third_level_start + right_left_child_index];
                let left_child_again = process_tree(&tree, left_child_index, second_level_len, second_level_start, all_flower_types, provided_flower_types | right_left_child_node, None);
                if left_child_again.1 > 0 {
                    // Selection [left completely] + [right's left child] is possible.
                    left_selections += 1;
                }
                if counter.is_some() {
                    // Selection [some rightmost children of left] + [right's left child] is possible.
                    *counter.unwrap().borrow_mut() += left_child_again.1;
                }
            }

            if right_child.1 > 0 {
                // If the right child has all flowers, combining it with the left child's right child will also have all flowers.
                let addition = if !has_right_right {
                    // Deduct full area so it isn't counted twice.
                    right_child.0 - 1
                } else {
                    right_child.0
                };
                if counter.is_some() {
                    *counter.unwrap().borrow_mut() += addition;
                }
                right_selections += addition;
            } else {
                // Try the right child and the left child's right child.
                let left_right_child_index = left_child_index * 2 + 1;
                let left_right_child_node = &tree[third_level_start + left_right_child_index];
                let right_child_again = process_tree(&tree, right_child_index, second_level_len, second_level_start, all_flower_types, provided_flower_types | left_right_child_node, None);
                if right_child_again.1 > 0 {
                    // Selection [right completely] + [left's right child] is possible.
                    right_selections += 1;
                }
                if counter.is_some() {
                    // Selection [some leftmost children of right] + [left's right child] is possible.
                    *counter.unwrap().borrow_mut() += right_child_again.0;
                }
            }
        }
    }

    (left_selections, right_selections)
}

fn build_tree<T : Default>(mut bottom_row: Vec<T>, sum_function: fn(&T, &T) -> T) -> Vec<T> {
    let bottom_row_len = bottom_row.len().next_power_of_two();
    for _ in bottom_row.len()..bottom_row_len {
        bottom_row.push(T::default());
    }
    debug_assert!(bottom_row.len().is_power_of_two());
    debug_assert_eq!(bottom_row.len(), bottom_row_len);

    let mut tree: VecDeque<T> = VecDeque::with_capacity(bottom_row_len * 2);
    tree.extend(bottom_row);
    let default_t = T::default();
    let mut sum_start = 0;
    let mut sum_len = bottom_row_len;
    while sum_len > 1 {
        let dest_len = sum_len / 2;
        for i in (0..dest_len).rev() {
            let a = sum_start + i * 2;
            let b = a + 1;

            let a_item = &tree[a];
            let b_item = if b >= (sum_start + sum_len) { &default_t } else { &tree[b] };

            tree.push_front(sum_function(a_item, b_item));
            sum_start += 1;
        }

        sum_len = dest_len;
        sum_start -= dest_len;
    }

    Vec::from(tree)
}

fn get_flowers<T : Default>(mut start: usize, mut end: usize, n: usize, tree: &Vec<T>, sum_function: fn(&T, &T) -> T) -> T {
    let mut level_len = n.next_power_of_two();
    let mut level_start = tree.len() - level_len;
    let mut sum = T::default();
    while start <= end {
        debug_assert!(end < level_len);
        if start % 2 == 1 {
            sum = sum_function(&sum, &tree[level_start + start]);
            start += 1;
        }
        if end % 2 == 0 {
            sum = sum_function(&sum, &tree[level_start + end]);
            if end == 0 {
                break;
            } else {
                end -= 1;
            }
        }

        // Move one level up
        level_len /= 2;
        level_start -= level_len;
        start /= 2;
        end /= 2;
    }

    sum
}

// Valid indices start from 1. 0 is reserved for an invalid/dummy state without actual flowers.
fn get_char_index(flower: char) -> u32 {
    if 'A' <= flower && flower <= 'Z' {
        flower as u32 - 'A' as u32 + 1
    } else {
        panic!("Illegal flower: {}", flower);
    }
}

#[inline]
fn sum_flower_cells(a: &u32, b: &u32) -> u32 {
    *a | *b
}

fn sum_flower_rows(a: &Vec<u32>, b: &Vec<u32>) -> Vec<u32> {
    let len = cmp::max(a.len(), b.len());
    let mut vec = Vec::with_capacity(len);
    if a.len() == b.len() {
        for i in 0..len {
            vec.push(sum_flower_cells(&a[i], &b[i]));
        }
    } else {
        // This would also work for the other case, but this is probably slower.
        debug_assert_eq!(cmp::min(a.len(), b.len()), 0);
        let mut a_iter = a.iter().chain([0].iter().cycle());
        let mut b_iter = b.iter().chain([0].iter().cycle());
        for _ in 0..len {
            vec.push(sum_flower_cells(a_iter.next().unwrap(), b_iter.next().unwrap()));
        }
    }
    vec
}

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 6

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 7

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 8

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 9

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 10

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 12

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 13

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 14

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 15

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 16

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 17

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 18

Group: 5, 6

Verdict: WRONG ANSWER

Test 19

Group: 5, 6

Verdict: WRONG ANSWER

Test 20

Group: 5, 6

Verdict: WRONG ANSWER

Test 21

Group: 5, 6

Verdict: WRONG ANSWER

Test 22

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 6

Verdict: TIME LIMIT EXCEEDED