QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#259345 | #3082. Ascending Matrix | jh05013 | AC ✓ | 15ms | 2396kb | Rust | 16.8kb | 2023-11-20 20:34:13 | 2023-11-20 20:34:14 |
Judging History
answer
#[allow(unused_imports)] use std::{collections::*, cmp::*, ops::*};
// https://cdn.discordapp.com/attachments/1079781449621852230/1175811206091645078/SPOILER_image.png?ex=656c9685&is=655a2185&hm=5cdeb3d3a68a9dcd341c04463a941c77e127d84b7cf4b599d06fdc105047c407&
fn main() {
let mut oj = OJ::new();
let n = oj.usize();
let m = oj.usize(); // n*m
let k = oj.usize()-1; // k layers
let r = oj.usize();
let c = oj.usize();
let v = oj.usize(); // A[r,c] = v
// i-th start is (i+1, k-1-i)
// i-th end is (m+i+1, n+k-1-i)
// cell (i,j)'s upper left corner is (j, n+k-i)
// target cell is (r+v, c+v-1)
// target cell's upper left corner is (c+v-2, n+k+2-r-v)
let targ_x = c+v-2;
let targ_y = n+k+2-r-v;
let mf = Modfact::new(1000);
let mut mat_x = SquareMatrix::<Modint>::new(k);
let mut mat_1 = SquareMatrix::<Modint>::new(k);
for i in 0..k {
let xstart = i+1;
let ystart = k-1-i;
for j in 0..k {
let xend = m+j+1;
let yend = n+k-1-j;
if xstart > xend || ystart > yend { continue; }
// cross the target diagonal (x+y = targ_x+targ_y) at y
for y in ystart..=yend {
if targ_x + targ_y < y { continue; }
let x = targ_x + targ_y - y;
if !(xstart..=xend).contains(&x) { continue; }
// count ways
let w = x - xstart; let h = y - ystart;
let ways1 = mf.comb(w+h, w);
let w = xend - x; let h = yend - y;
let ways2 = mf.comb(w+h, w);
let ways = ways1 * ways2;
// add to appropriate matrix
if y >= targ_y { mat_x[i][j] += ways; }
else if y+1 == targ_y { }
else { mat_1[i][j] += ways; }
}
}
}
let poly = SquareMatrix::det_axb(&mut mat_x, &mut mat_1);
oj.write(poly.get(v-1).unwrap_or(&modint(0)));
}
///////////////////////////////////////
pub mod square_matrix_mod {
use std::{ops::*, fmt::*, mem::take};
pub trait Semiring:
Neg<Output=Self>
+ AddAssign + Add<Output=Self> + MulAssign + Mul<Output=Self>
+ Clone + Default + From<i32> + PartialEq + Display + Debug {}
impl<T> Semiring for T where T:
Neg<Output=Self>
+ AddAssign + Add<Output=Self> + MulAssign + Mul<Output=Self>
+ Clone + Default + From<i32> + PartialEq + Display + Debug {}
/// A square matrix.
#[derive(Debug, Clone, Eq, PartialEq, Default)]
pub struct SquareMatrix<T> { pub mat: Vec<Vec<T>> }
impl<T> SquareMatrix<T> {
/// Creates an empty `n * n` matrix.
pub fn new(n: usize) -> Self where T: Clone + Default {
Self { mat: vec![vec![T::default(); n]; n] }
}
/// Cretaes a matrix out of `n * n` values.
pub fn from_line(n: usize, vals: &[T]) -> Self where T: Clone {
assert!(vals.len() == n*n);
if n == 0 { return Self { mat: vec![] }; }
Self { mat: vals.chunks(n).map(<[T]>::to_vec).collect() }
}
/// Creates an identity `n * n` matrix.
pub fn eye(n: usize) -> Self where T: Clone + Default + From<i32> {
let mut mat = Self::new(n);
for i in 0..n { mat[i][i] = 1.into(); }
mat
}
/// Returns `n`.
pub fn n(&self) -> usize { self.mat.len() }
/// Iterates over its elements.
pub fn elements(&self) -> impl Iterator<Item = &T> {
self.mat.iter().flat_map(|row| row.iter())
}
/// Iterates over its owned elements.
pub fn into_elements(self) -> impl Iterator<Item = T> {
self.mat.into_iter().flat_map(IntoIterator::into_iter)
}
/// Iterates mutably over its elements.
pub fn elements_mut(&mut self) -> impl Iterator<Item = &mut T> {
self.mat.iter_mut().flat_map(|row| row.iter_mut())
}
}
// io
impl<T: Display> Display for SquareMatrix<T> {
fn fmt(&self, f: &mut Formatter) -> Result {
for row in &self.mat {
for x in row { write!(f, "{} ", x)?; }
writeln!(f)?;
}
Ok(())
}
}
// indexing
/// Returns the `i`-th row.
impl<T> Index<usize> for SquareMatrix<T> { type Output = [T];
fn index(&self, i: usize) -> &Self::Output { &self.mat[i] }
}
/// Returns the `i`-th row mutably.
impl<T> IndexMut<usize> for SquareMatrix<T> {
fn index_mut(&mut self, i: usize) -> &mut Self::Output { &mut self.mat[i] }
}
// arithmetic
impl<T: Neg<Output = T> + Default> Neg for SquareMatrix<T> {
type Output = Self;
fn neg(mut self) -> Self::Output {
self.elements_mut().for_each(|x| *x = -take(x));
self
}
}
impl<T: AddAssign> AddAssign for SquareMatrix<T> {
fn add_assign(&mut self, b: Self) {
assert_eq!(self.n(), b.n(), "Matrix sizes mismatch");
self.elements_mut().zip(b.into_elements()).for_each(|(x, y)| *x += y);
}
}
impl<T: Add<Output = T> + Default> Add for SquareMatrix<T> { type Output = Self;
fn add(mut self, b: Self) -> Self {
assert_eq!(self.n(), b.n(), "Matrix sizes mismatch");
self.elements_mut().zip(b.into_elements())
.for_each(|(x, y)| *x = take(x) + y);
self
}
}
impl<T: SubAssign> SubAssign for SquareMatrix<T> {
fn sub_assign(&mut self, b: Self) {
assert_eq!(self.n(), b.n(), "Matrix sizes mismatch");
self.elements_mut().zip(b.into_elements()).for_each(|(x, y)| *x -= y);
}
}
impl<T: Sub<Output = T> + Default> Sub for SquareMatrix<T> { type Output = Self;
fn sub(mut self, b: Self) -> Self {
assert_eq!(self.n(), b.n(), "Matrix sizes mismatch");
self.elements_mut().zip(b.into_elements())
.for_each(|(x, y)| *x = take(x) - y);
self
}
}
impl<T: MulAssign + Clone> MulAssign<T> for SquareMatrix<T> {
fn mul_assign(&mut self, k: T) {
self.elements_mut().for_each(|x| *x *= k.clone());
}
}
impl<T: Mul<Output = T> + Default + Clone> Mul<T> for SquareMatrix<T> {
type Output = Self;
fn mul(mut self, k: T) -> Self {
self.elements_mut().for_each(|x| *x = take(x) * k.clone());
self
}
}
impl<T: Semiring> MulAssign for SquareMatrix<T> {
fn mul_assign(&mut self, b: Self) { *self = take(self) * b; }
}
impl<T: Semiring> Mul for SquareMatrix<T> {
type Output = Self;
fn mul(self, b: Self) -> Self {
assert_eq!(self.n(), b.n(), "Matrix sizes mismatch");
let mut ans = Self::new(self.n());
for (j, bj) in b.mat.iter().enumerate() {
for (ai, si) in ans.mat.iter_mut().zip(self.mat.iter()) {
for (aik, bjk) in ai.iter_mut().zip(bj.iter()) {
unsafe { *aik += si.get_unchecked(j).clone() * bjk.clone(); }
}}}
ans
}
}
impl<T: Semiring> SquareMatrix<T> {
/// Returns its `k`-th power.
pub fn pow(&self, mut k: u64) -> Self {
let mut ans = Self::eye(self.n());
let mut a = self.clone();
while k != 0 {
if k&1 == 1 { ans*= a.clone(); }
k>>= 1; a*= a.clone();
}
ans
}
}
} pub use square_matrix_mod::SquareMatrix;
pub mod gauss_elim_mod {
use std::ops::Div;
use super::square_matrix_mod::{Semiring, *};
pub trait Field: Semiring + Div<Output=Self> {}
impl<T> Field for T where T: Semiring + Div<Output=Self> {}
impl<T> SquareMatrix<T> where T: Semiring {
pub fn swap_row(&mut self, i: usize, j: usize) -> bool {
if i == j { false }
else { self.mat.swap(i, j); true }
}
pub fn swap_col(&mut self, i: usize, j: usize) -> bool {
if i == j { false }
else { for row in &mut self.mat { row.swap(i, j); } true }
}
pub fn mul_row(&mut self, i: usize, k: T) {
for x in &mut self[i] { *x *= k.clone(); }
}
pub fn mul_col(&mut self, j: usize, k: T) {
for row in &mut self.mat { row[j] *= k.clone(); }
}
pub fn add_row(&mut self, fr: usize, k: T, to: usize) {
assert_ne!(fr, to, "Bad row-add");
let row = std::mem::take(&mut self.mat[fr]);
for (x, y) in self.mat[to].iter_mut().zip(row.iter()) {
*x += k.clone() * y.clone();
}
self.mat[fr] = row;
}
pub fn add_col(&mut self, fr: usize, k: T, to: usize) {
assert_ne!(fr, to, "Bad col-add");
for row in &mut self.mat {
let v = row[fr].clone();
row[to] += k.clone() * v;
}
}
}
impl<T: Field> SquareMatrix<T> {
pub fn make_ref(&mut self) -> T {
let n = self.n();
let mut istart = 0;
let mut det: T = 1.into();
for j in 0..n {
// Find and swap pivot
let mut piv = istart;
while piv < n && self[piv][j] == T::default() { piv += 1; }
if piv == n { continue; }
if istart != piv {
det = -det; self.swap_row(istart, piv);
}
// Zero the other rows
let v = self.mat[istart][j].clone();
det *= v.clone();
self.mul_row(istart, T::from(1) / v);
for i in istart+1..n {
let v = self.mat[i][j].clone();
self.add_row(istart, -v, i);
}
istart += 1;
}
for i in 0..n { det *= self.mat[i][i].clone(); }
det
}
}
}
pub mod char_poly_mod {
use super::SquareMatrix;
use super::gauss_elim_mod::Field;
impl<T: Field> SquareMatrix<T> {
/// Transforms it into upper Hessenberg form.
pub fn make_hessenberg(&mut self) {
let n = self.n();
for piv in 1..n {
// find pivot and swap
let mut i = piv;
while i < n {
if self[i][piv-1] != T::default() { break; }
i += 1;
}
if i == n { continue; }
self.swap_row(i, piv); self.swap_col(i, piv);
// zero other rows
let x = T::from(1) / self[piv][piv-1].clone();
for i in i+1..n {
let mul = self[i][piv-1].clone() * x.clone();
self.add_row(piv, -mul.clone(), i);
self.add_col(i, mul, piv);
}
}
}
/// Transforms it into upper Hessenberg form and returns det(xI + A).
pub fn make_hessenberg_det_xia(&mut self) -> Vec<T> {
self.make_hessenberg();
let mut dets = vec![vec![T::from(1)]];
let mut det = vec![T::from(1)];
let n = self.n();
for k in 0..n {
let mut q = vec![T::default()];
q.append(&mut det.clone());
for (x, y) in q.iter_mut().zip(det.iter()) {
*x += self[k][k].clone() * y.clone();
}
det = q;
let mut prod = T::from(1);
for i in (0..k).rev() {
prod *= -self[i+1][i].clone();
let z = self[i][k].clone() * prod.clone();
let add = &dets[i];
for (x, y) in det.iter_mut().zip(add.iter()) {
*x += y.clone() * z.clone();
}
}
dets.push(det.clone());
}
det
}
/// Returns det(Ax + B).
// https://tistory.joonhyung.xyz/19
pub fn det_axb(a: &mut Self, b: &mut Self) -> Vec<T> {
let n = a.n();
assert_eq!(n, b.n(), "Matrix sizes mismatch");
let (mut alpha, mut beta) = (0, 0);
let mut det = T::from(1);
while alpha + beta < n {
for i in 0..alpha {
b.add_col(i, -a[i][alpha].clone(), alpha);
a.add_col(i, -a[i][alpha].clone(), alpha);
}
for i in alpha..n-beta {
if a[i][alpha] != T::default() {
if a.swap_row(alpha, i) { det = -det; }
b.swap_row(alpha, i);
break;
}
}
if a[alpha][alpha] != T::default() {
det *= a[alpha][alpha].clone();
let v = T::from(1) / a[alpha][alpha].clone();
a.mul_row(alpha, v.clone()); b.mul_row(alpha, v);
for i in alpha+1..n {
b.add_row(alpha, -a[i][alpha].clone(), i);
a.add_row(alpha, -a[i][alpha].clone(), i);
}
alpha += 1;
}
else {
let r = n-1-beta;
if a.swap_col(alpha, r) { det = -det; }
b.swap_col(alpha, r);
let mut pos = None;
for i in (0..=r).rev() {
if b[i][r] != T::default() { pos = Some(i); break; }
}
let Some(pos) = pos else { return vec![]; };
if pos < alpha {
a.swap_row(pos, alpha-1); b.swap_row(pos, alpha-1);
a.swap_col(pos, alpha-1); b.swap_col(pos, alpha-1);
if a.swap_row(alpha-1, r) { det = -det; }
b.swap_row(alpha-1, r);
alpha -= 1;
}
else {
if a.swap_row(pos, r) { det = -det; }
b.swap_row(pos, r);
}
det *= b[r][r].clone();
let v = T::from(1) / b[r][r].clone();
a.mul_row(r, v.clone()); b.mul_row(r, v);
for i in 0..r {
a.add_row(r, -b[i][r].clone(), i);
b.add_row(r, -b[i][r].clone(), i);
}
beta += 1;
}
}
let mut c = SquareMatrix::new(alpha);
for i in 0..alpha { for j in 0..alpha {
c[i][j] = b[i][j].clone();
}}
let mut poly = c.make_hessenberg_det_xia();
poly.iter_mut().for_each(|x| *x *= det.clone());
poly
}
}
}
pub mod modint_998244353 {
pub const MOD: i32 = 998244353;
pub const MODL: i64 = MOD as i64;
use std::ops::*;
use std::fmt::*;
#[derive(Default, Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
pub struct Modint { v: i32 }
pub fn modint(v: i64) -> Modint { Modint::new(v) }
impl Modint {
pub fn new(v: i64) -> Modint { Self { v: v.rem_euclid(MODL) as i32 } }
pub fn pow(&self, mut n: u64) -> Self {
let mut ans = Modint::new(1);
let mut a = *self;
while n != 0 {
if n&1 == 1 { ans*= a; }
n>>= 1; a*= a;
}
ans
}
pub fn inv(&self) -> Self {
assert!(self.v != 0, "Cannot invert 0");
self.pow((MOD-2) as u64)
}
}
// io
impl std::str::FromStr for Modint {
type Err = std::num::ParseIntError;
fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
Ok(Self::new(s.parse::<i64>()?))
}
}
impl Display for Modint {
fn fmt(&self, f: &mut Formatter) -> Result { write!(f, "{}", self.v) }
}
impl From<Modint> for i32 {
fn from(num: Modint) -> i32 { num.v }
}
impl From<i32> for Modint {
fn from(num: i32) -> Modint { Modint::new(num as i64) }
}
// arithmetic
impl AddAssign for Modint {
fn add_assign(&mut self, b: Self) {
self.v+= b.v; if self.v >= MOD { self.v-= MOD; }
}
}
impl Add for Modint { type Output = Self;
fn add(self, b: Self) -> Self { let mut z = self; z+= b; z }
}
impl Neg for Modint { type Output = Self;
fn neg(self) -> Self { Self::default() - self }
}
impl SubAssign for Modint {
fn sub_assign(&mut self, b: Self) {
self.v-= b.v; if self.v < 0 { self.v+= MOD; }
}
}
impl Sub for Modint { type Output = Self;
fn sub(self, b: Self) -> Self { let mut z = self; z-= b; z }
}
impl MulAssign for Modint {
fn mul_assign(&mut self, b: Self) {
self.v = ((self.v as i64) * (b.v as i64) % MODL) as i32;
}
}
impl Mul for Modint { type Output = Self;
fn mul(self, b: Self) -> Self { let mut z = self; z*= b; z }
}
impl DivAssign for Modint {
fn div_assign(&mut self, b: Self) { *self = *self / b; }
}
#[allow(clippy::suspicious_arithmetic_impl)]
impl Div for Modint { type Output = Self;
fn div(self, b: Self) -> Self { self * b.inv() }
}
// factorial
#[derive(Clone, Debug, Default)]
pub struct Modfact {
pub fact: Vec<Modint>,
pub ifact: Vec<Modint>,
}
impl Modfact {
pub fn new(n: usize) -> Self {
let mut fact = vec![modint(1)];
for i in 1..=n {
fact.push(fact[i-1] * modint(i as i64));
}
let mut ifact = vec![fact[n].inv(); n+1];
for i in (0..n).rev() {
ifact[i] = ifact[i+1] * modint((i+1) as i64);
}
Self { fact, ifact }
}
pub fn len(&self) -> usize { self.fact.len() }
pub fn comb(&self, n: usize, r: usize) -> Modint {
assert!(r <= n && n < self.len(),
"Bad comb-query values ({}, {})", n, r
);
self.fact[n] * self.ifact[r] * self.ifact[n-r]
}
}
}
pub use modint_998244353::{MOD, MODL, Modint, Modfact, modint};
pub mod oj_default_mod {
use std::{fmt::{Display, Debug}, io::*, process::*, str::*};
pub struct OJ {
buffer: std::str::SplitWhitespace<'static>,
out: BufWriter<Stdout>
}
impl OJ {
#[allow(clippy::new_without_default)]
pub fn new() -> Self {
let mut inp = String::new();
stdin().read_to_string(&mut inp).unwrap();
let input = Box::leak(inp.into_boxed_str()).split_whitespace();
Self { buffer: input, out: BufWriter::new(stdout()) }
}
pub fn try_read<T: FromStr>(&mut self) -> std::result::Result<T, &str> {
self.buffer.next().ok_or("EOF")?
.parse().or(Err("Failed parse"))
}
pub fn read<T: FromStr>(&mut self) -> T { self.try_read().unwrap() }
pub fn i32(&mut self) -> i32 { self.read() }
pub fn i64(&mut self) -> i64 { self.read() }
pub fn u32(&mut self) -> u32 { self.read() }
pub fn u64(&mut self) -> u64 { self.read() }
pub fn usize(&mut self) -> usize { self.read() }
pub fn f64(&mut self) -> f64 { self.read() }
pub fn string(&mut self) -> String { self.read() }
pub fn read_vec<T: FromStr>(&mut self, n: usize) -> Vec<T>
{ (0..n).map(|_| self.read()).collect() }
pub fn read_grid<T: FromStr>(&mut self, n: usize, m: usize) -> Vec<Vec<T>>
{ (0..n).map(|_| self.read_vec(m)).collect() }
pub fn write<T: Display>(&mut self, v: T) -> &mut Self
{ write!(self.out, "{v}").unwrap(); self }
pub fn writes<T: Display>(&mut self, vals: &[T]) -> &mut Self
{ for v in vals { self.write(v).sp(); } self }
pub fn debug<T: Debug>(&mut self, v: T) -> &mut Self
{ write!(self.out, "{v:?}").unwrap(); self }
pub fn sp(&mut self) -> &mut Self { self.write(' ') }
pub fn ln(&mut self) -> &mut Self { self.write('\n') }
pub fn quit<T: Display>(&mut self, v: T) -> !
{ self.write(v); self.out.flush().unwrap(); exit(0) }
}
}
pub use oj_default_mod::OJ;
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 2112kb
input:
148 129 48 144 105 13
output:
467058311
result:
ok single line: '467058311'
Test #2:
score: 0
Accepted
time: 0ms
memory: 2032kb
input:
57 48 11 56 9 1
output:
951177245
result:
ok single line: '951177245'
Test #3:
score: 0
Accepted
time: 6ms
memory: 2212kb
input:
121 146 72 117 72 25
output:
284798523
result:
ok single line: '284798523'
Test #4:
score: 0
Accepted
time: 0ms
memory: 2316kb
input:
66 142 11 51 124 4
output:
542285716
result:
ok single line: '542285716'
Test #5:
score: 0
Accepted
time: 8ms
memory: 2256kb
input:
45 127 98 3 31 80
output:
116902187
result:
ok single line: '116902187'
Test #6:
score: 0
Accepted
time: 3ms
memory: 2172kb
input:
125 199 45 51 91 21
output:
715355617
result:
ok single line: '715355617'
Test #7:
score: 0
Accepted
time: 0ms
memory: 2232kb
input:
41 153 6 6 147 2
output:
190519561
result:
ok single line: '190519561'
Test #8:
score: 0
Accepted
time: 2ms
memory: 2396kb
input:
112 108 69 99 29 47
output:
481688971
result:
ok single line: '481688971'
Test #9:
score: 0
Accepted
time: 11ms
memory: 2396kb
input:
138 99 94 73 43 73
output:
667469005
result:
ok single line: '667469005'
Test #10:
score: 0
Accepted
time: 0ms
memory: 1984kb
input:
143 147 18 24 141 9
output:
763965115
result:
ok single line: '763965115'
Test #11:
score: 0
Accepted
time: 8ms
memory: 2256kb
input:
99 63 97 78 51 66
output:
130195301
result:
ok single line: '130195301'
Test #12:
score: 0
Accepted
time: 0ms
memory: 2192kb
input:
103 23 10 25 7 4
output:
674555733
result:
ok single line: '674555733'
Test #13:
score: 0
Accepted
time: 2ms
memory: 2004kb
input:
137 194 42 125 104 17
output:
416667361
result:
ok single line: '416667361'
Test #14:
score: 0
Accepted
time: 1ms
memory: 2252kb
input:
191 13 37 42 2 21
output:
530754407
result:
ok single line: '530754407'
Test #15:
score: 0
Accepted
time: 2ms
memory: 2084kb
input:
195 33 53 101 29 32
output:
851306824
result:
ok single line: '851306824'
Test #16:
score: 0
Accepted
time: 0ms
memory: 2040kb
input:
84 173 8 70 70 6
output:
25135799
result:
ok single line: '25135799'
Test #17:
score: 0
Accepted
time: 1ms
memory: 2092kb
input:
39 53 49 37 6 9
output:
640044940
result:
ok single line: '640044940'
Test #18:
score: 0
Accepted
time: 5ms
memory: 2116kb
input:
135 129 68 134 86 16
output:
910022919
result:
ok single line: '910022919'
Test #19:
score: 0
Accepted
time: 2ms
memory: 2248kb
input:
62 74 56 28 12 46
output:
774987233
result:
ok single line: '774987233'
Test #20:
score: 0
Accepted
time: 8ms
memory: 2300kb
input:
87 135 81 27 44 58
output:
629485683
result:
ok single line: '629485683'
Test #21:
score: 0
Accepted
time: 3ms
memory: 2148kb
input:
148 199 44 79 81 40
output:
369408819
result:
ok single line: '369408819'
Test #22:
score: 0
Accepted
time: 0ms
memory: 2192kb
input:
18 195 5 17 151 5
output:
198068951
result:
ok single line: '198068951'
Test #23:
score: 0
Accepted
time: 9ms
memory: 2160kb
input:
200 137 75 67 65 74
output:
864017958
result:
ok single line: '864017958'
Test #24:
score: 0
Accepted
time: 5ms
memory: 2140kb
input:
171 162 56 113 97 30
output:
255341800
result:
ok single line: '255341800'
Test #25:
score: 0
Accepted
time: 0ms
memory: 2116kb
input:
8 134 38 1 93 10
output:
282048962
result:
ok single line: '282048962'
Test #26:
score: 0
Accepted
time: 2ms
memory: 2340kb
input:
13 55 93 3 25 40
output:
852404927
result:
ok single line: '852404927'
Test #27:
score: 0
Accepted
time: 0ms
memory: 2144kb
input:
169 157 42 77 108 39
output:
595819517
result:
ok single line: '595819517'
Test #28:
score: 0
Accepted
time: 6ms
memory: 2200kb
input:
41 199 87 18 82 58
output:
698977796
result:
ok single line: '698977796'
Test #29:
score: 0
Accepted
time: 3ms
memory: 2176kb
input:
190 68 57 188 59 15
output:
46174623
result:
ok single line: '46174623'
Test #30:
score: 0
Accepted
time: 4ms
memory: 2184kb
input:
90 52 71 39 41 23
output:
417181087
result:
ok single line: '417181087'
Test #31:
score: 0
Accepted
time: 8ms
memory: 2168kb
input:
108 76 89 55 40 13
output:
210578964
result:
ok single line: '210578964'
Test #32:
score: 0
Accepted
time: 1ms
memory: 2148kb
input:
166 191 27 102 30 11
output:
365224233
result:
ok single line: '365224233'
Test #33:
score: 0
Accepted
time: 0ms
memory: 2120kb
input:
41 166 4 10 49 2
output:
245797147
result:
ok single line: '245797147'
Test #34:
score: 0
Accepted
time: 7ms
memory: 2148kb
input:
135 128 79 44 16 6
output:
203896980
result:
ok single line: '203896980'
Test #35:
score: 0
Accepted
time: 8ms
memory: 2236kb
input:
101 193 79 43 65 75
output:
27637457
result:
ok single line: '27637457'
Test #36:
score: 0
Accepted
time: 2ms
memory: 2124kb
input:
88 81 53 35 54 47
output:
950708598
result:
ok single line: '950708598'
Test #37:
score: 0
Accepted
time: 1ms
memory: 2144kb
input:
87 40 28 37 8 8
output:
817953396
result:
ok single line: '817953396'
Test #38:
score: 0
Accepted
time: 9ms
memory: 2120kb
input:
193 136 94 12 94 23
output:
145619900
result:
ok single line: '145619900'
Test #39:
score: 0
Accepted
time: 3ms
memory: 2156kb
input:
90 183 67 8 171 26
output:
899333159
result:
ok single line: '899333159'
Test #40:
score: 0
Accepted
time: 1ms
memory: 2120kb
input:
107 178 32 24 103 12
output:
82019799
result:
ok single line: '82019799'
Test #41:
score: 0
Accepted
time: 2ms
memory: 2076kb
input:
160 23 61 60 17 3
output:
350971684
result:
ok single line: '350971684'
Test #42:
score: 0
Accepted
time: 0ms
memory: 2092kb
input:
100 176 10 54 58 4
output:
978823166
result:
ok single line: '978823166'
Test #43:
score: 0
Accepted
time: 0ms
memory: 2220kb
input:
181 183 42 7 91 41
output:
690262327
result:
ok single line: '690262327'
Test #44:
score: 0
Accepted
time: 3ms
memory: 2124kb
input:
105 131 47 53 68 33
output:
806603020
result:
ok single line: '806603020'
Test #45:
score: 0
Accepted
time: 5ms
memory: 2216kb
input:
51 10 100 1 5 73
output:
341852925
result:
ok single line: '341852925'
Test #46:
score: 0
Accepted
time: 6ms
memory: 2168kb
input:
87 198 73 75 109 72
output:
741170008
result:
ok single line: '741170008'
Test #47:
score: 0
Accepted
time: 0ms
memory: 2136kb
input:
25 158 13 22 1 1
output:
237363061
result:
ok single line: '237363061'
Test #48:
score: 0
Accepted
time: 3ms
memory: 2084kb
input:
64 112 71 28 109 10
output:
350168232
result:
ok single line: '350168232'
Test #49:
score: 0
Accepted
time: 3ms
memory: 2276kb
input:
143 191 52 10 98 10
output:
71885894
result:
ok single line: '71885894'
Test #50:
score: 0
Accepted
time: 1ms
memory: 2140kb
input:
30 130 36 22 85 6
output:
909971212
result:
ok single line: '909971212'
Test #51:
score: 0
Accepted
time: 1ms
memory: 2088kb
input:
154 136 38 34 109 15
output:
655764791
result:
ok single line: '655764791'
Test #52:
score: 0
Accepted
time: 0ms
memory: 2124kb
input:
13 112 7 9 55 1
output:
623849663
result:
ok single line: '623849663'
Test #53:
score: 0
Accepted
time: 2ms
memory: 2348kb
input:
137 103 47 56 77 35
output:
43033659
result:
ok single line: '43033659'
Test #54:
score: 0
Accepted
time: 0ms
memory: 2056kb
input:
40 17 37 11 7 15
output:
803046927
result:
ok single line: '803046927'
Test #55:
score: 0
Accepted
time: 0ms
memory: 2268kb
input:
166 14 58 49 1 26
output:
664593299
result:
ok single line: '664593299'
Test #56:
score: 0
Accepted
time: 0ms
memory: 2096kb
input:
88 195 15 10 120 5
output:
925522664
result:
ok single line: '925522664'
Test #57:
score: 0
Accepted
time: 15ms
memory: 2220kb
input:
164 166 96 161 138 32
output:
111053370
result:
ok single line: '111053370'
Test #58:
score: 0
Accepted
time: 13ms
memory: 2232kb
input:
145 135 94 68 83 9
output:
394110532
result:
ok single line: '394110532'
Test #59:
score: 0
Accepted
time: 5ms
memory: 2184kb
input:
154 173 63 5 77 51
output:
540440686
result:
ok single line: '540440686'
Test #60:
score: 0
Accepted
time: 0ms
memory: 2216kb
input:
20 91 30 20 83 17
output:
961395776
result:
ok single line: '961395776'
Test #61:
score: 0
Accepted
time: 0ms
memory: 2152kb
input:
144 39 13 77 9 5
output:
99731481
result:
ok single line: '99731481'
Test #62:
score: 0
Accepted
time: 8ms
memory: 2276kb
input:
87 152 83 4 59 81
output:
139490896
result:
ok single line: '139490896'
Test #63:
score: 0
Accepted
time: 13ms
memory: 2156kb
input:
171 135 89 114 124 10
output:
736020363
result:
ok single line: '736020363'
Test #64:
score: 0
Accepted
time: 4ms
memory: 2276kb
input:
82 41 99 66 6 5
output:
882042301
result:
ok single line: '882042301'
Test #65:
score: 0
Accepted
time: 0ms
memory: 2124kb
input:
33 114 28 11 73 11
output:
653378940
result:
ok single line: '653378940'
Test #66:
score: 0
Accepted
time: 0ms
memory: 2120kb
input:
180 73 10 43 63 9
output:
170492767
result:
ok single line: '170492767'
Test #67:
score: 0
Accepted
time: 2ms
memory: 2160kb
input:
33 185 63 19 107 7
output:
907253908
result:
ok single line: '907253908'
Test #68:
score: 0
Accepted
time: 0ms
memory: 2116kb
input:
69 90 22 34 31 3
output:
137223161
result:
ok single line: '137223161'
Test #69:
score: 0
Accepted
time: 0ms
memory: 2092kb
input:
42 45 60 29 38 36
output:
99908563
result:
ok single line: '99908563'
Test #70:
score: 0
Accepted
time: 1ms
memory: 2128kb
input:
69 158 34 56 39 17
output:
681472254
result:
ok single line: '681472254'
Test #71:
score: 0
Accepted
time: 5ms
memory: 2112kb
input:
66 69 84 5 8 41
output:
277373736
result:
ok single line: '277373736'
Test #72:
score: 0
Accepted
time: 3ms
memory: 2152kb
input:
168 31 68 66 4 21
output:
528816013
result:
ok single line: '528816013'
Test #73:
score: 0
Accepted
time: 4ms
memory: 2228kb
input:
65 33 94 2 30 76
output:
331224077
result:
ok single line: '331224077'
Test #74:
score: 0
Accepted
time: 0ms
memory: 2040kb
input:
84 111 12 28 106 12
output:
95279945
result:
ok single line: '95279945'
Test #75:
score: 0
Accepted
time: 6ms
memory: 2236kb
input:
102 77 83 95 62 51
output:
773914979
result:
ok single line: '773914979'
Test #76:
score: 0
Accepted
time: 7ms
memory: 2172kb
input:
113 144 76 24 68 13
output:
845242590
result:
ok single line: '845242590'
Test #77:
score: 0
Accepted
time: 0ms
memory: 2124kb
input:
45 24 9 10 2 5
output:
71790514
result:
ok single line: '71790514'
Test #78:
score: 0
Accepted
time: 5ms
memory: 2168kb
input:
158 98 61 86 50 29
output:
123475901
result:
ok single line: '123475901'
Test #79:
score: 0
Accepted
time: 1ms
memory: 2036kb
input:
118 52 27 11 23 21
output:
489202572
result:
ok single line: '489202572'
Test #80:
score: 0
Accepted
time: 1ms
memory: 2256kb
input:
122 148 35 112 17 17
output:
856169627
result:
ok single line: '856169627'
Test #81:
score: 0
Accepted
time: 0ms
memory: 2108kb
input:
135 114 15 20 43 9
output:
873320383
result:
ok single line: '873320383'
Test #82:
score: 0
Accepted
time: 5ms
memory: 2180kb
input:
89 70 84 70 12 18
output:
302990320
result:
ok single line: '302990320'
Test #83:
score: 0
Accepted
time: 2ms
memory: 2264kb
input:
15 68 67 5 51 66
output:
980298686
result:
ok single line: '980298686'
Test #84:
score: 0
Accepted
time: 1ms
memory: 2244kb
input:
50 2 73 40 2 8
output:
550497760
result:
ok single line: '550497760'
Test #85:
score: 0
Accepted
time: 5ms
memory: 2268kb
input:
117 88 83 93 1 50
output:
645491986
result:
ok single line: '645491986'
Test #86:
score: 0
Accepted
time: 2ms
memory: 2104kb
input:
45 173 54 34 93 3
output:
330947509
result:
ok single line: '330947509'
Test #87:
score: 0
Accepted
time: 0ms
memory: 2132kb
input:
39 10 22 34 6 20
output:
184357429
result:
ok single line: '184357429'
Test #88:
score: 0
Accepted
time: 2ms
memory: 2180kb
input:
58 27 71 55 19 22
output:
201813851
result:
ok single line: '201813851'
Test #89:
score: 0
Accepted
time: 1ms
memory: 2120kb
input:
123 57 40 14 38 23
output:
891805630
result:
ok single line: '891805630'
Test #90:
score: 0
Accepted
time: 0ms
memory: 2172kb
input:
84 64 70 12 2 23
output:
351372969
result:
ok single line: '351372969'
Test #91:
score: 0
Accepted
time: 3ms
memory: 2244kb
input:
46 160 72 21 146 9
output:
625614461
result:
ok single line: '625614461'
Test #92:
score: 0
Accepted
time: 2ms
memory: 2160kb
input:
45 99 57 25 40 4
output:
498175745
result:
ok single line: '498175745'
Test #93:
score: 0
Accepted
time: 0ms
memory: 1996kb
input:
15 21 12 14 6 3
output:
727195216
result:
ok single line: '727195216'
Test #94:
score: 0
Accepted
time: 1ms
memory: 2060kb
input:
154 77 32 73 62 15
output:
513610382
result:
ok single line: '513610382'
Test #95:
score: 0
Accepted
time: 0ms
memory: 2128kb
input:
165 97 16 158 69 11
output:
308621770
result:
ok single line: '308621770'
Test #96:
score: 0
Accepted
time: 8ms
memory: 2180kb
input:
146 128 97 132 24 10
output:
751957330
result:
ok single line: '751957330'
Test #97:
score: 0
Accepted
time: 1ms
memory: 2152kb
input:
49 39 35 2 10 14
output:
338882448
result:
ok single line: '338882448'
Test #98:
score: 0
Accepted
time: 2ms
memory: 2140kb
input:
73 1 73 35 1 44
output:
126891463
result:
ok single line: '126891463'
Test #99:
score: 0
Accepted
time: 1ms
memory: 2224kb
input:
69 82 59 1 73 1
output:
436743471
result:
ok single line: '436743471'
Test #100:
score: 0
Accepted
time: 1ms
memory: 2124kb
input:
88 86 40 19 77 4
output:
758000538
result:
ok single line: '758000538'