// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } use ntk_rand::Xorshift; fn main() { input! { n: usize, k: usize, t: [usize; k], u: [usize; k], } let mut rng = ntk_rand::Xorshift::new(); for _ in 0..n { let b = rng.gen_range(0..1000); let m = (b as f64 * 1.052) as usize; let e = (m as f64 / 12.345) as usize; println!("{} {} {}", b, m, e); } } pub fn get_time() -> f64 { let t = std::time::SystemTime::now() .duration_since(std::time::UNIX_EPOCH) .unwrap(); t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9 } struct Timer { start_time: f64, } impl Timer { fn new() -> Timer { Timer { start_time: get_time(), } } fn get_time(&self) -> f64 { get_time() - self.start_time } } #[allow(dead_code)] mod ntk_rand { pub trait Distribution { /// Generate a random value of `T`, using `rng` as the source of randomness. fn sample(&self, rng: &mut Xorshift) -> T; } pub struct Xorshift { seed: T, } impl Xorshift { pub fn new() -> Self { Xorshift { seed: 0x139408dcbbf7a44, } } pub fn seed_from_u64(seed: usize) -> Xorshift { Xorshift { seed } } fn gen(&mut self) -> usize { self.seed = self.seed ^ (self.seed << 13); self.seed = self.seed ^ (self.seed >> 7); self.seed = self.seed ^ (self.seed << 17); self.seed } pub fn rand(&mut self) -> usize { self.gen() } fn sample>(&mut self, distr: D) -> T { distr.sample(self) } pub fn gen_bool(&mut self, p: f64) -> bool { let d = Bernoulli::new(p).unwrap(); self.sample(d) } pub fn gen_range(&mut self, range: R) -> T where T: SampleUniform, R: SampleRange, { range.sample_single(self) } } pub struct Uniform(X::Sampler); impl Uniform { pub fn new(low: B1, high: B2) -> Uniform where B1: SampleBorrow + Sized, B2: SampleBorrow + Sized, { Uniform(X::Sampler::new(low, high)) } pub fn new_inclusive(low: B1, high: B2) -> Uniform where B1: SampleBorrow + Sized, B2: SampleBorrow + Sized, { Uniform(X::Sampler::new_inclusive(low, high)) } } impl Distribution for Uniform { fn sample(&self, rng: &mut Xorshift) -> X { self.0.sample(rng) } } pub trait UniformSampler: Sized { /// The type sampled by this implementation. type X; fn new(low: B1, high: B2) -> Self where B1: SampleBorrow + Sized, B2: SampleBorrow + Sized; fn new_inclusive(low: B1, high: B2) -> Self where B1: SampleBorrow + Sized, B2: SampleBorrow + Sized; /// Sample a value. fn sample(&self, rng: &mut Xorshift) -> Self::X; fn sample_single(low: B1, high: B2, rng: &mut Xorshift) -> Self::X where B1: SampleBorrow + Sized, B2: SampleBorrow + Sized, { let uniform: Self = UniformSampler::new(low, high); uniform.sample(rng) } fn sample_single_inclusive(low: B1, high: B2, rng: &mut Xorshift) -> Self::X where B1: SampleBorrow + Sized, B2: SampleBorrow + Sized, { let uniform: Self = UniformSampler::new_inclusive(low, high); uniform.sample(rng) } } impl From> for Uniform { fn from(r: core::ops::Range) -> Uniform { Uniform::new(r.start, r.end) } } impl From> for Uniform { fn from(r: core::ops::RangeInclusive) -> Uniform { Uniform::new_inclusive(r.start(), r.end()) } } pub trait SampleUniform: Sized { /// The `UniformSampler` implementation supporting type `X`. type Sampler: UniformSampler; } pub trait SampleBorrow { /// Immutably borrows from an owned value. See [`Borrow::borrow`] /// /// [`Borrow::borrow`]: std::borrow::Borrow::borrow fn borrow(&self) -> &Borrowed; } impl SampleBorrow for Borrowed where Borrowed: SampleUniform, { #[inline(always)] fn borrow(&self) -> &Borrowed { self } } impl<'a, Borrowed> SampleBorrow for &'a Borrowed where Borrowed: SampleUniform, { #[inline(always)] fn borrow(&self) -> &Borrowed { *self } } /// Range that supports generating a single sample efficiently. /// /// Any type implementing this trait can be used to specify the sampled range /// for `Rng::gen_range`. pub trait SampleRange { /// Generate a sample from the given range. fn sample_single(self, rng: &mut Xorshift) -> T; /// Check whether the range is empty. fn is_empty(&self) -> bool; } impl SampleRange for core::ops::Range { #[inline] fn sample_single(self, rng: &mut Xorshift) -> T { T::Sampler::sample_single(self.start, self.end, rng) } #[inline] fn is_empty(&self) -> bool { // !(self.start >= self.end) self.start < self.end } } impl SampleRange for core::ops::RangeInclusive { #[inline] fn sample_single(self, rng: &mut Xorshift) -> T { T::Sampler::sample_single_inclusive(self.start(), self.end(), rng) } #[inline] fn is_empty(&self) -> bool { // !(self.start() <= self.end()) self.start() > self.end() } } pub trait WideningMultiply { type Output; fn wmul(self, x: RHS) -> Self::Output; } macro_rules! wmul_impl { ($ty:ty, $wide:ty, $shift:expr) => { impl WideningMultiply for $ty { type Output = ($ty, $ty); #[inline(always)] fn wmul(self, x: $ty) -> Self::Output { let tmp = (self as $wide) * (x as $wide); ((tmp >> $shift) as $ty, tmp as $ty) } } }; // simd bulk implementation ($(($ty:ident, $wide:ident),)+, $shift:expr) => { $( impl WideningMultiply for $ty { type Output = ($ty, $ty); #[inline(always)] fn wmul(self, x: $ty) -> Self::Output { // For supported vectors, this should compile to a couple // supported multiply & swizzle instructions (no actual // casting). // TODO: optimize let y: $wide = self.cast(); let x: $wide = x.cast(); let tmp = y * x; let hi: $ty = (tmp >> $shift).cast(); let lo: $ty = tmp.cast(); (hi, lo) } } )+ }; } wmul_impl! { u8, u16, 8 } wmul_impl! { u16, u32, 16 } wmul_impl! { u32, u64, 32 } wmul_impl! { u64, u128, 64 } macro_rules! wmul_impl_large { ($ty:ty, $half:expr) => { impl WideningMultiply for $ty { type Output = ($ty, $ty); #[inline(always)] fn wmul(self, b: $ty) -> Self::Output { const LOWER_MASK: $ty = !0 >> $half; let mut low = (self & LOWER_MASK).wrapping_mul(b & LOWER_MASK); let mut t = low >> $half; low &= LOWER_MASK; t += (self >> $half).wrapping_mul(b & LOWER_MASK); low += (t & LOWER_MASK) << $half; let mut high = t >> $half; t = low >> $half; low &= LOWER_MASK; t += (b >> $half).wrapping_mul(self & LOWER_MASK); low += (t & LOWER_MASK) << $half; high += t >> $half; high += (self >> $half).wrapping_mul(b >> $half); (high, low) } } }; // simd bulk implementation (($($ty:ty,)+) $scalar:ty, $half:expr) => { $( impl WideningMultiply for $ty { type Output = ($ty, $ty); #[inline(always)] fn wmul(self, b: $ty) -> Self::Output { // needs wrapping multiplication const LOWER_MASK: $scalar = !0 >> $half; let mut low = (self & LOWER_MASK) * (b & LOWER_MASK); let mut t = low >> $half; low &= LOWER_MASK; t += (self >> $half) * (b & LOWER_MASK); low += (t & LOWER_MASK) << $half; let mut high = t >> $half; t = low >> $half; low &= LOWER_MASK; t += (b >> $half) * (self & LOWER_MASK); low += (t & LOWER_MASK) << $half; high += t >> $half; high += (self >> $half) * (b >> $half); (high, low) } } )+ }; } wmul_impl_large! { u128, 64 } macro_rules! wmul_impl_usize { ($ty:ty) => { impl WideningMultiply for usize { type Output = (usize, usize); #[inline(always)] fn wmul(self, x: usize) -> Self::Output { let (high, low) = (self as $ty).wmul(x as $ty); (high as usize, low as usize) } } }; } #[cfg(target_pointer_width = "16")] wmul_impl_usize! { u16 } #[cfg(target_pointer_width = "32")] wmul_impl_usize! { u32 } #[cfg(target_pointer_width = "64")] wmul_impl_usize! { u64 } pub struct UniformInt { low: X, range: X, z: X, } macro_rules! uniform_int_impl { ($ty:ty, $unsigned:ident, $u_large:ident) => { impl SampleUniform for $ty { type Sampler = UniformInt<$ty>; } impl UniformSampler for UniformInt<$ty> { type X = $ty; #[inline] fn new(low_b: B1, high_b: B2) -> Self where B1: SampleBorrow + Sized, B2: SampleBorrow + Sized, { let low = *low_b.borrow(); let high = *high_b.borrow(); assert!(low < high, "Uniform::new called with `low >= high`"); UniformSampler::new_inclusive(low, high - 1) } #[inline] fn new_inclusive(low_b: B1, high_b: B2) -> Self where B1: SampleBorrow + Sized, B2: SampleBorrow + Sized, { let low = *low_b.borrow(); let high = *high_b.borrow(); assert!( low <= high, "Uniform::new_inclusive called with `low > high`" ); let unsigned_max = core::$u_large::MAX; let range = high.wrapping_sub(low).wrapping_add(1) as $unsigned; let ints_to_reject = if range > 0 { let range = $u_large::from(range); (unsigned_max - range + 1) % range } else { 0 }; UniformInt { low, range: range as $ty, z: ints_to_reject as $unsigned as $ty, } } #[inline] fn sample(&self, rng: &mut Xorshift<$u_large>) -> Self::X { let range = self.range as $unsigned as $u_large; if range > 0 { let unsigned_max = core::$u_large::MAX; let zone = unsigned_max - (self.z as $unsigned as $u_large); loop { let v: $u_large = rng.gen(); let (hi, lo) = v.wmul(range); if lo <= zone { return self.low.wrapping_add(hi as $ty); } } } else { rng.gen() } } #[inline] fn sample_single( low_b: B1, high_b: B2, rng: &mut Xorshift<$u_large>, ) -> Self::X where B1: SampleBorrow + Sized, B2: SampleBorrow + Sized, { let low = *low_b.borrow(); let high = *high_b.borrow(); assert!(low < high, "UniformSampler::sample_single: low >= high"); Self::sample_single_inclusive(low, high - 1, rng) } #[inline] fn sample_single_inclusive( low_b: B1, high_b: B2, rng: &mut Xorshift<$u_large>, ) -> Self::X where B1: SampleBorrow + Sized, B2: SampleBorrow + Sized, { let low = *low_b.borrow(); let high = *high_b.borrow(); assert!( low <= high, "UniformSampler::sample_single_inclusive: low > high" ); let range = high.wrapping_sub(low).wrapping_add(1) as $unsigned as $u_large; if range == 0 { return rng.gen(); } let zone = if core::$unsigned::MAX <= core::u16::MAX as $unsigned { let unsigned_max: $u_large = core::$u_large::MAX; let ints_to_reject = (unsigned_max - range + 1) % range; unsigned_max - ints_to_reject } else { (range << range.leading_zeros()).wrapping_sub(1) }; loop { let v: $u_large = rng.gen(); let (hi, lo) = v.wmul(range); if lo <= zone { return low.wrapping_add(hi as $ty); } } } } }; } uniform_int_impl! { usize, usize, usize } pub struct Bernoulli { p_int: u64, } const ALWAYS_TRUE: u64 = u64::max_value(); const SCALE: f64 = 2.0 * (1u64 << 63) as f64; #[derive(Clone, Copy, Debug, PartialEq, Eq)] pub enum BernoulliError { InvalidProbability, } impl Bernoulli { #[inline] pub fn new(p: f64) -> Result { if !(0.0..1.0).contains(&p) { if p == 1.0 { return Ok(Bernoulli { p_int: ALWAYS_TRUE }); } return Err(BernoulliError::InvalidProbability); } Ok(Bernoulli { p_int: (p * SCALE) as u64, }) } } impl Distribution for Bernoulli { #[inline] fn sample(&self, rng: &mut Xorshift) -> bool { if self.p_int == ALWAYS_TRUE { return true; } let v: u64 = rng.gen() as u64; v < self.p_int } } }