結果
| 問題 | No.599 回文かい |
| ユーザー |
 sntea
|
| 提出日時 | 2018-02-05 22:32:28 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 9,009 bytes |
| コンパイル時間 | 12,597 ms |
| コンパイル使用メモリ | 386,976 KB |
| 最終ジャッジ日時 | 2024-11-14 20:20:39 |
| 合計ジャッジ時間 | 13,297 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
warning: unused macro definition: `readlvec`
--> src/main.rs:29:14
|
29 | macro_rules! readlvec {
| ^^^^^^^^
|
= note: `#[warn(unused_macros)]` on by default
warning: unused macro definition: `debug`
--> src/main.rs:39:14
|
39 | macro_rules! debug {
| ^^^^^
warning: type `mint0` should have an upper camel case name
--> src/main.rs:220:31
|
220 | make_modint!(1_000_000_000+7, mint0);
| ^^^^^ help: convert the identifier to upper camel case: `Mint0`
|
= note: `#[warn(non_camel_case_types)]` on by default
warning: type `mint1` should have an upper camel case name
--> src/main.rs:221:31
|
221 | make_modint!(1_000_000_000+9, mint1);
| ^^^^^ help: convert the identifier to upper camel case: `Mint1`
warning: type `mint2` should have an upper camel case name
--> src/main.rs:222:27
|
222 | make_modint!(999_999_937, mint2);
| ^^^^^ help: convert the identifier to upper camel case: `Mint2`
warning: unused variable: `i`
--> src/main.rs:283:14
|
283 | for (i, &e) in s.as_bytes().iter().enumerate() {
| ^ help: if this is intentional, prefix it with an underscore: `_i`
|
= note: `#[warn(unused_variables)]` on by default
warning: unused variable: `i`
--> src/main.rs:301:13
|
301 | for i in 0..n {
| ^ help: if this is intentional, prefix it with an underscore: `_i`
error[E0502]: cannot borrow `dp` as immutable because it is also borrowed as mutable
--> src/main.rs:354:26
|
354 | dp[i] += dp[j];
| ---------^^---
| | |
| | immutable borrow occurs here
| mutable borrow occurs here
| mutable borrow later used here
|
help: try adding a local storing this...
--> src/main.rs:354:28
|
354 |
ソースコード
// use std::ops::{Index, IndexMut};// use std::cmp::{Ordering, min, max};// use std::collections::{BinaryHeap, BTreeMap};// use std::collections::btree_map::Entry::{Occupied, Vacant};// use std::clone::Clone;fn getline() -> String{let mut res = String::new();std::io::stdin().read_line(&mut res).ok();res}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(),)*)}};}macro_rules! readlvec {($t: ty) => {{let s = getline();let iter = s.trim().split(' ');iter.map(|x| x.parse().unwrap()).collect::<Vec<$t>>()}}}macro_rules! debug {($x: expr) => {println!("{}: {:?}", stringify!($x), $x)}}fn printiter<'a, T>(v: &'a T)where&'a T: std::iter::IntoIterator,<&'a T as std::iter::IntoIterator>::Item: std::fmt::Display {for (i,e) in v.into_iter().enumerate() {if i != 0 {print!(" ");}print!("{}", e);}println!("");}struct ContestPrinter {s: String,}impl ContestPrinter {fn new() -> ContestPrinter {ContestPrinter {s: String::new(),}}fn print<T>(&mut self, x: T)where T: std::fmt::Display {self.s.push_str(format!("{}", x).as_str());}fn println<T>(&mut self, x: T)where T: std::fmt::Display {self.s.push_str(format!("{}\n", x).as_str());}}impl std::ops::Drop for ContestPrinter {fn drop(&mut self) {print!("{}", self.s);}}macro_rules! make_modint {($MOD: expr, $name: ident) => {#[derive(Eq, PartialEq, PartialOrd, Ord, Hash)]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)}make_modint!(1_000_000_000+7, mint0);make_modint!(1_000_000_000+9, mint1);make_modint!(999_999_937, mint2);struct Random {x: i32,y: i32,z: i32,w: i32,t: i32,}impl Random {fn new() -> Random {Random {x: 123456789,y: 362436069,z: 521288629,w: 886751233,t: 1,}}fn next(&mut self) -> i32 {self.t = self.x^(self.x << 11);self.x = self.y;self.y = self.z;self.z = self.w;self.w = (self.w ^ (self.w>>19)) ^ (self.t ^ (self.t>>8));self.w&0x7fffffff}}// construct: O(n), Query: O(1)struct RolllingHash {b0: mint0,b1: mint1,b2: mint2,table: Vec<(mint0, mint1, mint2)>,power_inv: Vec<(mint0, mint1, mint2)>}impl RolllingHash {fn new(s: &str) -> RolllingHash {let n = s.len();let mut table = Vec::with_capacity(n+1);let mut rnd = Random::new();let b0 = mint0::new(rnd.next() as i64);let b1 = mint1::new(rnd.next() as i64);let b2 = mint2::new(rnd.next() as i64);let mut t0 = mint0::new(1);let mut t1 = mint1::new(1);let mut t2 = mint2::new(1);table.push((mint0::new(0), mint1::new(0), mint2::new(0)));let mut val0 = mint0::new(0);let mut val1 = mint1::new(0);let mut val2 = mint2::new(0);for (i, &e) in s.as_bytes().iter().enumerate() {val0 += mint0::new(e as i64)*t0;val1 += mint1::new(e as i64)*t1;val2 += mint2::new(e as i64)*t2;table.push((val0, val1, val2));t0 *= b0;t1 *= b1;t2 *= b2;}let mut powers = Vec::with_capacity(n+1);let mut t0 = mint0::new(1);let mut t1 = mint1::new(1);let mut t2 = mint2::new(1);let b0_inv = b0.inv();let b1_inv = b1.inv();let b2_inv = b2.inv();powers.push((t0, t1, t2));for i in 0..n {t0 *= b0_inv;t1 *= b1_inv;t2 *= b2_inv;powers.push((t0, t1, t2));}RolllingHash {b0: b0,b1: b1,b2: b2,table: table,power_inv: powers,}}fn query(&self, l: usize, r: usize) -> (mint0, mint1, mint2) {let (lval0, lval1, lval2) = self.table[l];let (rval0, rval1, rval2) = self.table[r];let (inv0, inv1, inv2) = self.power_inv[l];((rval0-lval0)*inv0, (rval1-lval1)*inv1, (rval2-lval2)*inv2)}}fn main() {let mut printer = ContestPrinter::new();let s: Vec<_> = readl!(String).into_bytes();let (l, r): (String, String) = {let mut l = Vec::new();let mut r = Vec::new();for i in 0..s.len()/2 {l.push(s[i]);}let m = (s.len()+1)/2;for i in 0..s.len()/2 {r.push(s[m+i]);}(l.into_iter().map(|x| x as char).collect(),r.into_iter().map(|x| x as char).collect())};// debug!(l); debug!(r);let lr = RolllingHash::new(l.as_str());let rr = RolllingHash::new(r.as_str());let mut dp = vec![mint(1); s.len()/2+1];for i in 1..s.len()/2+1 {for j in 0..i {if rr.query(j, i) == lr.query(s.len()/2-i, s.len()/2-j) {// debug!(j); debug!(i);dp[i] += dp[j];}}}printer.println(dp.last().unwrap());}