// パフォーマスと使いやすさ再優先のためunsafeもunwrapもカジュアルに使う. // 入力はASCII文字以外ダメ. fn main() { let mut input_buffer = String::with_capacity(cp_io::BUFFER_SIZE); let mut output_buffer = Vec::with_capacity(cp_io::BUFFER_SIZE); unsafe { cp_io::input::buf = &mut output_buffer; cp_io::output::buf = &mut input_buffer; } std::thread::Builder::new() .stack_size(104_857_600) .spawn(solve).unwrap() .join().unwrap(); cp_io::output::flush(); } #[macro_use] #[allow(dead_code, non_upper_case_globals, unused_macros)] mod cp_io { pub const BUFFER_SIZE: usize = 8192; #[macro_use] pub mod output { pub const ENABLE_DUMP: bool = true; pub const PRECISION: usize = 10; pub static mut buf: *mut String = 0 as *mut String; macro_rules! p { ($x: expr) => {{ $x.output(); "\n".output(); unsafe { if (*cp_io::output::buf).len() > cp_io::BUFFER_SIZE { flush(); } } }}; ($x: expr, $($y: expr),+) => {{ $x.output(); " ".output(); p!($($y),+); }}; } macro_rules! pf { ($($x: expr),+) => {{ p!($($x),+); flush(); }}; } macro_rules! d { ($($a: expr),+) => { if ENABLE_DUMP { use std::io::*; write!(stderr(), "{}:{}\t", file!(), line!()).unwrap(); d!(A $($a),+); write!(stderr(), " = ").unwrap(); d!(B $($a),+); write!(stderr(), "\n").unwrap(); stderr().flush().unwrap(); } }; (A $x: expr) => { write!(stderr(), "{}", stringify!($x)).unwrap(); }; (A $x: expr, $($y: expr),+) => { write!(stderr(), "{}, ", stringify!($x)).unwrap(); d!(A $($y),+); }; (B $x: expr) => { write!(stderr(), "{:?}", $x).unwrap(); }; (B $x: expr, $($y: expr),+) => { write!(stderr(), "{:?}, ", $x).unwrap(); d!(B $($y),+); }; } pub trait Output { fn output(&self); } macro_rules! output_normal { ($t: ty) => { impl Output for $t { fn output(&self) { unsafe { use std::fmt::Write; write!(&mut *buf, "{}", self).unwrap(); } } } }; ($t: ty, $($u: ty),+) => { output_normal!($t); output_normal!($($u),+); }; } macro_rules! output_float { ($t: ty) => { impl Output for $t { fn output(&self) { unsafe { use std::fmt::Write; write!(&mut *buf, "{:.*}", PRECISION, self).unwrap(); } } } }; ($t: ty, $($u: ty),+) => { output_float!($t); output_float!($($u),+); }; } pub fn flush() { unsafe { print!("{}", *buf); use std::io::*; stdout().flush().unwrap(); (*buf).clear(); } } output_normal!(u8, u16, u32, u64, usize); output_normal!(i8, i16, i32, i64, isize); output_normal!(bool, &'static str, String); output_float!(f32, f64); } pub mod input { pub trait Input { fn input() -> T; } macro_rules! input_primitive { ($t: ty) => { impl Input<$t> for $t { fn input() -> $t { get_word().expect("EOF?").parse() .unwrap_or_else(|e| panic!("Cannot parse {}", e)) } } }; ($t: ty, $($u: ty),+) => { input_primitive!($t); input_primitive!($($u),+); }; } macro_rules! input_tuple { ($($t: ident),*) => { impl< $($t: Input<$t>),* > Input< ( $($t),* ) > for ( $($t),* ) { fn input() -> ( $($t),* ) { ( $( $t::input()),* ) } } }; } input_primitive!(u8, u16, u32, u64, usize); input_primitive!(i8, i16, i32, i64, isize); input_primitive!(bool, String); input_tuple!(A, B); input_tuple!(A, B, C); input_tuple!(A, B, C, D); pub fn get>() -> T { T::input() } pub fn get_vec>(n: usize) -> Vec { (0..n).map(|_| get()).collect() } pub fn get_mat>(r: usize, c: usize) -> Vec> { (0..r).map(|_| get_vec(c)).collect() } pub fn get_vec_char() -> Vec { get_word().unwrap().chars().collect() } pub fn get_mat_char(h: usize) -> Vec> { (0..h).map(|_| get_vec_char()).collect() } pub fn get_line() -> String { get_line_wrapped().unwrap() } fn get_word() -> Option { let mut res = String::with_capacity(18); while let Some(c) = get_u8() { let d = c as char; if !d.is_whitespace() { res.push(d); } else if res.len() != 0 { unget_u8(c); break; } } if res.len() == 0 { None } else { Some(res) } } fn get_line_wrapped() -> Option { let c = get_u8(); if c.is_none() { return None; } let mut line = String::with_capacity(18); line.push(c.unwrap() as char); loop { let c = get_u8(); if c.is_none() || c.unwrap() == b'\n' { // コメントはC++等での仕様 // if c.is_some() { // self.unget_u8(b'\n'); // } return Some(line); } line.push(c.unwrap() as char); } } pub fn has_next() -> bool { loop { let c = get_u8(); if c.is_none() { return false; } let c = c.unwrap(); if !(c as char).is_whitespace() { unget_u8(c); return true; } } } pub static mut buf: *mut Vec = 0 as *mut Vec; fn get_u8() -> Option { unsafe { let b = &mut (*buf); use std::io::{stdin, Read}; if let Some(c) = b.pop() { Some(c as u8) } else { b.resize(super::BUFFER_SIZE, 0); match stdin().read(b) { Ok(l) if l > 0 => { b.truncate(l); b.reverse(); b.pop() } _ => return None, } } } } fn unget_u8(c: u8) { unsafe { (*buf).push(c) } } } } #[allow(unused_imports)] use cp_io::input::*; #[allow(unused_imports)] use cp_io::output::*; use std::*; use std::collections::*; use std::mem::swap; use std::hash::*; use std::fmt::*; use std::cmp::*; struct Node { depth: usize, next: Vec>, } impl Node { fn new(depth: usize) -> Node { let mut n = Vec::with_capacity(26); for _ in 0..26 { n.push(None) } Node { depth: depth, next: n, } } fn insert<'a, I>(&'a mut self, it: I) -> *const Node where I: IntoIterator { let mut it = it.into_iter(); if let Some(c) = it.next() { let d = self.depth; if self.next[*c as usize].is_none() { let p = Box::into_raw(Box::new(Self::new(d + 1))); self.next[*c as usize] = Some(p); } unsafe { (*self.next[*c as usize].unwrap()).insert(it) } } else { self } } } struct Trie { root: *mut Node, } impl Trie { fn new() -> Self { Trie { root: Box::into_raw(Box::new(Node::new(0))), } } fn insert<'a, I>(&'a mut self, it: I) -> *const Node where I: IntoIterator { unsafe { (*self.root).insert(it) } } fn dfs(n: *const Node, a: &mut Vec<*const Node>) { // d!(n); a.push(n); unsafe { for p in &(*n).next { if let &Some(c) = p { Self::dfs(c, a); a.push(n); // d!(c); } } } // d!(n); } fn make_array(&self) -> Vec<*const Node> { let mut a = vec![]; Trie::dfs(self.root, &mut a); a } } struct SparceTable { n: usize, min: Vec> } impl SparceTable { fn new(it: I) -> SparceTable where I: IntoIterator { let it = it.into_iter(); let v = it.collect::>(); let n = v.len(); let mut res = SparceTable { n: n, min: vec![v], }; for i in 0..30 { let w = 1 << i; if n < w*2-1 { break; } let next = (0..n-w*2-1).map(|l| { min(res.min[i][l], res.min[i][l + w]) }).collect(); res.min.push(next); } res } fn rmq(&self, l: usize, r: usize) -> T { let w = r - l; // return self.min[0][0]; // d!(l, r, w); let mut i = 0; while (1 << i) < w { i += 1; } i -= 1; let rr = r - (1 << i); //assert!(r - (1 << i) == rr); min(self.min[i][l], self.min[i][rr]) } } fn solve() { while has_next() { let n = get(); let s: Vec> = get_mat_char(n) .iter().map(|s| s.iter().map(|&c| c as u8 - b'a').collect()) .collect(); // d!(s); let (m, mut x, d): (usize, u64, u64) = get(); let mut i = vec![0usize; m]; let mut j = vec![0usize; m]; for k in 0..m { let n = n as u64; i[k] = ((x / (n - 1)) + 1) as usize; j[k] = ((x % (n - 1)) + 1) as usize; if i[k] > j[k] { swap(&mut i[k], &mut j[k]); } else { j[k] = j[k] + 1; } x = (x + d) % (n * (n - 1)); } let mut trie = Trie::new(); let (index, depth) = { let node = s.iter().map(|s| trie.insert(s.iter())).collect::>(); let pa = trie.make_array(); let mut mp = HashMap::<_, usize>::new(); for i in 0..pa.len() { mp.entry(pa[i]).or_insert(i); } let index = (0..n).map(|i| mp[&node[i]]).collect::>(); let da = pa.iter().map(|i| unsafe { (**i).depth }).collect::>(); (index, da) }; let rmq = SparceTable::<_>::new(depth.iter()); let calc = |i: usize, j: usize| { let (l, r) = if index[i] < index[j] { (index[i], index[j]) } else { (index[j], index[i]) }; rmq.rmq(l, r + 1) }; let ans = i.iter().zip(j.iter()).fold(0, |acc, (&i, &j)| { acc + calc(i - 1, j - 1) }); p!(ans); } }