結果
| 問題 |
No.663 セルオートマトンの逆操作
|
| コンテスト | |
| ユーザー |
 sntea
|
| 提出日時 | 2018-04-20 18:21:03 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1 ms / 2,000 ms |
| コード長 | 6,808 bytes |
| コンパイル時間 | 13,634 ms |
| コンパイル使用メモリ | 387,496 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-06-27 05:08:22 |
| 合計ジャッジ時間 | 14,553 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 29 |
コンパイルメッセージ
warning: unused macro definition: `printf`
--> src/main.rs:247:18
|
247 | macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); }
| ^^^^^^
|
= note: `#[warn(unused_macros)]` on by default
warning: method `pow` is never used
--> src/main.rs:71:16
|
65 | impl $name {
| ---------- method in this implementation
...
71 | fn pow(&self, x: i64) -> $name {
| ^^^
...
186 | make_modint!(1_000_000_000 + 7, ModInt);
| --------------------------------------- in this macro invocation
|
= note: `#[warn(dead_code)]` on by default
= note: this warning originates in the macro `make_modint` (in Nightly builds, run with -Z macro-backtrace for more info)
warning: function `test` is never used
--> src/main.rs:194:4
|
194 | fn test(n: usize) {
| ^^^^
ソースコード
#[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));
}