Torni

warning: unused import: `std::collections::BTreeSet`
 --> input/code.rs:1:5
  |
1 | use std::collections::BTreeSet;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `std::collections::VecDeque`
 --> input/code.rs:2:5
  |
2 | use std::collections::VecDeque;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: function is never used: `solve`
  --> input/code.rs:41:4
   |
41 | fn solve(n: usize) -> usize {
   |    ^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: function is never used: `brute`
  --> input/code.rs:52:4
   |
52 | fn brute(n: usize) -> usize {
   |    ^^^^^

use std::collections::BTreeSet;
use std::collections::VecDeque;
use std::io::BufRead;

const MOD: usize = 1_000_000_007;

struct Solver {
    result: Vec<usize>,
}

impl Solver {
    pub fn new(max_n: usize) -> Self {
        let mut solid: Vec<usize> = Vec::with_capacity(max_n);
        let mut split: Vec<usize> = Vec::with_capacity(max_n);
        let mut result: Vec<usize> = Vec::with_capacity(max_n);
        let mut result_sum: usize = 0;

        solid.push(1);
        split.push(1);
        result.push(2);
        result_sum += 2;

        for _ in 1..max_n {
            let last_solid = *solid.last().unwrap();
            let last_split = *split.last().unwrap();
            split.push((4 * last_split + last_solid) % MOD);
            solid.push((1 + result_sum) % MOD);

            result.push((solid.last().unwrap() + split.last().unwrap()) % MOD);
            result_sum = (result_sum + result.last().unwrap()) % MOD;
        }

        Self { result }
    }

    pub fn res(&self, n: usize) -> usize {
        self.result[n - 1]
    }
}

fn solve(n: usize) -> usize {
    Solver::new(n).res(n)
}

#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
struct Block {
    sideways: bool,
    up: bool,
    down: bool,
}

fn brute(n: usize) -> usize {
    fn construct_until(
        left: &mut Vec<Block>,
        right: &mut Vec<Block>,
        all: &mut Vec<(Vec<Block>, Vec<Block>)>,
        n: usize,
    ) {
        if left.len() == n && right.len() == n {
            all.push((left.clone(), right.clone()));
            return;
        }
        if left.len() < n {
            for i in 1..=n - left.len() {
                // Just add to left column
                for j in 0..i {
                    left.push(Block {
                        sideways: false,
                        up: j != i - 1,
                        down: j > 0,
                    });
                }
                construct_until(left, right, all, n);
                for _ in 0..i {
                    left.pop();
                }
            }
        }
        if right.len() < n {
            for i in 1..=n - right.len() {
                // Just add to right column
                for j in 0..i {
                    right.push(Block {
                        sideways: false,
                        up: j != i - 1,
                        down: j > 0,
                    });
                }
                construct_until(left, right, all, n);
                for _ in 0..i {
                    right.pop();
                }
            }
        }
        if left.len() == right.len() && left.len() < n {
            // Add a double-wide block
            for i in 1..=n - right.len() {
                // Just add to right column
                for j in 0..i {
                    left.push(Block {
                        sideways: true,
                        up: j != i - 1,
                        down: j > 0,
                    });
                    right.push(Block {
                        sideways: true,
                        up: j != i - 1,
                        down: j > 0,
                    });
                }
                construct_until(left, right, all, n);
                for _ in 0..i {
                    left.pop();
                    right.pop();
                }
            }
        }
    }
    let mut all = Vec::new();
    construct_until(&mut vec![], &mut vec![], &mut all, n);
    all.sort();
    all.dedup();

    // println!("{:?}",all);

    all.len()
}

fn main() {
    let solver = Solver::new(1_000_000);
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let mut lines = stdin.lines();
    let t: usize = lines.next().unwrap().unwrap().parse().unwrap();
    for _ in 0..t {
        let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
        println!("{}", solver.res(n));
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_samples() {
        assert_eq!(solve(1), 2);
        assert_eq!(solve(2), 8);
        assert_eq!(solve(3), 34); // Brute
        assert_eq!(solve(4), 148); // Brute
        assert_eq!(solve(5), 650); // Brute
        assert_eq!(solve(6), 2864);
        assert_eq!(solve(7), 12634); // Brute
        assert_eq!(solve(8), 55756); // Brute
        assert_eq!(solve(9), 246098); // Brute
        assert_eq!(solve(10), 1086296); // Brute
        assert_eq!(solve(11), 4795090); // Brute
        assert_eq!(solve(12), 21166468); // Brute
        assert_eq!(solve(13), 93433178); // Brute
        assert_eq!(solve(14), 412433792); // Brute
        assert_eq!(solve(15), 1820570506 % MOD); // Brute
        assert_eq!(solve(16), 8036386492 % MOD); // Brute
        assert_eq!(solve(17), 35474325410 % MOD); // Brute
        assert_eq!(solve(18), 156591247016 % MOD); // Brute
        assert_eq!(solve(19), 691227204226 % MOD); // Brute
        assert_eq!(solve(20), 3051224496244 % MOD); // Brute
        assert_eq!(solve(21), 13468756547882 % MOD); // Brute
        assert_eq!(solve(22), 59453967813584 % MOD); // Brute
        assert_eq!(solve(23), 262442511046330 % MOD); // Brute
        assert_eq!(solve(24), 1158477291582892 % MOD); // Brute
        assert_eq!(solve(25), 5113766172173042 % MOD); // Brute
        assert_eq!(solve(26), 22573255991958008 % MOD); // Brute
        assert_eq!(solve(27), 99643172746536754 % MOD); // Brute

        assert_eq!(solve(1337), 640403945);
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED