結果
| 問題 |
No.1810 RGB Biscuits
|
| ユーザー |
 Strorkis
|
| 提出日時 | 2022-01-15 18:31:40 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 49 ms / 2,000 ms |
| コード長 | 11,677 bytes |
| コンパイル時間 | 15,604 ms |
| コンパイル使用メモリ | 379,800 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-11-21 21:31:13 |
| 合計ジャッジ時間 | 16,673 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 20 |
ソースコード
pub mod input {
pub trait Readable {
type Output;
fn read<R: std::io::BufRead>(r: &mut R) -> Self::Output;
}
macro_rules! impl_readable_for_int {
($($t:ty)*) => ($(impl Readable for $t {
type Output = $t;
#[inline]
fn read<R: std::io::BufRead>(r: &mut R) -> Self::Output {
let mut is_positive = true;
let mut is_empty = true;
let mut is_only_sign = true;
let mut result: Self::Output = 0;
loop {
let buf = match r.fill_buf() {
Ok(buf) => buf,
Err(e) if e.kind() == std::io::ErrorKind::Interrupted => continue,
Err(e) => panic!("{}", e),
};
let (done, used, mut buf) = match buf.iter().position(u8::is_ascii_whitespace) {
Some(i) => (i > 0 || !is_empty, i + 1, &buf[..i]),
None => (buf.is_empty(), buf.len(), buf),
};
if is_empty && buf.len() > 0 {
is_empty = false;
buf = match buf[0] {
b'+' => &buf[1..],
b'-' => {
is_positive = false;
&buf[1..]
}
_ => buf,
};
}
if buf.len() > 0 {
is_only_sign = false;
}
if is_positive {
for &c in buf {
let x = (c as char).to_digit(10).expect("InvalidDigit");
result = result.checked_mul(10).expect("PosOverflow");
result = result.checked_add(x as $t).expect("PosOverflow");
}
} else {
for &c in buf {
let x = (c as char).to_digit(10).expect("InvalidDigit");
result = result.checked_mul(10).expect("NegOverflow");
result = result.checked_sub(x as $t).expect("NegOverflow");
}
}
r.consume(used);
if done {
if is_empty {
panic!("Empty");
}
if is_only_sign {
panic!("InvalidDigit");
}
return result;
}
}
}
})*)
}
impl_readable_for_int! { i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize }
pub mod marker {
use super::Readable;
pub enum Usize1 {}
impl Readable for Usize1 {
type Output = usize;
#[inline]
fn read<R: std::io::BufRead>(r: &mut R) -> Self::Output {
usize::read(r).checked_sub(1).expect("NegOverflow")
}
}
pub enum Bytes {}
impl Readable for Bytes {
type Output = Vec<u8>;
#[inline]
fn read<R: std::io::BufRead>(r: &mut R) -> Self::Output {
let mut result = Vec::new();
loop {
let buf = match r.fill_buf() {
Ok(buf) => buf,
Err(e) if e.kind() == std::io::ErrorKind::Interrupted => continue,
Err(e) => panic!("{}", e),
};
let (done, used, buf) = match buf.iter().position(u8::is_ascii_whitespace) {
Some(i) => (i > 0 || !result.is_empty(), i + 1, &buf[..i]),
None => (buf.is_empty(), buf.len(), buf),
};
result.extend_from_slice(buf);
r.consume(used);
if done { return result; }
}
}
}
}
impl Readable for String {
type Output = String;
#[inline]
fn read<R: std::io::BufRead>(r: &mut R) -> Self::Output {
String::from_utf8(marker::Bytes::read(r)).unwrap()
}
}
macro_rules! impl_readable_for_float {
($($t:ty)*) => ($(impl Readable for $t {
type Output = $t;
#[inline]
fn read<R: std::io::BufRead>(r: &mut R) -> Self::Output {
String::read(r).parse().unwrap()
}
})*)
}
impl_readable_for_float! { f32 f64 }
macro_rules! impl_readable_for_tuple {
($head:ident, $($tail:ident),*) => {
impl<$head, $($tail),*> Readable for ($head, $($tail),*)
where
$head: Readable,
$($tail: Readable),*,
{
type Output = (
<$head as Readable>::Output,
$(<$tail as Readable>::Output),*,
);
#[inline]
fn read<R: std::io::BufRead>(r: &mut R) -> Self::Output {
(<$head>::read(r), $(<$tail>::read(r)),*)
}
}
impl_readable_for_tuple!($($tail),*);
};
($head:ident) => {};
}
impl_readable_for_tuple!(A, B, C, D, E, F, G, H, I, J);
#[macro_export]
macro_rules! read {
($r:expr, [$t:tt; $n:expr]) => {{
<[_; $n]>::try_from(read!($r, ($t; $n)).as_slice()).unwrap()
}};
($r:expr, ($t:tt)) => {
read!($r, ($t; read!($r, usize)))
};
($r:expr, ($t:tt; $n:expr)) => {
(0..$n).map(|_| read!($r, $t)).collect::<Vec<_>>()
};
($r:expr, $t:ty) => {
<$t>::read($r)
};
}
#[macro_export]
macro_rules! input {
($r:expr, $($($v:ident)* : $t:tt),* $(,)?) => {$(
let $($v)* = read!($r, $t);
)*};
}
}
pub mod matrix {
use std::ops::{Add, Mul};
pub trait MatrixHelper: Add<Output = Self> + Mul<Output = Self> + Copy {
fn zero() -> Self;
fn one() -> Self;
}
#[derive(Clone, Debug)]
pub struct Matrix<M> {
n: usize, m: usize, a: Vec<Vec<M>>,
}
impl<M: MatrixHelper> Matrix<M> {
pub fn new(n: usize, m: usize, a: Vec<Vec<M>>) -> Self {
Matrix {
n, m, a
}
}
pub fn zero(n: usize, m: usize) -> Self {
Matrix::new(n, m, vec![vec![M::zero(); m]; n])
}
pub fn identity(n: usize) -> Self {
let mut res = Matrix::zero(n, n);
for i in 0..n {
res.a[i][i] = M::one();
}
res
}
pub fn get(&self, i: usize, j: usize) -> &M {
&self.a[i][j]
}
pub fn set(&mut self, i: usize, j: usize, m: M) {
self.a[i][j] = m;
}
pub fn mul(&self, other: &Self) -> Self {
assert!(self.m == other.n);
let mut res = Matrix::zero(self.n, other.m);
for (res, b) in res.a.iter_mut().zip(self.a.iter()) {
for (&b, c) in b.iter().zip(other.a.iter()) {
for (res, &c) in res.iter_mut().zip(c.iter()) {
*res = *res + b * c;
}
}
}
res
}
pub fn pow(&self, mut n: u64) -> Self {
assert!(self.n == self.m);
let mut res = Matrix::identity(self.n);
let mut x = self.clone();
while n > 0 {
if n & 1 == 1 {
res = res.mul(&x);
}
x = x.mul(&x);
n >>= 1;
}
res
}
}
}
pub mod mod_int {
use std::fmt;
use std::ops::*;
#[derive(Clone, Copy, Debug, Default)]
pub struct ModInt(u64);
impl ModInt {
const MOD: u64 = 1_000_000_007;
pub fn new(mut x: u64) -> Self {
if x >= Self::MOD {
x %= Self::MOD;
}
Self(x)
}
pub fn zero() -> Self {
Self(0)
}
pub fn one() -> Self {
Self(1)
}
}
impl From<usize> for ModInt {
fn from(x: usize) -> Self {
Self::new(x as u64)
}
}
impl From<i64> for ModInt {
fn from(mut x: i64) -> Self {
let m = Self::MOD as i64;
if x.abs() >= m {
x %= m;
}
if x < 0 {
x += m
}
Self::new(x as u64)
}
}
impl Add for ModInt {
type Output = Self;
fn add(self, other: Self) -> Self {
let mut x = self.0 + other.0;
if x >= Self::MOD {
x -= Self::MOD;
}
Self(x)
}
}
impl AddAssign for ModInt {
fn add_assign(&mut self, other: Self) {
*self = *self + other;
}
}
impl Sub for ModInt {
type Output = Self;
fn sub(mut self, other: Self) -> Self {
if self.0 < other.0 {
self.0 += Self::MOD;
}
Self(self.0 - other.0)
}
}
impl SubAssign for ModInt {
fn sub_assign(&mut self, other: Self) {
*self = *self - other;
}
}
impl Mul for ModInt {
type Output = Self;
fn mul(self, other: Self) -> Self {
Self::new(self.0 * other.0)
}
}
impl MulAssign for ModInt {
fn mul_assign(&mut self, other: Self) {
*self = *self * other;
}
}
impl fmt::Display for ModInt {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.0)
}
}
impl ModInt {
pub fn pow(mut self, mut n: u64) -> Self {
let mut res = Self::one();
while n > 0 {
if n & 1 == 1 {
res *= self;
}
self *= self;
n >>= 1;
}
res
}
pub fn inv(self) -> Self {
self.pow(Self::MOD - 2)
}
}
}
use input::Readable;
use matrix::{Matrix, MatrixHelper};
use mod_int::ModInt;
impl MatrixHelper for ModInt {
fn zero() -> Self {
Self::zero()
}
fn one() -> Self {
Self::one()
}
}
fn run<R: std::io::BufRead, W: std::io::Write>(reader: &mut R, writer: &mut W) {
input! {
reader,
a: u64, b: u64,
}
let mut m0 = Matrix::zero(6, 1);
m0.set(0, 0, ModInt::one());
m0.set(1, 0, ModInt::one());
let mut m = Matrix::zero(6, 6);
m.set(3, 0, ModInt::one());
m.set(4, 1, ModInt::one());
m.set(5, 0, ModInt::new(a));
m.set(5, 1, ModInt::new(b));
m.set(1, 3, ModInt::one());
m.set(0, 5, ModInt::one());
for _ in 0..read!(reader, usize) {
let t = read!(reader, u64);
let res = m.pow(t).mul(&m0);
let mut ans = ModInt::zero();
for i in 0..6 {
ans += *res.get(i, 0);
}
writeln!(writer, "{}", ans).ok();
}
}
fn main() {
let (stdin, stdout) = (std::io::stdin(), std::io::stdout());
let ref mut reader = std::io::BufReader::new(stdin.lock());
let ref mut writer = std::io::BufWriter::new(stdout.lock());
run(reader, writer);
}