結果
| 問題 | No.2017 Mod7 Parade |
| ユーザー |
 cotton_fn_
|
| 提出日時 | 2022-07-22 23:27:55 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 48 ms / 2,000 ms |
| コード長 | 20,624 bytes |
| コンパイル時間 | 13,169 ms |
| コンパイル使用メモリ | 387,652 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-07-04 08:19:24 |
| 合計ジャッジ時間 | 14,969 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,816 KB |
| testcase_01 | AC | 1 ms
6,816 KB |
| testcase_02 | AC | 1 ms
6,816 KB |
| testcase_03 | AC | 38 ms
6,944 KB |
| testcase_04 | AC | 26 ms
6,944 KB |
| testcase_05 | AC | 19 ms
6,944 KB |
| testcase_06 | AC | 41 ms
6,940 KB |
| testcase_07 | AC | 6 ms
6,940 KB |
| testcase_08 | AC | 24 ms
6,940 KB |
| testcase_09 | AC | 10 ms
6,944 KB |
| testcase_10 | AC | 24 ms
6,940 KB |
| testcase_11 | AC | 33 ms
6,940 KB |
| testcase_12 | AC | 29 ms
6,940 KB |
| testcase_13 | AC | 48 ms
6,944 KB |
| testcase_14 | AC | 48 ms
6,940 KB |
| testcase_15 | AC | 48 ms
6,940 KB |
| testcase_16 | AC | 48 ms
6,940 KB |
| testcase_17 | AC | 48 ms
6,940 KB |
| testcase_18 | AC | 35 ms
6,940 KB |
| testcase_19 | AC | 8 ms
6,944 KB |
| testcase_20 | AC | 1 ms
6,944 KB |
ソースコード
#![allow(unused_imports)]
use input::*;
use std::{
collections::*,
io::{self, BufWriter, Write},
};
def_mint!(7);
fn run<I: Input, O: Write>(mut ss: I, mut out: O) {
use mod_int::*;
let k: usize = ss.parse();
let dl: Vec<(u32, i64)> = ss.seq().take(k).collect();
let mut ans = 0;
let mut a = [0; 7];
a[0] = 1;
for (d, l) in dl {
let t = Mint::from(10).pow(l).get() as usize;
let r = ((Mint::from(10).pow(l) - mint(1)) / mint(9) * mint(d)).get() as usize;
let mut b = a;
for i in 0..7 {
b[(i * t + r) % 7] += a[i];
}
for i in 0..7 {
b[i] %= 1000000007;
}
a = b;
}
for i in 0..7 {
ans += a[i] * i;
ans %= 1000000007;
}
wln!(out, "{}", ans)
}
fn main() {
let stdin = io::stdin();
let ss = SplitWs::new(stdin.lock());
let stdout = io::stdout();
let out = BufWriter::new(stdout.lock());
run(ss, out);
}
pub mod mod_int {
use std::{
cmp,
fmt::{self, Debug, Display},
hash::Hash,
iter::{Product, Sum},
marker::PhantomData,
mem,
ops::*,
};
pub struct ModInt<M> {
x: u32,
marker: PhantomData<*const M>,
}
pub trait Modulo {
fn modulo() -> u32;
}
impl<M> ModInt<M> {
pub fn new(x: u32) -> Self {
Self {
x,
marker: PhantomData,
}
}
pub fn get(self) -> u32 {
self.x
}
}
impl<M: Modulo> ModInt<M> {
pub fn modulo() -> u32 {
M::modulo()
}
pub fn normalize(self) -> Self {
Self::new(self.x % M::modulo())
}
pub fn inv(self) -> Self {
assert_ne!(self.get(), 0);
self.pow(M::modulo() - 2)
}
pub fn twice(self) -> Self {
self + self
}
pub fn half(self) -> Self {
if self.x & 1 == 0 {
Self::new(self.x >> 1)
} else {
Self::new((self.x >> 1) + ((Self::modulo() + 1) >> 1))
}
}
}
impl<M> Clone for ModInt<M> {
fn clone(&self) -> Self {
Self::new(self.x)
}
}
impl<M> Copy for ModInt<M> {}
impl<M: Modulo> Neg for ModInt<M> {
type Output = Self;
fn neg(self) -> Self {
Self::new(if self.x != 0 { M::modulo() - self.x } else { 0 })
}
}
impl<M: Modulo> Neg for &ModInt<M> {
type Output = ModInt<M>;
fn neg(self) -> Self::Output {
-(*self)
}
}
impl<M: Modulo> Add for ModInt<M> {
type Output = Self;
fn add(self, rhs: Self) -> Self {
let x = self.x + rhs.x;
Self::new(if x < M::modulo() { x } else { x - M::modulo() })
}
}
impl<M: Modulo> Sub for ModInt<M> {
type Output = Self;
fn sub(self, rhs: Self) -> Self {
let x = if self.x >= rhs.x {
self.x - rhs.x
} else {
M::modulo() + self.x - rhs.x
};
Self::new(x)
}
}
impl<M: Modulo> Mul for ModInt<M> {
type Output = Self;
fn mul(self, rhs: Self) -> Self {
let x = (self.x as u64 * rhs.x as u64) % M::modulo() as u64;
Self::new(x as u32)
}
}
impl<M: Modulo> Div for ModInt<M> {
type Output = Self;
#[allow(clippy::suspicious_arithmetic_impl)]
fn div(self, rhs: Self) -> Self {
self * rhs.inv()
}
}
macro_rules! biops {
($ Op : ident , $ op : ident , $ OpAssign : ident , $ op_assign : ident) => {
impl<M: Modulo> $Op<&Self> for ModInt<M> {
type Output = Self;
fn $op(self, rhs: &Self) -> Self {
self.$op(*rhs)
}
}
impl<M: Modulo> $Op<ModInt<M>> for &ModInt<M> {
type Output = ModInt<M>;
fn $op(self, rhs: ModInt<M>) -> ModInt<M> {
(*self).$op(rhs)
}
}
impl<M: Modulo> $Op for &ModInt<M> {
type Output = ModInt<M>;
fn $op(self, rhs: Self) -> ModInt<M> {
(*self).$op(*rhs)
}
}
impl<M: Modulo> $OpAssign for ModInt<M> {
fn $op_assign(&mut self, rhs: Self) {
*self = self.$op(rhs);
}
}
impl<M: Modulo> $OpAssign<&Self> for ModInt<M> {
fn $op_assign(&mut self, rhs: &Self) {
*self = self.$op(rhs);
}
}
};
}
biops!(Add, add, AddAssign, add_assign);
biops!(Sub, sub, SubAssign, sub_assign);
biops!(Mul, mul, MulAssign, mul_assign);
biops!(Div, div, DivAssign, div_assign);
impl<M: Modulo> Sum for ModInt<M> {
fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(ModInt::new(0), |x, y| x + y)
}
}
impl<M: Modulo> Product for ModInt<M> {
fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(ModInt::new(1), |x, y| x * y)
}
}
macro_rules! fold {
($ Trait : ident , $ f : ident) => {
impl<'a, M: Modulo + 'a> $Trait<&'a ModInt<M>> for ModInt<M> {
fn $f<I: Iterator<Item = &'a ModInt<M>>>(iter: I) -> Self {
iter.copied().$f()
}
}
};
}
fold!(Sum, sum);
fold!(Product, product);
pub trait Pow<Exp> {
fn pow(self, exp: Exp) -> Self;
}
macro_rules! pow {
($ uty : ident , $ ity : ident) => {
impl<M: Modulo> Pow<$uty> for ModInt<M> {
fn pow(self, mut exp: $uty) -> Self {
if exp == 0 {
return ModInt::new(1);
}
let mut res = ModInt::new(1);
let mut base = self;
while exp > 1 {
if exp & 1 != 0 {
res *= base;
}
exp >>= 1;
base *= base;
}
base * res
}
}
impl<M: Modulo> Pow<$ity> for ModInt<M> {
fn pow(self, exp: $ity) -> Self {
if exp >= 0 {
self.pow(exp as $uty)
} else {
self.inv().pow(-exp as $uty)
}
}
}
};
}
macro_rules ! impls { ($ m : ident , $ ($ uty : ident , $ ity : ident) ,*) => { $ ($ m ! ($ uty , $ ity) ;) * } ; }
impls!(pow, usize, isize, u8, i8, u16, i16, u32, i32, u64, i64, u128, i128);
impl<M> Default for ModInt<M> {
fn default() -> Self {
Self::new(0)
}
}
impl<M> PartialEq for ModInt<M> {
fn eq(&self, other: &Self) -> bool {
self.x == other.x
}
}
impl<M> Eq for ModInt<M> {}
impl<M> PartialOrd for ModInt<M> {
fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
self.x.partial_cmp(&other.x)
}
}
impl<M> Ord for ModInt<M> {
fn cmp(&self, other: &Self) -> cmp::Ordering {
self.x.cmp(&other.x)
}
}
impl<M> Hash for ModInt<M> {
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
self.x.hash(state)
}
}
macro_rules! from_uint {
($ ty : ident) => {
impl<M: Modulo> From<$ty> for ModInt<M> {
fn from(x: $ty) -> Self {
if mem::size_of::<$ty>() <= 4 {
if ($ty::max_value() as u32) < M::modulo() {
Self::new(x as u32)
} else {
Self::new(x as u32).normalize()
}
} else {
Self::new((x % M::modulo() as $ty) as u32)
}
}
}
};
}
macro_rules ! impls { ($ m : ident , $ ($ ty : ident) ,*) => { $ ($ m ! ($ ty) ;) * } ; }
impls!(from_uint, usize, u8, u16, u32, u64, u128);
macro_rules! from_small_int {
($ ty : ident) => {
impl<M: Modulo> From<$ty> for ModInt<M> {
fn from(x: $ty) -> Self {
let mut x = x as i32;
if x >= 0 {
Self::from(x as u32)
} else {
while x < 0 {
x += M::modulo() as i32;
}
Self::new(x as u32)
}
}
}
};
}
impls!(from_small_int, i8, i16, i32);
impl<M> Display for ModInt<M> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
Display::fmt(&self.x, f)
}
}
impl<M> Debug for ModInt<M> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
Debug::fmt(&self.x, f)
}
}
#[macro_export]
macro_rules! def_mint {
($ modulo : expr) => {
#[derive(Clone, Copy, PartialEq, Eq, Default, Debug)]
pub struct MintModulo;
impl crate::mod_int::Modulo for MintModulo {
fn modulo() -> u32 {
$modulo
}
}
pub type Mint = crate::mod_int::ModInt<MintModulo>;
pub fn mint(x: u32) -> Mint {
x.into()
}
};
}
}
pub mod input {
use std::{
io::{self, prelude::*},
marker::PhantomData,
mem,
};
pub trait Input {
fn bytes(&mut self) -> &[u8];
fn bytes_vec(&mut self) -> Vec<u8> {
self.bytes().to_vec()
}
fn str(&mut self) -> &str {
std::str::from_utf8(self.bytes()).unwrap()
}
fn parse<T: Parse>(&mut self) -> T {
self.parse_with(DefaultParser)
}
fn parse_with<T>(&mut self, mut parser: impl Parser<T>) -> T {
parser.parse(self)
}
fn seq<T: Parse>(&mut self) -> Seq<T, Self, DefaultParser> {
self.seq_with(DefaultParser)
}
fn seq_with<T, P: Parser<T>>(&mut self, parser: P) -> Seq<T, Self, P> {
Seq {
input: self,
parser,
marker: PhantomData,
}
}
fn collect<T: Parse, C: std::iter::FromIterator<T>>(&mut self, n: usize) -> C {
self.seq().take(n).collect()
}
}
impl<T: Input> Input for &mut T {
fn bytes(&mut self) -> &[u8] {
(**self).bytes()
}
}
pub trait Parser<T> {
fn parse<I: Input + ?Sized>(&mut self, s: &mut I) -> T;
}
impl<T, P: Parser<T>> Parser<T> for &mut P {
fn parse<I: Input + ?Sized>(&mut self, s: &mut I) -> T {
(**self).parse(s)
}
}
pub trait Parse {
fn parse<I: Input + ?Sized>(s: &mut I) -> Self;
}
pub struct DefaultParser;
impl<T: Parse> Parser<T> for DefaultParser {
fn parse<I: Input + ?Sized>(&mut self, s: &mut I) -> T {
T::parse(s)
}
}
pub struct Seq<'a, T, I: ?Sized, P> {
input: &'a mut I,
parser: P,
marker: PhantomData<*const T>,
}
impl<'a, T, I: Input + ?Sized, P: Parser<T>> Iterator for Seq<'a, T, I, P> {
type Item = T;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
Some(self.input.parse_with(&mut self.parser))
}
fn size_hint(&self) -> (usize, Option<usize>) {
(!0, None)
}
}
impl Parse for char {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
let s = s.bytes();
debug_assert_eq!(s.len(), 1);
*s.first().expect("zero length") as char
}
}
macro_rules ! tuple { ($ ($ T : ident) ,*) => { impl <$ ($ T : Parse) ,*> Parse for ($ ($ T ,) *) { # [inline] # [allow (unused_variables)] # [allow (clippy :: unused_unit)] fn parse < I : Input + ? Sized > (s : & mut I) -> Self { ($ ($ T :: parse (s) ,) *) } } } ; }
tuple!();
tuple!(A);
tuple!(A, B);
tuple!(A, B, C);
tuple!(A, B, C, D);
tuple!(A, B, C, D, E);
tuple!(A, B, C, D, E, F);
tuple!(A, B, C, D, E, F, G);
#[cfg(feature = "newer")]
impl<T: Parse, const N: usize> Parse for [T; N] {
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
use std::{mem::MaybeUninit, ptr};
struct Guard<T, const N: usize> {
arr: [MaybeUninit<T>; N],
i: usize,
}
impl<T, const N: usize> Drop for Guard<T, N> {
fn drop(&mut self) {
unsafe {
ptr::drop_in_place(&mut self.arr[..self.i] as *mut _ as *mut [T]);
}
}
}
let mut g = Guard::<T, N> {
arr: unsafe { MaybeUninit::uninit().assume_init() },
i: 0,
};
while g.i < N {
g.arr[g.i] = MaybeUninit::new(s.parse());
g.i += 1;
}
unsafe { mem::transmute_copy(&g.arr) }
}
}
macro_rules! uint {
($ ty : ty) => {
impl Parse for $ty {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
let s = s.bytes();
s.iter().fold(0, |x, d| 10 * x + (0xf & d) as $ty)
}
}
};
}
macro_rules! int {
($ ty : ty) => {
impl Parse for $ty {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
let f = |s: &[u8]| {
s.iter()
.fold(0 as $ty, |x, d| (10 * x).wrapping_add((0xf & d) as $ty))
};
let s = s.bytes();
if let Some((b'-', s)) = s.split_first() {
f(s).wrapping_neg()
} else {
f(s)
}
}
}
};
}
macro_rules! float {
($ ty : ty) => {
impl Parse for $ty {
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
const POW: [$ty; 18] = [
1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13,
1e14, 1e15, 1e16, 1e17,
];
let s = s.bytes();
let (minus, s) = if let Some((b'-', s)) = s.split_first() {
(true, s)
} else {
(false, s)
};
let (int, fract) = if let Some(p) = s.iter().position(|c| *c == b'.') {
(&s[..p], &s[p + 1..])
} else {
(s, &[][..])
};
let x = int
.iter()
.chain(fract)
.fold(0u64, |x, d| 10 * x + (0xf & *d) as u64);
let x = x as $ty;
let x = if minus { -x } else { x };
let exp = fract.len();
if exp == 0 {
x
} else if let Some(pow) = POW.get(exp) {
x / pow
} else {
x / (10.0 as $ty).powi(exp as i32)
}
}
}
};
}
macro_rules! from_bytes {
($ ty : ty) => {
impl Parse for $ty {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
s.bytes().into()
}
}
};
}
macro_rules! from_str {
($ ty : ty) => {
impl Parse for $ty {
#[inline]
fn parse<I: Input + ?Sized>(s: &mut I) -> Self {
s.str().into()
}
}
};
}
macro_rules ! impls { ($ m : ident , $ ($ ty : ty) ,*) => { $ ($ m ! ($ ty) ;) * } ; }
impls!(uint, usize, u8, u16, u32, u64, u128);
impls!(int, isize, i8, i16, i32, i64, i128);
impls!(float, f32, f64);
impls!(from_bytes, Vec<u8>, Box<[u8]>);
impls!(from_str, String);
#[derive(Clone)]
pub struct SplitWs<T> {
src: T,
buf: Vec<u8>,
pos: usize,
len: usize,
}
const BUF_SIZE: usize = 1 << 26;
impl<T: Read> SplitWs<T> {
pub fn new(src: T) -> Self {
Self {
src,
buf: vec![0; BUF_SIZE],
pos: 0,
len: 0,
}
}
#[inline(always)]
fn peek(&self) -> &[u8] {
unsafe { self.buf.get_unchecked(self.pos..self.len) }
}
#[inline(always)]
fn consume(&mut self, n: usize) -> &[u8] {
let pos = self.pos;
self.pos += n;
unsafe { self.buf.get_unchecked(pos..self.pos) }
}
fn read(&mut self) -> usize {
self.buf.copy_within(self.pos..self.len, 0);
self.len -= self.pos;
self.pos = 0;
if self.len == self.buf.len() {
self.buf.resize(2 * self.buf.len(), 0);
}
loop {
match self.src.read(&mut self.buf[self.len..]) {
Ok(n) => {
self.len += n;
return n;
}
Err(e) if e.kind() == io::ErrorKind::WouldBlock => {}
Err(e) => panic!("io error: {:?}", e),
}
}
}
}
impl<T: Read> Input for SplitWs<T> {
#[inline]
fn bytes(&mut self) -> &[u8] {
loop {
if let Some(del) = self.peek().iter().position(|c| c.is_ascii_whitespace()) {
if del > 0 {
let s = self.consume(del + 1);
return s.split_last().unwrap().1;
} else {
self.consume(1);
}
} else if self.read() == 0 {
return self.consume(self.len - self.pos);
}
}
}
}
}
pub mod macros {
#[macro_export]
macro_rules ! w { ($ ($ arg : tt) *) => { write ! ($ ($ arg) *) . unwrap () ; } }
#[macro_export]
macro_rules ! wln { ($ dst : expr $ (, $ ($ arg : tt) *) ?) => { { writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; # [cfg (debug_assertions)] $ dst . flush () . unwrap () ; } } }
#[macro_export]
macro_rules! w_iter {
($ dst : expr , $ fmt : expr , $ iter : expr , $ delim : expr) => {{
let mut first = true;
for elem in $iter {
if first {
w!($dst, $fmt, elem);
first = false;
} else {
w!($dst, concat!($delim, $fmt), elem);
}
}
}};
($ dst : expr , $ fmt : expr , $ iter : expr) => {
w_iter!($dst, $fmt, $iter, " ")
};
}
#[macro_export]
macro_rules ! w_iter_ln { ($ dst : expr , $ ($ t : tt) *) => { { w_iter ! ($ dst , $ ($ t) *) ; wln ! ($ dst) ; } } }
#[macro_export]
macro_rules ! e { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprint ! ($ ($ t) *) } }
#[macro_export]
macro_rules ! eln { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprintln ! ($ ($ t) *) } }
#[macro_export]
#[doc(hidden)]
macro_rules ! __tstr { ($ h : expr $ (, $ t : expr) +) => { concat ! (__tstr ! ($ ($ t) ,+) , ", " , __tstr ! (@)) } ; ($ h : expr) => { concat ! (__tstr ! () , " " , __tstr ! (@)) } ; () => { "\x1B[94m[{}:{}]\x1B[0m" } ; (@) => { "\x1B[1;92m{}\x1B[0m = {:?}" } }
#[macro_export]
macro_rules ! d { ($ ($ a : expr) ,*) => { if std :: env :: var ("ND") . map (| v | & v == "0") . unwrap_or (true) { eln ! (__tstr ! ($ ($ a) ,*) , file ! () , line ! () , $ (stringify ! ($ a) , $ a) ,*) ; } } ; }
}