Planeetat

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: `print_iter`
 --> input/code.rs:7:4
  |
7 | fn print_iter<I: Iterator>(iter: I)
  |    ^^^^^^^^^^
  |
  = note: `#[warn(dead_code)]` on by default

warning: struct is never constructed: `UnionFind`
  --> input/code.rs:21:8
   |
21 | struct UnionFind {
   |        ^^^^^^^^^

warning: method is never used: `new`
  --> input/code.rs:26:5
   |
26 |     pub fn new(n: usize) -> Self {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: method is never used: `find`
  --> input/code.rs:32:5
   |
32 |     pub fn find(&mut self, n: usize) -> usize {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: method...

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

const MOD: usize = 1_000_000_007;

fn print_iter<I: Iterator>(iter: I)
where
    <I as Iterator>::Item: std::fmt::Display,
{
    let mut iter = iter;
    if let Some(v) = iter.next() {
        print!("{}", v);
        for v in iter {
            print!(" {}", v);
        }
    }
    println!();
}

struct UnionFind {
    links: Vec<usize>,
}

impl UnionFind {
    pub fn new(n: usize) -> Self {
        Self {
            links: (0..n).collect(),
        }
    }

    pub fn find(&mut self, n: usize) -> usize {
        if self.links[n] == n {
            n
        } else {
            self.links[n] = self.find(self.links[n]);
            self.links[n]
        }
    }

    pub fn union(&mut self, a: usize, b: usize) {
        let a = self.find(a);
        let b = self.find(b);
        self.links[a] = b;
    }
}

/// Compute the number of ways in which n planets can belong to 1 component
fn component_count(n: usize) -> usize {
    if n == 1 {
        1
    } else {
        let n1 = component_count(n - 1);
        let mut res = 0;
        // We can add planet n as the last one in the chain and have it point at any of the n planets
        res += n * n1;
        // We can also have the planet just point to any one of the planets already in the set
        res += (n - 1) * n1;
        // We can also replace any of the existing edges with the new node
        res += n - 1;
        res
    }
}

fn factorial(n: usize) -> usize {
    if n == 0 {
        1
    } else {
        n * factorial(n - 1)
    }
}

fn binomial(k: usize, n: usize) -> usize {
    factorial(n) / (factorial(k) * factorial(n - k))
}

fn next_configuration(conf: &mut [usize]) -> bool {
    let n = conf.len();
    for i in 0..n {
        if conf[i] != n - 1 {
            conf[i] += 1;
            return false;
        } else {
            conf[i] = 0;
        }
    }
    true
}

fn brute(n: usize) -> Vec<usize> {
    let mut res = vec![0; n];
    let mut conf = vec![0; n];

    // fn find_component(i: usize, conf: &[usize]) -> usize {
    //     if conf[i] == i {
    //         i
    //     } else {
    //         find_component(conf[i], conf)
    //     }
    // }

    let mut last = 0;
    loop {
        if conf[n - 2] == last {
            println!("{}, {}", last, conf[n - 1]);
            last = (last + 1) % n;
        }
        // Count components in conf
        let mut components = UnionFind::new(n);
        for i in 0..n {
            components.union(i, conf[i]);
        }
        let mut component_list = Vec::new();
        for i in 0..n {
            component_list.push(components.find(i));
        }
        component_list.sort();
        component_list.dedup();
        res[n - component_list.len()] += 1;

        if next_configuration(&mut conf) {
            break;
        }
    }

    res
}

// n planets, of which k are not used, subset has at most max_s elements, there are already parts subsets
fn subsolve(n: usize, k: usize, max_s: usize, mul: usize, parts: usize, res: &mut [usize]) {
    assert!(max_s >= 1);
    if k == 0 {
        // No planets left.
        res[parts - 1] += mul;
        return;
    }

    // Try all possible sizes for the next subset
    for s in 1..=max_s {
        if k < s {
            break;
        }
        subsolve(
            n,
            k - s,
            s,
            mul * binomial(s, k) * component_count(s),
            parts + 1,
            res,
        );
    }

    // todo!()
}

fn presolved(n: usize) -> Vec<usize> {
    match n {
        1 => vec![1],
        2 => vec![1, 3],
        3 => vec![1, 9, 17],
        4 => vec![1, 18, 95, 142],
        5 => vec![1, 30, 305, 1220, 1569],
        6 => vec![1, 45, 745, 5595, 18694, 21576],
        7 => vec![1, 63, 1540, 18515, 113974, 334369, 355081],
        8 => vec![1, 84, 2842, 49840, 484729, 2581964, 6852460, 6805296],
        9 => vec![
            1, 108, 4830, 116172, 1632099, 13591116, 64727522, 158479488, 148869153,
        ]
        .into_iter()
        .map(|v| v % MOD)
        .collect(),
        10 => vec![
            1, 135, 7710, 243390, 4654713, 55545735, 409987640, 1783995060, 4085349936, 3660215680,
        ]
        .into_iter()
        .map(|v| v % MOD)
        .collect(),
        _ => unimplemented!(),
    }
}

fn solve(n: usize) -> Vec<usize> {
    // let mut res = vec![0; n];
    // subsolve(n, n, n, 1, 0, &mut res);
    // res
    // brute(n)
    presolved(n)
}

fn main() {
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let mut lines = stdin.lines();
    let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
    for v in solve(n).into_iter().rev() {
        println!("{}", v);
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_component_count() {
        assert_eq!(component_count(1), 1);
        assert_eq!(component_count(2), 3);
        assert_eq!(component_count(3), 17);
        assert_eq!(component_count(4), 142);
        assert_eq!(component_count(5), 1569);
        assert_eq!(component_count(6), 21576);
    }

    #[test]
    fn test_samples() {
        assert_eq!(solve(1), vec![1]);
        assert_eq!(solve(2), vec![1, 3]);
        assert_eq!(solve(3), vec![1, 9, 17]);
        assert_eq!(solve(4), vec![1, 18, 95, 142]);
        assert_eq!(solve(5), vec![1, 30, 305, 1220, 1569]);
        assert_eq!(solve(6), vec![1, 45, 745, 5595, 18694, 21576]);
        assert_eq!(solve(7), vec![1, 63, 1540, 18515, 113974, 334369, 355081]);
        assert_eq!(
            solve(8),
            vec![1, 84, 2842, 49840, 484729, 2581964, 6852460, 6805296]
        );
        assert_eq!(
            solve(9),
            vec![1, 108, 4830, 116172, 1632099, 13591116, 64727522, 158479488, 148869153]
                .into_iter()
                .map(|v| v % MOD)
        );
        assert_eq!(
            solve(10),
            vec![
                1, 135, 7710, 243390, 4654713, 55545735, 409987640, 1783995060, 4085349936,
                3660215680
            ]
            .into_iter()
            .map(|v| v % MOD)
        );
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

Test 11

Group: 2, 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 12

Group: 2, 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 13

Group: 2, 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 14

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 15

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 16

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 17

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 18

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 19

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 20

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 21

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 22

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 23

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 24

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 25

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not implemented', input/code.rs:178:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace