結果
問題 | No.1410 A lot of Bit Operations |
ユーザー |
![]() |
提出日時 | 2021-02-20 04:12:41 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1 ms / 2,000 ms |
コード長 | 8,492 bytes |
コンパイル時間 | 14,191 ms |
コンパイル使用メモリ | 378,256 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-17 06:48:12 |
合計ジャッジ時間 | 13,299 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 44 |
ソースコード
// ---------- begin Matrix ----------#[allow(dead_code)]mod matrix {use std::ops::{Add, Mul};pub trait SemiRing: Add<Output = Self> + Mul<Output = Self> + Copy {fn zero() -> Self;fn one() -> Self;}pub const SIZE: usize = 2;#[derive(Clone)]pub struct SquareMatrix<T: SemiRing> {buf: [[T; SIZE]; SIZE],}impl<T: SemiRing> SquareMatrix<T> {pub fn zero() -> Self {let z = T::zero();SquareMatrix {buf: [[z; SIZE]; SIZE],}}pub fn identity() -> Self {let mut m = Self::zero();for i in 0..SIZE {m.buf[i][i] = T::one();}m}pub fn set_at(&mut self, i: usize, j: usize, v: T) {self.buf[i][j] = v;}pub fn get_at(&self, i: usize, j: usize) -> T {self.buf[i][j]}pub fn matmul(&self, rhs: &Self) -> Self {let mut res = Self::zero();for (x, a) in res.buf.iter_mut().zip(self.buf.iter()) {for (a, b) in a.iter().zip(rhs.buf.iter()) {for (x, b) in x.iter_mut().zip(b.iter()) {*x = *x + *a * *b;}}}res}pub fn matadd(&self, rhs: &Self) -> Self {let mut c = Self::zero();for (c, (a, b)) in c.buf.iter_mut().zip(self.buf.iter().zip(rhs.buf.iter())) {for (c, (a, b)) in c.iter_mut().zip(a.iter().zip(b.iter())) {*c = *a + *b;}}c}pub fn matpow(&self, mut n: usize) -> Self {let mut t = Self::identity();let mut s = self.clone();while n > 0 {if n & 1 == 1 {t = t.matmul(&s);}s = s.matmul(&s);n >>= 1;}t}}}// ---------- end Matrix ----------// ---------- begin ModInt ----------mod modint {#[allow(dead_code)]pub struct Mod;impl ConstantModulo for Mod {const MOD: u32 = 1_000_000_007;}#[allow(dead_code)]pub struct StaticMod;static mut STATIC_MOD: u32 = 0;impl Modulo for StaticMod {fn modulo() -> u32 {unsafe { STATIC_MOD }}}#[allow(dead_code)]impl StaticMod {pub fn set_modulo(p: u32) {unsafe {STATIC_MOD = p;}}}use std::marker::*;use std::ops::*;pub trait Modulo {fn modulo() -> u32;}pub trait ConstantModulo {const MOD: u32;}impl<T> Modulo for TwhereT: ConstantModulo,{fn modulo() -> u32 {T::MOD}}pub struct ModInt<T>(pub u32, PhantomData<T>);impl<T> Clone for ModInt<T> {fn clone(&self) -> Self {ModInt::new_unchecked(self.0)}}impl<T> Copy for ModInt<T> {}impl<T: Modulo> Add for ModInt<T> {type Output = ModInt<T>;fn add(self, rhs: Self) -> Self::Output {let mut d = self.0 + rhs.0;if d >= T::modulo() {d -= T::modulo();}ModInt::new_unchecked(d)}}impl<T: Modulo> AddAssign for ModInt<T> {fn add_assign(&mut self, rhs: Self) {*self = *self + rhs;}}impl<T: Modulo> Sub for ModInt<T> {type Output = ModInt<T>;fn sub(self, rhs: Self) -> Self::Output {let mut d = T::modulo() + self.0 - rhs.0;if d >= T::modulo() {d -= T::modulo();}ModInt::new_unchecked(d)}}impl<T: Modulo> SubAssign for ModInt<T> {fn sub_assign(&mut self, rhs: Self) {*self = *self - rhs;}}impl<T: Modulo> Mul for ModInt<T> {type Output = ModInt<T>;fn mul(self, rhs: Self) -> Self::Output {let v = self.0 as u64 * rhs.0 as u64 % T::modulo() as u64;ModInt::new_unchecked(v as u32)}}impl<T: Modulo> MulAssign for ModInt<T> {fn mul_assign(&mut self, rhs: Self) {*self = *self * rhs;}}impl<T: Modulo> Neg for ModInt<T> {type Output = ModInt<T>;fn neg(self) -> Self::Output {if self.0 == 0 {Self::zero()} else {Self::new_unchecked(T::modulo() - self.0)}}}impl<T> std::fmt::Display for ModInt<T> {fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {write!(f, "{}", self.0)}}impl<T> std::fmt::Debug for ModInt<T> {fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {write!(f, "{}", self.0)}}impl<T: Modulo> std::str::FromStr for ModInt<T> {type Err = std::num::ParseIntError;fn from_str(s: &str) -> Result<Self, Self::Err> {let val = s.parse::<u32>()?;Ok(ModInt::new(val))}}impl<T: Modulo> From<usize> for ModInt<T> {fn from(val: usize) -> ModInt<T> {ModInt::new_unchecked((val % T::modulo() as usize) as u32)}}impl<T: Modulo> From<u64> for ModInt<T> {fn from(val: u64) -> ModInt<T> {ModInt::new_unchecked((val % T::modulo() as u64) as u32)}}impl<T: Modulo> From<i64> for ModInt<T> {fn from(val: i64) -> ModInt<T> {let m = T::modulo() as i64;ModInt::new((val % m + m) as u32)}}#[allow(dead_code)]impl<T> ModInt<T> {pub fn new_unchecked(d: u32) -> Self {ModInt(d, PhantomData)}pub fn zero() -> Self {ModInt::new_unchecked(0)}pub fn one() -> Self {ModInt::new_unchecked(1)}pub fn is_zero(&self) -> bool {self.0 == 0}}#[allow(dead_code)]impl<T: Modulo> ModInt<T> {pub fn new(d: u32) -> Self {ModInt::new_unchecked(d % T::modulo())}pub fn pow(&self, mut n: u64) -> Self {let mut t = Self::one();let mut s = *self;while n > 0 {if n & 1 == 1 {t *= s;}s *= s;n >>= 1;}t}pub fn inv(&self) -> Self {assert!(self.0 != 0);self.pow(T::modulo() as u64 - 2)}}}// ---------- end ModInt ----------use modint::*;type M = ModInt<Mod>;use matrix::*;type Mat = SquareMatrix<M>;impl SemiRing for M {fn zero() -> Self {M::zero()}fn one() -> Self {M::one()}}fn read() -> (usize, Vec<u8>) {let mut s = String::new();use std::io::Read;std::io::stdin().read_to_string(&mut s).unwrap();let mut it = s.trim().split_whitespace();let n: usize = it.next().unwrap().parse().unwrap();(n, it.next().unwrap().bytes().collect())}fn main() {let (n, s) = read();assert!(n <= 10usize.pow(18));assert!(s.len() == 8 && s.iter().all(|c| *c == b'-' || *c == b'o'));if n == 0 {println!("{}", s.iter().filter(|c| **c == b'o').count());return;}let mut ans = M::zero();for (i, _) in s.iter().enumerate().filter(|p| *p.1 == b'o') {let mut cnt = [0; 2];for k in 0..4 {cnt[(i >> k) & 1] += 1;}let c0 = M::new(cnt[0]);let c1 = M::new(cnt[1]);let mut mat = Mat::zero();mat.set_at(0, 0, M::new(8));mat.set_at(0, 1, c0 - c1);mat.set_at(1, 1, M::new(4));let mat = mat.matpow(n - 1);ans += c0 * (mat.get_at(0, 0) + mat.get_at(1, 0))+ c0 * (mat.get_at(0, 1) + mat.get_at(1, 1));let mut mat = Mat::zero();mat.set_at(0, 0, M::new(8));mat.set_at(0, 1, c1 - c0);mat.set_at(1, 1, M::new(4));let mat = mat.matpow(n - 1);ans += c1 * (mat.get_at(0, 0) + mat.get_at(1, 0))+ c1 * (mat.get_at(0, 1) + mat.get_at(1, 1));}println!("{}", ans);}