#252720 (Rust) No.663 セルオートマトンの逆操作

• 問題: No.663 セルオートマトンの逆操作
• ユーザー: sntea
• 提出日時: 2018-04-20 18:21:03
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 6,808 bytes
• コンパイル時間: 2,272 ms
• コンパイル使用メモリ: 164,100 KB
• 実行使用メモリ: 4,380 KB
• 最終ジャッジ日時: 2023-09-09 12:02:41
• 合計ジャッジ時間: 3,708 ms
• ジャッジサーバーID （参考情報）: judge11 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,376 KB
testcase_01	AC	1 ms; 4,380 KB
testcase_02	AC	1 ms; 4,380 KB
testcase_03	AC	1 ms; 4,376 KB
testcase_04	AC	1 ms; 4,380 KB
testcase_05	AC	1 ms; 4,376 KB
testcase_06	AC	1 ms; 4,376 KB
testcase_07	AC	1 ms; 4,376 KB
testcase_08	AC	1 ms; 4,380 KB
testcase_09	AC	1 ms; 4,380 KB
testcase_10	AC	1 ms; 4,376 KB
testcase_11	AC	1 ms; 4,376 KB
testcase_12	AC	1 ms; 4,376 KB
testcase_13	AC	1 ms; 4,380 KB
testcase_14	AC	1 ms; 4,376 KB
testcase_15	AC	1 ms; 4,376 KB
testcase_16	AC	1 ms; 4,380 KB
testcase_17	AC	1 ms; 4,376 KB
testcase_18	AC	1 ms; 4,376 KB
testcase_19	AC	1 ms; 4,380 KB
testcase_20	AC	1 ms; 4,380 KB
testcase_21	AC	1 ms; 4,380 KB
testcase_22	AC	1 ms; 4,376 KB
testcase_23	AC	1 ms; 4,380 KB
testcase_24	AC	1 ms; 4,380 KB
testcase_25	AC	1 ms; 4,376 KB
testcase_26	AC	1 ms; 4,376 KB
testcase_27	AC	1 ms; 4,376 KB
testcase_28	AC	1 ms; 4,380 KB

コンパイルメッセージ

warning: unused macro definition: `printf`
   --> Main.rs:247:18
    |
247 |     macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); }
    |                  ^^^^^^
    |
    = note: `#[warn(unused_macros)]` on by default

warning: function `test` is never used
   --> Main.rs:194:4
    |
194 | fn test(n: usize) {
    |    ^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: associated function `pow` is never used
   --> Main.rs:71:16
    |
71  |             fn pow(&self, x: i64) -> $name {
    |                ^^^
...
186 | make_modint!(1_000_000_000 + 7, ModInt);
    | --------------------------------------- in this macro invocation
    |
    = note: this warning originates in the macro `make_modint` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: 3 warnings emitted

ソースコード

#[allow(dead_code)]
fn getline() -> String {
    let mut res = String::new();
    std::io::stdin().read_line(&mut res).ok();
    res
}

#[allow(unused_macros)]
macro_rules! readl {
    ($t: ty) => {
        {
            let s = getline();
            s.trim().parse::<$t>().unwrap()
        }
    };
    ($( $t: ty),+ ) => {
        {
            let s = getline();
            let mut iter = s.trim().split(' ');
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*)
        }
    };
}

#[allow(unused_macros)]
macro_rules! readlvec {
    ($t: ty) => {
        {
            let s = getline();
            let iter = s.trim().split(' ');
            iter.map(|x| x.parse().unwrap()).collect::<Vec<$t>>()
        }
    }
}

#[allow(unused_macros)]
macro_rules! debug { ($x: expr) => { println!("{}: {:?}", stringify!($x), $x) } }
// macro_rules! debug { ($x: expr) => () }

#[allow(dead_code)]
fn show<T>(iter: T) -> String
where
    T: Iterator,
    T::Item: std::fmt::Display
{
    let mut res = iter.fold(String::new(), |sum, e| sum + &format!("{} ", e));
    res.pop();
    res
}

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BinaryHeap, HashMap, HashSet};
#[allow(unused_imports)]
use std::collections::btree_map::Entry::{Occupied, Vacant};

macro_rules! make_modint {
    ($MOD: expr, $name: ident) => {
        #[derive(Ord, Hash, Eq, PartialOrd, PartialEq)]
        struct $name {
            val: i64,
        }

        impl $name {
            fn new(x: i64) -> $name {
                let x = x%$MOD;
                $name{val: if x < 0 { x+$MOD } else { x }}
            }

            fn pow(&self, x: i64) -> $name {
                let mut res = $name::new(1);
                let mut tmp = x;
                let mut p = *self;
                while tmp != 0 {
                    if tmp&1 == 1 {
                        res *= p;
                    }
                    tmp = tmp>>1;
                    p = p*p;
                }
                res
            }

            fn inv(&self) -> $name {
                assert!(self.val != 0);
                let mut a = self.val;
                let mut b = $MOD;
                let mut u = 1;
                let mut v = 0;
                use std::mem::swap;
                while b != 0 {
                    let t = a/b;
                    a -= t*b;
                    swap(&mut a, &mut b);
                    u -= t*v;
                    swap(&mut u, &mut v);
                }
                $name::new(u)
            }
        }

        impl std::clone::Clone for $name {
            fn clone(&self) -> $name {
                $name{ val: self.val }
            }
        }

        impl std::marker::Copy for $name { }

        impl std::ops::Add for $name {
            type Output = $name;
            fn add(self, y: $name) -> $name {
                let tmp = self.val+y.val;
                $name{val: if tmp >= $MOD {tmp-$MOD} else {tmp}}
            }
        }

        impl std::ops::Neg for $name {
            type Output = $name;
            fn neg(self) -> $name {
                $name::new(self.val)
            }
        }

        impl std::ops::Sub for $name {
            type Output = $name;
            fn sub(self, other: $name) -> $name{
                let tmp = self.val-other.val;
                $name{val: if tmp < 0 {tmp+$MOD} else {tmp}}
            }
        }

        impl std::ops::Mul for $name {
            type Output = $name;
            fn mul(self, y: $name) -> $name {
                $name{val: (self.val*y.val)%$MOD}
            }
        }

        impl std::ops::Div for $name {
            type Output = $name;
            fn div(self, other: $name) -> $name {
                self*other.inv()
            }
        }

        impl std::fmt::Display for $name {
            fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
                write!(f, "{}", self.val)
            }
        }

        impl std::ops::AddAssign for $name {
        fn add_assign(&mut self, other: $name) {
            *self = *self+other;
        }
        }

        impl std::ops::SubAssign for $name {
            fn sub_assign(&mut self, other: $name) {
                *self = *self-other;
            }
        }

        impl std::ops::MulAssign for $name {
            fn mul_assign(&mut self, other: $name) {
                *self = *self*other;
            }
        }

        impl std::ops::DivAssign for $name {
            fn div_assign(&mut self, other: $name) {
                *self = *self*other.inv();
            }
        }

        impl std::fmt::Debug for $name {
            fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
                write!(f, "{}", self.val)
            }
        }
    }
}

make_modint!(1_000_000_000 + 7, ModInt);

fn mint(x: i64) -> ModInt {
    ModInt::new(x)
}



fn test(n: usize) {
    let gn = [0, 1, 1, 1, 0, 1, 1, 0];
    let mut cnt = HashMap::new();
    for mask in 0..1<<n {
        let mask: Vec<_> = (0..n).map(|i| (mask>>i&1)).collect(); 
        let mut nmask = vec![0; n];
        for i in 0..n {
            nmask[i] = gn[mask[(i as i32-1+n as i32) as usize%n]<<2 | mask[i]<<1 | mask[(i+1)%n]];
        }
        debug!((&mask, &nmask));
        *cnt.entry(nmask).or_insert(0) += 1;
    }
    cnt.iter().for_each(|(k, v)| {
        let ans = solve(n, k).val;
        if ans != *v {
            debug!((k, v));
            debug!(ans);
            panic!("aa");
        }
    });
}

fn solve(n: usize, xs: &Vec<i32>) -> ModInt {
    let gn = [0, 1, 1, 1, 0, 1, 1, 0];
    let mut ans = mint(0);
    for rv in 0..2 {
        for lv in 0..2 {
            let mut dp = [mint(0); 4];
            dp[rv<<1 | lv] = mint(1);
            for i in 0..n {
                let mut next = [mint(0); 4];
                for l in 0..2 {
                    for c in 0..2 {
                        for r in 0..2 {
                            if gn[l<<2 | c<<1 | r] == xs[i] {
                                next[c<<1 | r] += dp[l<<1 | c];
                            }
                        }
                    }
                }
                dp = next;
            }
            ans += dp[rv<<1 | lv];
        }
    }
    ans
}


fn main() {
    use std::io::Write;
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); }
    macro_rules! printfln { () => (writeln!(out).unwrap()); ($($arg:tt)*) => (writeln!(out, $($arg)*).unwrap()); }
    

    // test(4);
    
    solve(3, &vec![0, 1, 1]);
    let n = readl!(usize);
    let xs: Vec<_> = (0..n).map(|_| readl!(i32)).collect();
    printfln!("{}", solve(n, &xs));
}