結果
| 問題 | No.723 2つの数の和 |
| ユーザー |
 へのく
|
| 提出日時 | 2021-06-12 00:41:31 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 103 ms / 2,000 ms |
| コード長 | 42,620 bytes |
| コンパイル時間 | 15,132 ms |
| コンパイル使用メモリ | 379,792 KB |
| 実行使用メモリ | 11,884 KB |
| 最終ジャッジ日時 | 2024-05-08 21:29:52 |
| 合計ジャッジ時間 | 16,005 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | AC | 1 ms
5,248 KB |
| testcase_02 | AC | 1 ms
5,248 KB |
| testcase_03 | AC | 102 ms
11,752 KB |
| testcase_04 | AC | 99 ms
11,760 KB |
| testcase_05 | AC | 103 ms
11,880 KB |
| testcase_06 | AC | 101 ms
11,756 KB |
| testcase_07 | AC | 100 ms
11,884 KB |
| testcase_08 | AC | 102 ms
11,756 KB |
| testcase_09 | AC | 103 ms
11,752 KB |
| testcase_10 | AC | 101 ms
11,756 KB |
| testcase_11 | AC | 101 ms
11,756 KB |
| testcase_12 | AC | 103 ms
11,880 KB |
| testcase_13 | AC | 1 ms
5,376 KB |
| testcase_14 | AC | 1 ms
5,376 KB |
| testcase_15 | AC | 1 ms
5,376 KB |
| testcase_16 | AC | 1 ms
5,376 KB |
| testcase_17 | AC | 1 ms
5,376 KB |
| testcase_18 | AC | 5 ms
5,376 KB |
| testcase_19 | AC | 103 ms
10,980 KB |
| testcase_20 | AC | 1 ms
5,376 KB |
| testcase_21 | AC | 1 ms
5,376 KB |
| testcase_22 | AC | 1 ms
5,376 KB |
| testcase_23 | AC | 103 ms
11,880 KB |
| testcase_24 | AC | 101 ms
11,884 KB |
ソースコード
#![allow(non_snake_case)]
use crate::{fps::conv_i64::fps_i64, scanner::Scanner};
fn main() {
let mut scan = Scanner::new();
let n = scan.int();
let x = scan.int();
if x > 200000 {
println!("0");
return;
}
let a = scan.readn::<isize>(n);
let mut f = list![0;100001];
for e in a {
f[e] += 1;
}
let mut f = fps_i64(f);
f.shrink();
let f2 = &f * &f;
println!("{}", f2[x]);
}
pub mod fps {
pub mod convolution {
use std::mem::swap;
use crate::{
arraylist::List,
independent::integer::Int,
modint,
modulo::{ButterflyCache, ModInt, Modulus},
prime_number::primitive_root,
};
fn prepare<M: Modulus>() -> ButterflyCache<M> {
let g = ModInt::<M>::raw(primitive_root(M::M as i32) as u32);
let mut es = [ModInt::<M>::raw(0); 30];
let mut ies = [ModInt::<M>::raw(0); 30];
let cnt2 = (M::M - 1).trailing_zeros() as usize;
let mut e = g.pow((M::M - 1) >> cnt2);
let mut ie = e.inv();
for i in (2..=cnt2).rev() {
es[i - 2] = e;
ies[i - 2] = ie;
e *= e;
ie *= ie;
}
let sum_e = es
.iter()
.scan(ModInt::new(1), |acc, e| {
*acc *= *e;
Some(*acc)
})
.collect();
let sum_ie = ies
.iter()
.scan(ModInt::new(1), |acc, ie| {
*acc *= *ie;
Some(*acc)
})
.collect();
ButterflyCache { sum_e, sum_ie }
}
fn ceil_pow2(n: u32) -> u32 {
32 - n.saturating_sub(1).leading_zeros()
}
fn inv_gcd(a: i64, b: i64) -> (i64, i64) {
let a = a.rem_euclid(b);
if a == 0 {
return (b, 0);
}
let mut s = b;
let mut t = a;
let mut m0 = 0;
let mut m1 = 1;
while t != 0 {
let u = s / t;
s -= t * u;
m0 -= m1 * u;
swap(&mut s, &mut t);
swap(&mut m0, &mut m1);
}
if m0 < 0 {
m0 += b / s;
}
(s, m0)
}
fn butterfly<M: Modulus>(a: &mut [ModInt<M>]) {
let n = a.len();
let h = ceil_pow2(n as u32);
M::butterfly_cache().with(|cache| {
let mut cache = cache.borrow_mut();
let ButterflyCache { sum_e, .. } = cache.get_or_insert_with(prepare);
for ph in 1..=h {
let w = 1 << (ph - 1);
let p = 1 << (h - ph);
let mut now = ModInt::<M>::new(1);
for s in 0..w {
let offset = s << (h - ph + 1);
for i in 0..p {
let l = a[i + offset];
let r = a[i + offset + p] * now;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
now *= sum_e[(!s).trailing_zeros() as usize];
}
}
});
}
fn butterfly_inv<M: Modulus>(a: &mut [ModInt<M>]) {
let n = a.len();
let h = ceil_pow2(n as u32);
M::butterfly_cache().with(|cache| {
let mut cache = cache.borrow_mut();
let ButterflyCache { sum_ie, .. } = cache.get_or_insert_with(prepare);
for ph in (1..=h).rev() {
let w = 1 << (ph - 1);
let p = 1 << (h - ph);
let mut inow = ModInt::<M>::new(1);
for s in 0..w {
let offset = s << (h - ph + 1);
for i in 0..p {
let l = a[i + offset];
let r = a[i + offset + p];
a[i + offset] = l + r;
a[i + offset + p] = ModInt::new(M::M + l.val - r.val) * inow;
}
inow *= sum_ie[(!s).trailing_zeros() as usize];
}
}
})
}
pub fn convolution_naive<T: Int>(a: &[T], b: &[T]) -> List<T> {
if a.is_empty() || b.is_empty() {
return vec![].into();
}
let (n, m) = (a.len(), b.len());
let (n, m, a, b) = if n < m { (m, n, b, a) } else { (n, m, a, b) };
let mut ans = vec![T::zero(); n + m - 1];
for i in 0..n {
for j in 0..m {
ans[i + j] += a[i] * b[j];
}
}
ans.into()
}
pub fn convolution_ntt<M: Modulus>(a: &[ModInt<M>], b: &[ModInt<M>]) -> List<ModInt<M>> {
if a.is_empty() || b.is_empty() {
return vec![].into();
}
let (n, m) = (a.len(), b.len());
if n.min(m) <= 60 {
return convolution_naive(a, b);
}
let (mut a, mut b) = (a.to_owned(), b.to_owned());
let z = 1 << ceil_pow2((n + m - 1) as _);
a.resize(z, ModInt::raw(0));
butterfly(&mut a);
b.resize(z, ModInt::raw(0));
butterfly(&mut b);
for (a, b) in a.iter_mut().zip(&b) {
*a *= *b;
}
butterfly_inv(&mut a);
a.resize(n + m - 1, ModInt::raw(0));
let iz = ModInt::new(z).inv();
for a in &mut a {
*a *= iz;
}
a.into()
}
pub fn convolution_raw<T: Int, M: Modulus>(a: &[T], b: &[T]) -> List<T> {
let a = a.iter().cloned().map(ModInt::<M>::new).collect::<Vec<_>>();
let b = b.iter().cloned().map(ModInt::<M>::new).collect::<Vec<_>>();
convolution_ntt::<M>(&a, &b)
.into_iter()
.map(|z| T::from_u32(z.val))
.collect()
}
pub fn convolution_i64(a: &[i64], b: &[i64]) -> List<i64> {
const M1: u64 = 754_974_721;
const M2: u64 = 167_772_161;
const M3: u64 = 469_762_049;
const M2M3: u64 = M2 * M3;
const M1M3: u64 = M1 * M3;
const M1M2: u64 = M1 * M2;
const M1M2M3: u64 = M1M2.wrapping_mul(M3);
modint!(M1);
modint!(M2);
modint!(M3);
if a.is_empty() || b.is_empty() {
return List::new();
}
let (_, i1) = inv_gcd(M2M3 as _, M1 as _);
let (_, i2) = inv_gcd(M1M3 as _, M2 as _);
let (_, i3) = inv_gcd(M1M2 as _, M3 as _);
let c1 = convolution_raw::<_, M1>(a, b);
let c2 = convolution_raw::<_, M2>(a, b);
let c3 = convolution_raw::<_, M3>(a, b);
c1.into_iter()
.zip(c2)
.zip(c3)
.map(|((c1, c2), c3)| {
const OFFSET: &[u64] = &[0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3];
let mut x = [(c1, i1, M1, M2M3), (c2, i2, M2, M1M3), (c3, i3, M3, M1M2)]
.iter()
.map(|&(c, i, m1, m2)| {
c.wrapping_mul(i).rem_euclid(m1 as _).wrapping_mul(m2 as _)
})
.fold(0, i64::wrapping_add);
let mut diff = c1 - x.rem_euclid(M1 as _);
if diff < 0 {
diff += M1 as i64;
}
x = x.wrapping_sub(OFFSET[diff.rem_euclid(5) as usize] as _);
x
})
.collect()
}
}
pub mod conv_i64 {
use crate::{
arraylist::List,
fps::{
convolution::convolution_i64,
formal_power_series::{Convolution, FormalPowerSeries},
},
independent::integer::Int,
};
#[derive(Debug, PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
pub enum ConvolutionI64 {}
impl Convolution<i64> for ConvolutionI64 {
fn convolution(a: &[i64], b: &[i64]) -> List<i64> {
convolution_i64(a, b)
}
}
pub fn fps_i64<T: Int>(lst: List<T>) -> FormalPowerSeries<T, ConvolutionI64>
where
ConvolutionI64: Convolution<T>,
{
FormalPowerSeries::new(lst)
}
#[macro_export]
macro_rules! fps_i64 {
() => {$crate::fps!([$crate::fps::conv_i64::ConvolutionI64])};
($($v:expr),+ $(,)?) => {$crate::fps!($($v),+;[$crate::fps::conv_i64::ConvolutionI64])};
}
}
pub mod formal_power_series {
use std::{
fmt::Debug,
marker::PhantomData,
ops::{
Add, AddAssign, Div, DivAssign, Index, IndexMut, Mul, MulAssign, Neg, Rem,
RemAssign, Shl, Shr, Sub, SubAssign,
},
};
use crate::{
arraylist::{lst, List},
independent::integer::Int,
list,
};
pub trait Convolution<T> {
fn convolution(a: &[T], b: &[T]) -> List<T>;
}
impl<T: Int, F: Convolution<T>> From<&lst<T>> for FormalPowerSeries<T, F> {
fn from(lst: &lst<T>) -> Self {
Self::new(lst.list())
}
}
#[derive(PartialEq, Eq)]
pub struct FormalPowerSeries<T, F: Convolution<T>> {
data: List<T>,
phantom: PhantomData<fn() -> F>,
}
impl<T: Int, F: Convolution<T>> Clone for FormalPowerSeries<T, F> {
fn clone(&self) -> Self {
Self::new(self.data.clone())
}
}
impl<T: Int + Debug, F: Convolution<T>> Debug for FormalPowerSeries<T, F> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
self.data.fmt(f)
}
}
impl<T: Int, F: Convolution<T>> FormalPowerSeries<T, F> {
pub fn new(data: List<T>) -> FormalPowerSeries<T, F> {
FormalPowerSeries {
data,
phantom: PhantomData,
}
}
pub fn empty() -> Self {
Self::new(List::new())
}
pub fn lens(&self) -> isize {
self.data.lens()
}
pub fn is_empty(&self) -> bool {
self.data.lens() == 0
}
pub fn resize(&mut self, new_len: isize) {
self.data.resize(new_len, T::zero());
}
pub fn shrink(&mut self) {
while self.data.last() == Some(&T::zero()) {
self.data.pop();
}
}
pub fn pre(&self, size: isize) -> Self {
Self::from(&self.data[..self.lens().min(size)])
}
pub fn rev(&self, deg: impl Into<Option<isize>>) -> Self {
let deg = deg.into();
let mut data = self.data.clone();
if let Some(deg) = deg {
data.resize(deg, T::zero());
}
data.reverse();
Self::new(data)
}
pub fn inv(&self, deg: impl Into<Option<isize>>) -> Self {
assert!(self[0] != T::zero());
let n = self.lens();
let deg = deg.into().unwrap_or(n);
let mut ret = Self::new(list![T::one() / self[0]]);
let mut i = 1;
while i < deg {
ret = (&ret + &ret - &ret * &ret * self.pre(i << 1)).pre(i << 1);
i <<= 1;
}
ret.pre(deg)
}
}
macro_rules! impl_ops {
($tpe:ident, $fname:ident, $op:tt) => {
impl<T: Int, F: Convolution<T>> $tpe<&Self> for FormalPowerSeries<T, F> {
type Output = FormalPowerSeries<T, F>;
fn $fname(self, rhs: &Self) -> Self::Output {
let mut ret: FormalPowerSeries<T, F> = self.clone();
ret $op rhs;
ret
}
}
impl<T: Int, F: Convolution<T>> $tpe for FormalPowerSeries<T, F> {
type Output = FormalPowerSeries<T, F>;
fn $fname(self, rhs: Self) -> Self::Output {
let mut ret: FormalPowerSeries<T, F> = self.clone();
ret $op &rhs;
ret
}
}
impl<T: Int, F: Convolution<T>> $tpe for &FormalPowerSeries<T, F> {
type Output = FormalPowerSeries<T, F>;
fn $fname(self, rhs: Self) -> Self::Output {
let mut ret: FormalPowerSeries<T, F> = self.clone();
ret $op rhs;
ret
}
}
};
}
impl_ops!(Add, add, +=);
impl_ops!(Sub, sub, -=);
impl_ops!(Mul, mul, *=);
impl_ops!(Div, div, /=);
impl_ops!(Rem, rem, %=);
impl<T: Int, F: Convolution<T>> Neg for &FormalPowerSeries<T, F> {
type Output = FormalPowerSeries<T, F>;
fn neg(self) -> Self::Output {
let data = self.data.map(|x| T::zero() - x);
FormalPowerSeries {
data,
phantom: PhantomData,
}
}
}
impl<T: Int, F: Convolution<T>> AddAssign<&Self> for FormalPowerSeries<T, F> {
fn add_assign(&mut self, rhs: &Self) {
if rhs.lens() > self.lens() {
self.resize(rhs.lens())
};
self.data
.iter_mut()
.zip(rhs.data.iter())
.for_each(|(e, r)| *e += *r);
}
}
impl<T: Int, F: Convolution<T>> AddAssign<T> for FormalPowerSeries<T, F> {
fn add_assign(&mut self, rhs: T) {
if self.is_empty() {
self.resize(1)
};
self[0] += rhs;
}
}
impl<T: Int, F: Convolution<T>> SubAssign<&Self> for FormalPowerSeries<T, F> {
fn sub_assign(&mut self, rhs: &Self) {
if rhs.lens() > self.lens() {
self.resize(rhs.lens())
};
self.data
.iter_mut()
.zip(rhs.data.iter())
.for_each(|(e, r)| *e -= *r);
self.shrink();
}
}
impl<T: Int, F: Convolution<T>> SubAssign<T> for FormalPowerSeries<T, F> {
fn sub_assign(&mut self, rhs: T) {
if self.is_empty() {
self.resize(1);
}
self[0] -= rhs;
self.shrink();
}
}
impl<T: Int, F: Convolution<T>> MulAssign<T> for FormalPowerSeries<T, F> {
fn mul_assign(&mut self, rhs: T) {
for e in self.data.iter_mut() {
*e *= rhs;
}
}
}
impl<T: Int, F: Convolution<T>> MulAssign<&Self> for FormalPowerSeries<T, F> {
fn mul_assign(&mut self, rhs: &Self) {
if self.is_empty() || rhs.is_empty() {
self.data.data.clear();
return;
}
self.data = F::convolution(&self.data, &rhs.data);
}
}
impl<T: Int, F: Convolution<T>> RemAssign<&Self> for FormalPowerSeries<T, F> {
fn rem_assign(&mut self, rhs: &Self) {
*self -= &(&*self / rhs * rhs);
}
}
impl<T: Int, F: Convolution<T>> DivAssign<&Self> for FormalPowerSeries<T, F> {
fn div_assign(&mut self, rhs: &Self) {
if self.lens() < rhs.lens() {
self.data.data.clear();
return;
}
let n = self.lens() - rhs.lens() + 1;
*self = (self.rev(None).pre(n) * rhs.rev(None).inv(n)).pre(n).rev(n);
}
}
impl<T: Int, F: Convolution<T>> Shr<isize> for &FormalPowerSeries<T, F> {
type Output = FormalPowerSeries<T, F>;
fn shr(self, rhs: isize) -> Self::Output {
if self.lens() <= rhs {
return FormalPowerSeries::<T, F>::empty();
}
Self::Output::from(&self.data[rhs..])
}
}
impl<T: Int, F: Convolution<T>> Shl<isize> for &FormalPowerSeries<T, F> {
type Output = FormalPowerSeries<T, F>;
fn shl(self, rhs: isize) -> Self::Output {
let mut data = list![T::zero();rhs];
data.append(&self.data);
Self::Output::new(data)
}
}
impl<T: Int, F: Convolution<T>> Index<isize> for FormalPowerSeries<T, F> {
type Output = T;
fn index(&self, index: isize) -> &T {
&self.data[index]
}
}
impl<T: Int, F: Convolution<T>> IndexMut<isize> for FormalPowerSeries<T, F> {
fn index_mut(&mut self, index: isize) -> &mut T {
&mut self.data[index]
}
}
#[macro_export]
macro_rules! fps {
([$($tpe:tt)+]) => { $crate::fps::formal_power_series::FormalPowerSeries::<_, $($tpe)+>::empty() };
($($v:expr),+ $(,)?;[$($tpe:tt)+]) => { $crate::fps::formal_power_series::FormalPowerSeries::<_, $($tpe)+>::new(List::from([$($v),+].to_vec())) };
}
}
}
pub mod independent {
pub mod integer {
use std::fmt::Display;
use std::ops::*;
pub trait Int:
Add<Output = Self>
+ Sub<Output = Self>
+ Mul<Output = Self>
+ Div<Output = Self>
+ Rem<Output = Self>
+ AddAssign
+ SubAssign
+ MulAssign
+ DivAssign
+ RemAssign
+ std::hash::Hash
+ PartialEq
+ Eq
+ PartialOrd
+ Ord
+ Copy
+ Display
{
fn to_u8(&self) -> u8;
fn to_u16(&self) -> u16;
fn to_u32(&self) -> u32;
fn to_u64(&self) -> u64;
fn to_u128(&self) -> u128;
fn to_i8(&self) -> i8;
fn to_i16(&self) -> i16;
fn to_i32(&self) -> i32;
fn to_i64(&self) -> i64;
fn to_i128(&self) -> i128;
fn to_usize(&self) -> usize;
fn to_isize(&self) -> isize;
fn from_u8(x: u8) -> Self;
fn from_u16(x: u16) -> Self;
fn from_u32(x: u32) -> Self;
fn from_u64(x: u64) -> Self;
fn from_u128(x: u128) -> Self;
fn from_i8(x: i8) -> Self;
fn from_i16(x: i16) -> Self;
fn from_i32(x: i32) -> Self;
fn from_i64(x: i64) -> Self;
fn from_i128(x: i128) -> Self;
fn from_usize(x: usize) -> Self;
fn from_isize(x: isize) -> Self;
fn zero() -> Self;
fn one() -> Self;
fn next(&self) -> Self {
*self + Self::one()
}
}
#[macro_export]
macro_rules! impl_integer_functions {
($to_op:expr, $from_op:expr) => {
impl_integer_functions!(
$to_op, $from_op,
to_u8, from_u8, u8,
to_u16, from_u16, u16,
to_u32, from_u32, u32,
to_u64, from_u64, u64,
to_u128, from_u128, u128,
to_i8, from_i8, i8,
to_i16, from_i16, i16,
to_i32, from_i32, i32,
to_i64, from_i64, i64,
to_i128, from_i128, i128,
to_usize, from_usize, usize,
to_isize, from_isize, isize
);
};
($to_op:expr, $from_op:expr, $($tofn:ident, $fromfn:ident, $tpe:ident),*) => {
$(
fn $tofn(&self) -> $tpe {
$to_op(self) as $tpe
}
fn $fromfn(x: $tpe) -> Self {
$from_op(x)
}
)*
fn zero() -> Self {$from_op(0)}
fn one() -> Self {$from_op(1)}
};
}
macro_rules! impl_integer {
($($tpe:ident),*) => {
$(
impl Int for $tpe {
impl_integer_functions!(
|s: &Self| *s, |x| x as $tpe
);
}
)*
};
}
impl_integer!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize);
}
}
pub mod prime_number {
use crate::arraylist::List;
use crate::ext::int::IntExtra;
pub struct MinFactor {
pub is_prime: List<bool>,
pub min_factor: List<isize>,
}
impl MinFactor {}
pub fn primitive_root(m: i32) -> i32 {
match m {
2 => return 1,
167_772_161 => return 3,
469_762_049 => return 3,
754_974_721 => return 11,
998_244_353 => return 3,
_ => {}
}
let mut divs = [0; 20];
divs[0] = 2;
let mut cnt = 1;
let mut x = (m - 1) / 2;
while x % 2 == 0 {
x /= 2;
}
for i in (3..std::i32::MAX).step_by(2) {
if i as i64 * i as i64 > x as i64 {
break;
}
if x % i == 0 {
divs[cnt] = i;
cnt += 1;
while x % i == 0 {
x /= i;
}
}
}
if x > 1 {
divs[cnt] = x;
cnt += 1;
}
let mut g = 2;
loop {
if (0..cnt).all(|i| g.pow_mod(((m - 1) / divs[i]) as i64, m) != 1) {
break g as i32;
}
g += 1;
}
}
}
pub mod ext {
pub mod int {
use crate::ext::range::IntRangeBounds;
use crate::independent::integer::Int;
use std::ops::RangeBounds;
pub trait IntExtra: Int {
fn chrange<U: RangeBounds<Self>>(self, range: U) -> Self {
range.domain_of(self)
}
fn div_ceil(self, y: Self) -> Self {
(self + y - Self::one()) / y
}
fn div_floor(self, y: Self) -> Self {
self / y
}
fn ceil_multiple(self, y: Self) -> Self {
self.div_ceil(y) * y
}
fn floor_multiple(self, y: Self) -> Self {
self.div_floor(y) * y
}
fn pow_mod(mut self, mut n: i64, m: Self) -> Self {
let mut res = Self::one();
self %= m;
while n > 0 {
if n & 1 == 1 {
res *= self;
res %= m;
}
self = (self * self) % m;
n >>= 1;
}
res
}
}
impl<T> IntExtra for T where T: Int {}
}
pub mod range {
use crate::independent::integer::Int;
use std::cmp::{max, min};
use std::ops::{Bound, Range, RangeBounds};
pub trait IntRangeBounds<U: Int>: RangeBounds<U> {
fn lbopt(&self) -> Option<U> {
match self.start_bound() {
Bound::Included(x) => Some(*x),
Bound::Excluded(x) => Some(*x + U::one()),
Bound::Unbounded => None,
}
}
fn ubopt(&self) -> Option<U> {
match self.end_bound() {
Bound::Included(x) => Some(*x + U::one()),
Bound::Excluded(x) => Some(*x),
Bound::Unbounded => None,
}
}
fn lower_bound(&self, limit: U) -> U {
self.lbopt().map_or(limit, |x| max(limit, x))
}
fn upper_bound(&self, limit: U) -> U {
self.ubopt().map_or(limit, |x| min(limit, x))
}
fn to_harfopen(&self, lb: U, ub: U) -> Range<U> {
self.lower_bound(lb)..self.upper_bound(ub)
}
fn domain_of(&self, mut t: U) -> U {
if let Some(x) = self.lbopt() {
if t < x {
t = x;
}
}
if let Some(x) = self.ubopt() {
if x <= t {
t = x - U::one();
}
}
t
}
fn width(&self) -> U {
if self.empty() {
U::zero()
} else {
self.ubopt().unwrap() - self.lbopt().unwrap()
}
}
fn empty(&self) -> bool {
match (self.lbopt(), self.ubopt()) {
(Some(lb), Some(ub)) => lb >= ub,
(None, _ub) => false,
(_lb, None) => false,
}
}
fn contain_range(&self, inner: &Self) -> bool {
(match (self.lbopt(), inner.lbopt()) {
(Some(a), Some(b)) => a <= b,
(None, _) => true,
(Some(_), None) => false,
}) && (match (inner.ubopt(), self.ubopt()) {
(Some(a), Some(b)) => a <= b,
(_, None) => true,
(None, Some(_)) => false,
})
}
fn separate_range(&self, other: &Self) -> bool {
if let (Some(a), Some(b)) = (self.ubopt(), other.lbopt()) {
if a <= b {
return true;
}
}
if let (Some(a), Some(b)) = (other.ubopt(), self.lbopt()) {
if a <= b {
return true;
}
}
false
}
fn overlap(&self, other: &Self) -> Range<U> {
let left = if let (Some(a), Some(b)) = (self.lbopt(), other.lbopt()) {
max(a, b)
} else {
self.lbopt().or(other.lbopt()).unwrap()
};
let right = if let (Some(a), Some(b)) = (self.ubopt(), other.ubopt()) {
min(a, b)
} else {
self.ubopt().or(other.ubopt()).unwrap()
};
left..right
}
}
impl<T: ?Sized, U: Int> IntRangeBounds<U> for T where T: RangeBounds<U> {}
}
}
pub mod arraylist {
use std::ops::*;
use std::slice::Iter;
use std::fmt::Formatter;
use std::iter::FromIterator;
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct List<T> {
pub data: Vec<T>,
}
impl<T> List<T> {
#[inline]
pub fn new() -> List<T> {
List { data: vec![] }
}
#[inline]
pub fn init(init: T, n: isize) -> List<T>
where
T: Clone,
{
List {
data: vec![init; n as usize],
}
}
#[inline]
pub fn pop(&mut self) -> Option<T> {
self.data.pop()
}
#[inline]
pub fn reverse(&mut self) {
self.data.reverse();
}
#[inline]
pub fn append(&mut self, other: &lst<T>)
where
T: Clone,
{
self.data.append(&mut other.to_vec());
}
#[inline]
pub fn resize(&mut self, new_len: isize, value: T)
where
T: Clone,
{
self.data.resize(new_len as usize, value);
}
}
macro_rules! impl_idx {
($($tpe:ty, $t:ident [$($output:tt)+], $slf:ident, $index:ident, $f:expr),*) => {
$(impl<$t> Index<$tpe> for List<$t> {
type Output = $($output)+;
#[inline]
fn index(&$slf, $index: $tpe) -> &Self::Output {$f}
})*
$(impl<$t> Index<$tpe> for lst<$t> {
type Output = $($output)+;
#[inline]
fn index(&$slf, $index: $tpe) -> &Self::Output {$f}
})*
}
}
macro_rules! impl_idx_mut {
($($tpe:ty, $slf:ident, $index:ident, $f:expr),*) => {
$(impl<T> IndexMut<$tpe> for List<T> {
#[inline]
fn index_mut(&mut $slf, $index: $tpe) -> &mut Self::Output {$f}
})*
$(impl<T> IndexMut<$tpe> for lst<T> {
#[inline]
fn index_mut(&mut $slf, $index: $tpe) -> &mut Self::Output {$f}
})*
};
}
macro_rules! impl_idx_slice {
($($tpe:ty),*) => {
impl_idx!($($tpe, T [lst<T>], self, i, self.as_slice(i)),*);
impl_idx_mut!($($tpe, self, i, self.as_slice_mut(i)),*);
};
}
impl_idx! {
isize, T [T], self, i, self.at(i),
char, T [T], self, i, self.at(i as isize - 'a' as isize)
}
impl_idx_slice! {
Range<isize>, RangeTo<isize>, RangeFrom<isize>, RangeFull, RangeInclusive<isize>, RangeToInclusive<isize>
}
impl_idx_mut! {
isize, self, i, self.at_mut(i),
char, self, i, self.at_mut(i as isize - 'a' as isize)
}
impl<T> FromIterator<T> for List<T> {
#[inline]
fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> Self {
List {
data: iter.into_iter().collect(),
}
}
}
impl<T> IntoIterator for List<T> {
type Item = T;
type IntoIter = std::vec::IntoIter<T>;
#[inline]
fn into_iter(self) -> std::vec::IntoIter<T> {
self.data.into_iter()
}
}
macro_rules! impl_traits {
($($tpe:tt),*) => {
$(
impl<T: std::fmt::Display> std::fmt::Display for $tpe<T> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "{}", self.iter().map(|x| format!("{}", x)).collect::<Vec<_>>().join(" "))
}
}
impl<T: std::fmt::Debug> std::fmt::Debug for $tpe<T> {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
self.data.fmt(f)
}
}
impl<'a, T> IntoIterator for &'a $tpe<T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
#[inline]
fn into_iter(self) -> Iter<'a, T> {
self.iter()
}
}
)*
};
}
impl_traits!(List, lst);
impl<T> From<Vec<T>> for List<T> {
#[inline]
fn from(vec: Vec<T>) -> Self {
List { data: vec }
}
}
impl<T: Clone> From<&[T]> for List<T> {
#[inline]
fn from(slice: &[T]) -> Self {
slice.iter().cloned().collect()
}
}
impl<T> Deref for List<T> {
type Target = lst<T>;
#[inline]
fn deref(&self) -> &lst<T> {
lst::new(&self.data)
}
}
impl<T> DerefMut for List<T> {
#[inline]
fn deref_mut(&mut self) -> &mut lst<T> {
lst::new_mut(&mut self.data)
}
}
#[macro_export]
macro_rules! list {
() => { $crate::arraylist::List::new() };
($($v:expr),+ $(,)?) => { $crate::arraylist::List::from([$($v),+].to_vec()) };
($v:expr; $a:expr) => { $crate::arraylist::List::init($v, $a)};
($v:expr; $a:expr; $($rest:expr);+) => { $crate::arraylist::List::init(list!($v; $($rest);+), $a) };
}
#[allow(non_camel_case_types)]
#[derive(PartialEq, Eq, PartialOrd, Ord)]
#[repr(transparent)]
pub struct lst<T> {
data: [T],
}
impl<T> lst<T> {
#[inline]
pub fn new(slice: &[T]) -> &Self {
unsafe { &*(slice as *const [T] as *const Self) }
}
#[inline]
pub fn new_mut(slice: &mut [T]) -> &mut Self {
unsafe { &mut *(slice as *mut [T] as *mut Self) }
}
#[inline]
pub fn lens(&self) -> isize {
self.data.len() as isize
}
#[inline]
pub fn list(&self) -> List<T>
where
T: Clone,
{
self.cloned().collect()
}
#[inline]
fn at(&self, index: isize) -> &T {
if cfg!(debug_assertions) {
self.data.index(index as usize)
} else {
unsafe { self.data.get_unchecked(index as usize) }
}
}
#[inline]
fn at_mut(&mut self, index: isize) -> &mut T {
if cfg!(debug_assertions) {
self.data.index_mut(index as usize)
} else {
unsafe { self.data.get_unchecked_mut(index as usize) }
}
}
#[inline]
pub fn as_slice(&self, range: impl RangeBounds<isize>) -> &lst<T> {
if cfg!(debug_assertions) {
lst::new(self.data.index(self.rgm(range)))
} else {
unsafe { lst::new(self.data.get_unchecked(self.rgm(range))) }
}
}
#[inline]
pub fn as_slice_mut(&mut self, range: impl RangeBounds<isize>) -> &mut lst<T> {
if cfg!(debug_assertions) {
lst::new_mut(self.data.index_mut(self.rgm(range)))
} else {
let r = self.rgm(range);
unsafe { lst::new_mut(self.data.get_unchecked_mut(r)) }
}
}
#[inline]
pub fn cloned(&self) -> std::iter::Cloned<Iter<T>>
where
T: Clone,
{
self.iter().cloned()
}
#[inline]
pub fn map<B, F>(&self, f: F) -> List<B>
where
T: Clone,
F: FnMut(T) -> B,
{
self.cloned().map(f).collect()
}
#[inline]
fn rgm(&self, r: impl RangeBounds<isize>) -> Range<usize> {
(match r.start_bound() {
Bound::Included(x) => *x as usize,
Bound::Excluded(x) => *x as usize + 1,
_ => 0,
})
.max(0)..(match r.end_bound() {
Bound::Included(x) => *x as usize + 1,
Bound::Excluded(x) => *x as usize,
_ => self.len(),
})
.min(self.len())
}
}
impl lst<isize> {}
impl<T> Deref for lst<T> {
type Target = [T];
#[inline]
fn deref(&self) -> &[T] {
&self.data
}
}
impl<T> DerefMut for lst<T> {
#[inline]
fn deref_mut(&mut self) -> &mut [T] {
&mut self.data
}
}
impl<'a, T> From<&'a [T]> for &'a lst<T> {
#[inline]
fn from(slice: &'a [T]) -> Self {
lst::new(slice)
}
}
}
pub mod modulo {
use crate::{impl_integer_functions, independent::integer::Int};
use std::cell::RefCell;
use std::fmt::Debug;
use std::marker::PhantomData;
use std::ops::*;
use std::thread::LocalKey;
#[derive(PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
#[repr(transparent)]
pub struct ModInt<T> {
pub val: u32,
phantom: PhantomData<fn() -> T>,
}
impl<T: Modulus> Debug for ModInt<T> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
self.val.fmt(f)
}
}
impl<T: Modulus> ModInt<T> {
#[inline]
pub fn new<U: Int>(a: U) -> Self {
let x = a.to_i128();
ModInt::raw(x.rem_euclid(T::M as i128) as _)
}
#[inline]
pub fn pow<U: Int>(self, x: U) -> Self {
let mut n = x.to_i64();
let mut a = self;
let mut res = Self::raw(1);
while n > 0 {
if n & 1 == 1 {
res *= a;
}
a = a * a;
n >>= 1;
}
res
}
#[inline]
pub fn inv(self) -> Self {
self.pow(T::M - 2)
}
#[inline]
pub fn raw(val: u32) -> Self {
ModInt {
val,
phantom: PhantomData,
}
}
#[inline]
fn add_impl(self, other: Self) -> Self {
let mut ret = self.val + other.val;
if ret >= T::M {
ret -= T::M;
}
Self::raw(ret)
}
#[inline]
fn sub_impl(self, other: Self) -> Self {
let mut ret = self.val.wrapping_sub(other.val);
if ret >= T::M {
ret = ret.wrapping_add(T::M);
}
Self::raw(ret)
}
#[inline]
fn mul_impl(self, other: Self) -> Self {
Self::raw((u64::from(self.val) * u64::from(other.val) % u64::from(T::M)) as _)
}
#[inline]
fn div_impl(self, other: Self) -> Self {
self * other.inv()
}
#[inline]
fn rem_impl(self, other: Self) -> Self {
Self::raw(self.val % other.val)
}
}
pub trait Modulus: 'static + PartialEq + Eq + Copy + Clone + std::hash::Hash + Ord {
const M: u32;
fn butterfly_cache() -> &'static LocalKey<RefCell<Option<ButterflyCache<Self>>>>;
}
impl<T> std::fmt::Display for ModInt<T> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "{}", self.val)
}
}
macro_rules! impl_from_for_modint {
($($tpe:ident),*) => {
$(
impl<T: Modulus> From<$tpe> for ModInt<T> {
fn from(n: $tpe) -> Self {
Self::new(n)
}
}
)*
};
}
impl_from_for_modint!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize);
macro_rules! impl_assign {
($t1:ty, $t2:ty, $fa:ident, $f:ident, $f_impl:ident) => {
impl<T: Modulus> $t1 for ModInt<T> {
type Output = Self;
#[inline]
fn $f(self, other: Self) -> Self {
Self::$f_impl(self, other)
}
}
impl<T: Modulus> $t2 for ModInt<T> {
#[inline]
fn $fa(&mut self, other: Self) {
*self = self.$f(other);
}
}
};
}
impl_assign!(Add, AddAssign, add_assign, add, add_impl);
impl_assign!(Sub, SubAssign, sub_assign, sub, sub_impl);
impl_assign!(Mul, MulAssign, mul_assign, mul, mul_impl);
impl_assign!(Div, DivAssign, div_assign, div, div_impl);
impl_assign!(Rem, RemAssign, rem_assign, rem, rem_impl);
#[macro_export]
macro_rules! modint {
() => {
$crate::modint!(1000000007);
};
($m:literal) => {
$crate::modint!($m, ModValue);
#[allow(dead_code)]
type Z = $crate::modulo::ModInt<ModValue>;
};
($name:ident) => {
$crate::modint!($name, $name);
};
($value:expr, $name:ident) => {
#[derive(Debug, PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
pub enum $name {}
impl $crate::modulo::Modulus for $name {
const M: u32 = $value as _;
fn butterfly_cache() -> &'static ::std::thread::LocalKey<::std::cell::RefCell<::std::option::Option<$crate::modulo::ButterflyCache<Self>>>> {
thread_local! {
static BUTTERFLY_CACHE: ::std::cell::RefCell<::std::option::Option<$crate::modulo::ButterflyCache<$name>>> = ::std::default::Default::default();
}
&BUTTERFLY_CACHE
}
}
};
}
impl<T: Modulus> Int for ModInt<T> {
impl_integer_functions!(|s: &Self| s.val, |x| Self::new(x));
}
pub struct ButterflyCache<T> {
pub sum_e: Vec<ModInt<T>>,
pub sum_ie: Vec<ModInt<T>>,
}
}
pub mod scanner {
use crate::arraylist::List;
use std::io::{stdin, BufReader, Bytes, Read, Stdin};
use std::str::FromStr;
pub struct Scanner {
buf: Bytes<BufReader<Stdin>>,
}
impl Scanner {
pub fn new() -> Scanner {
Scanner {
buf: BufReader::new(stdin()).bytes(),
}
}
#[inline]
fn token<T: std::iter::FromIterator<char>>(&mut self) -> T {
self.buf
.by_ref()
.map(|c| c.unwrap() as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect()
}
#[inline]
pub fn read<T: FromStr>(&mut self) -> T {
self.string().parse().ok().unwrap()
}
#[inline]
pub fn readn<T: FromStr>(&mut self, n: isize) -> List<T> {
(0..n).map(|_| self.read::<T>()).collect()
}
#[inline]
pub fn string(&mut self) -> String {
self.token()
}
#[inline]
pub fn int(&mut self) -> isize {
self.read()
}
}
}