結果
| 問題 | No.3682 きあいのハチマキ |
| コンテスト | |
| ユーザー |
 cacampu
|
| 提出日時 | 2026-09-05 15:47:27 |
| 言語 | Rust (1.97.1 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 17 ms / 2,000 ms |
| + 985µs | |
| コード長 | 15,026 bytes |
| 記録 | |
| コンパイル時間 | 3,450 ms |
| コンパイル使用メモリ | 202,888 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2026-09-05 15:47:50 |
| 合計ジャッジ時間 | 5,148 ms |
|
ジャッジサーバーID （参考情報） |
judge4_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 2 |
ソースコード
pub use __cargo_equip::prelude::*;
use cplib_math_modint::ModInt998244353 as mint;
use proconio::{fastout, input};
fn solve() -> mint {
input! {
c: (usize,usize,usize),
g: (usize,usize,usize),
}
let xg = (g.0 - 1) / c.1;
let xc = (c.0 - 1) / g.1;
let ss = if c.2 < g.2 {
mint::new(1) / mint::new(10)
} else if c.2 > g.2 {
mint::new(1)
} else {
mint::new(1) / mint::new(2) + mint::new(1) / mint::new(20)
};
let r0 = mint::new(9) / mint::new(10);
let r1 = mint::new(1) / mint::new(10);
let r = r1 * r1;
let ans;
if xc <= xg {
let p0 = r0 * r1.pow((xg - xc) as u64) * ss;
ans = p0 / (mint::new(1) - r);
} else {
let p = r0 * (mint::new(1) - r1.pow((xc - xg) as u64)) / (mint::new(1) - r1);
let q0 = r0 * r1.pow((xc - xg) as u64) * ss;
let q = q0 / (mint::new(1) - r);
ans = p + q;
}
ans
}
#[fastout]
fn main() {
input! {
t: usize,
}
for _ in 0..t {
println!("{}", solve());
}
}
// The following code was expanded by `cargo-equip`.
/// # Bundled libraries
///
/// - `git+https://github.com/cacampu/cplib-rs#algebra@0.1.0` licensed under `MIT` as `crate::__cargo_equip::crates::cplib_core_algebra`
/// - `git+https://github.com/cacampu/cplib-rs#modint@0.1.0` licensed under `MIT` as `crate::__cargo_equip::crates::cplib_math_modint`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod cplib_core_algebra {use std::marker::PhantomData;use std::ops::{Add,BitXor,Mul,Sub};pub trait Monoid{type T:Clone;fn identity(&self)->Self::T;fn binary_op(&self,a:&Self::T,b:&Self::T)->Self::T;}pub trait Group:Monoid{fn inv_binary_op(&self,a:&Self::T,b:&Self::T)->Self::T;fn inverse(&self,a:&Self::T)->Self::T{self.inv_binary_op(&self.identity(),a)}}macro_rules!def_marker_monoid{($($name:ident),*)=>{$(pub struct$name<T>(PhantomData<fn()->T>);impl<T>$name<T>{pub fn new()->Self{Self(PhantomData)}}impl<T>Default for$name<T>{fn default()->Self{Self::new()}}impl<T>Clone for$name<T>{fn clone(&self)->Self{*self}}impl<T>Copy for$name<T>{})*};}def_marker_monoid!(Min,Max,MinMax,Sum,Prod,Xor,BitAnd,BitOr,Gcd,Lcm);impl<T:Clone>MinMax<T>{#[inline]pub fn of(value:T)->(T,T){(value.clone(),value)}}pub trait Zero{fn zero()->Self;}pub trait One{fn one()->Self;}pub trait Bounded{fn min_value()->Self;fn max_value()->Self;}pub trait AllOnes{fn all_ones()->Self;}impl<T:Clone+Ord+Bounded>Monoid for Min<T>{type T=T;#[inline]fn identity(&self)->T{T::max_value()}#[inline]fn binary_op(&self,a:&T,b:&T)->T{if a<=b{a.clone()}else{b.clone()}}}impl<T:Clone+Ord+Bounded>Monoid for Max<T>{type T=T;#[inline]fn identity(&self)->T{T::min_value()}#[inline]fn binary_op(&self,a:&T,b:&T)->T{if a>=b{a.clone()}else{b.clone()}}}impl<T:Clone+Ord+Bounded>Monoid for MinMax<T>{type T=(T,T);#[inline]fn identity(&self)->(T,T){(T::max_value(),T::min_value())}#[inline]fn binary_op(&self,a:&(T,T),b:&(T,T))->(T,T){let lo=if a.0<=b.0{a.0.clone()}else{b.0.clone()};let hi=if a.1>=b.1{a.1.clone()}else{b.1.clone()};(lo,hi)}}impl<T:Clone+Zero+Add<Output=T>>Monoid for Sum<T>{type T=T;#[inline]fn identity(&self)->T{T::zero()}#[inline]fn binary_op(&self,a:&T,b:&T)->T{a.clone()+b.clone()}}impl<T:Clone+Zero+Add<Output=T>+Sub<Output=T>>Group for Sum<T>{#[inline]fn inv_binary_op(&self,a:&T,b:&T)->T{a.clone()-b.clone()}}impl<T:Clone+One+Mul<Output=T>>Monoid for Prod<T>{type T=T;#[inline]fn identity(&self)->T{T::one()}#[inline]fn binary_op(&self,a:&T,b:&T)->T{a.clone()*b.clone()}}impl<T:Clone+Zero+BitXor<Output=T>>Monoid for Xor<T>{type T=T;#[inline]fn identity(&self)->T{T::zero()}#[inline]fn binary_op(&self,a:&T,b:&T)->T{a.clone()^b.clone()}}impl<T:Clone+Zero+BitXor<Output=T>>Group for Xor<T>{#[inline]fn inv_binary_op(&self,a:&T,b:&T)->T{a.clone()^b.clone()}}impl<T:Clone+AllOnes+std::ops::BitAnd<Output=T>>Monoid for BitAnd<T>{type T=T;#[inline]fn identity(&self)->T{T::all_ones()}#[inline]fn binary_op(&self,a:&T,b:&T)->T{a.clone()&b.clone()}}impl<T:Clone+Zero+std::ops::BitOr<Output=T>>Monoid for BitOr<T>{type T=T;#[inline]fn identity(&self)->T{T::zero()}#[inline]fn binary_op(&self,a:&T,b:&T)->T{a.clone()|b.clone()}}macro_rules!impl_num_traits{($($t:ty),*)=>{$(impl Zero for$t{#[inline]fn zero()->$t{0}}impl One for$t{#[inline]fn one()->$t{1}}impl Bounded for$t{#[inline]fn min_value()->$t{<$t>::MIN}#[inline]fn max_value()->$t{<$t>::MAX}}impl AllOnes for$t{#[inline]fn all_ones()->$t{!0}}impl Monoid for Gcd<$t>{type T=$t;#[doc=" gcd(0, x) = x なので単位元は 0。"]#[inline]fn identity(&self)->$t{0}#[inline]fn binary_op(&self,a:&$t,b:&$t)->$t{Gcd::<$t>::of(*a,*b)}}impl Monoid for Lcm<$t>{type T=$t;#[inline]fn identity(&self)->$t{1}#[inline]fn binary_op(&self,a:&$t,b:&$t)->$t{Lcm::<$t>::of(*a,*b)}})*};}impl_num_traits!(usize,isize,u8,u16,u32,u64,u128,i8,i16,i32,i64,i128);macro_rules!impl_gcd_lcm{(@norm signed$x:expr)=>{($x).wrapping_abs()};(@norm unsigned$x:expr)=>{$x};($sign:ident:$($t:ty),*)=>{$(impl Gcd<$t>{#[doc=" ユークリッドの互除法。結果は非負。"]pub fn of(a:$t,b:$t)->$t{let(mut a,mut b)=(a,b);while b!=0{let r=a%b;a=b;b=r;}impl_gcd_lcm!(@norm$sign a)}}impl Lcm<$t>{#[doc=" `lcm(0, x) = 0`。オーバーフローは呼び出し側の責任。"]pub fn of(a:$t,b:$t)->$t{if a==0||b==0{return 0;}let g=Gcd::<$t>::of(a,b);impl_gcd_lcm!(@norm$sign a/g*b)}})*};}impl_gcd_lcm!(unsigned:usize,u8,u16,u32,u64,u128);impl_gcd_lcm!(signed:isize,i8,i16,i32,i64,i128);pub struct FnMonoid<T,F>{identity:T,op:F,}impl<T,F>FnMonoid<T,F>where T:Clone,F:Fn(&T,&T)->T,{pub fn new(identity:T,op:F)->Self{Self{identity,op}}}impl<T,F>Monoid for FnMonoid<T,F>where T:Clone,F:Fn(&T,&T)->T,{type T=T;#[inline]fn identity(&self)->T{self.identity.clone()}#[inline]fn binary_op(&self,a:&T,b:&T)->T{(self.op)(a,b)}}pub struct FnGroup<T,F,G>{identity:T,op:F,inv_op:G,}impl<T,F,G>FnGroup<T,F,G>where T:Clone,F:Fn(&T,&T)->T,G:Fn(&T,&T)->T,{pub fn new(identity:T,op:F,inv_op:G)->Self{Self{identity,op,inv_op,}}}impl<T,F,G>Monoid for FnGroup<T,F,G>where T:Clone,F:Fn(&T,&T)->T,G:Fn(&T,&T)->T,{type T=T;#[inline]fn identity(&self)->T{self.identity.clone()}#[inline]fn binary_op(&self,a:&T,b:&T)->T{(self.op)(a,b)}}impl<T,F,G>Group for FnGroup<T,F,G>where T:Clone,F:Fn(&T,&T)->T,G:Fn(&T,&T)->T,{#[inline]fn inv_binary_op(&self,a:&T,b:&T)->T{(self.inv_op)(a,b)}}}
pub mod cplib_math_modint {use crate::__cargo_equip::preludes::cplib_math_modint::*;use std::cell::Cell;use std::fmt;use std::iter::{Product,Sum};use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign};use algebra::{One,Zero};#[derive(Clone,Copy,PartialEq,Eq,Hash,Default,PartialOrd,Ord)]pub struct ModInt<const M:u32>{val:u32,}pub type ModInt998244353=ModInt<998_244_353>;pub type ModInt1000000007=ModInt<1_000_000_007>;impl<const M:u32>ModInt<M>{const ASSERT_MOD:()=assert!(M>=1&&M<(1<<31),"modulus must be in [1, 2^31)");#[inline]pub fn raw(value:u32)->Self{()=Self::ASSERT_MOD;debug_assert!(value<M,"raw value must be less than the modulus");Self{val:value}}#[inline]pub fn val(self)->u32{self.val}#[inline]pub fn modulus()->u32{M}}impl<const M:u32>Add for ModInt<M>{type Output=Self;#[inline]fn add(self,rhs:Self)->Self{let mut val=self.val+rhs.val;if val>=M{val-=M;}Self::raw(val)}}impl<const M:u32>Sub for ModInt<M>{type Output=Self;#[inline]fn sub(self,rhs:Self)->Self{let mut val=self.val.wrapping_sub(rhs.val);if val>=M{val=val.wrapping_add(M);}Self::raw(val)}}impl<const M:u32>Mul for ModInt<M>{type Output=Self;#[inline]fn mul(self,rhs:Self)->Self{Self::raw((self.val as u64*rhs.val as u64%M as u64)as u32)}}#[derive(Clone,Copy,PartialEq,Eq,Hash,Default,PartialOrd,Ord)]pub struct DynamicModInt<const ID:usize=0>{val:u32,}pub type DynModInt=DynamicModInt<0>;pub const MAX_DYNAMIC_IDS:usize=16;thread_local!{static BARRETTS:[Cell<Barrett>;MAX_DYNAMIC_IDS]=const{[const{Cell::new(Barrett::UNSET)};MAX_DYNAMIC_IDS]};}impl<const ID:usize>DynamicModInt<ID>{const ASSERT_ID:()=assert!(ID<MAX_DYNAMIC_IDS,"ID must be less than MAX_DYNAMIC_IDS");pub fn set_modulus(m:u32){()=Self::ASSERT_ID;assert!((1..(1<<31)).contains(&m),"modulus must be in [1, 2^31), got {m}");BARRETTS.with(|bs|bs[ID].set(Barrett::new(m)));}#[inline]fn barrett()->Barrett{()=Self::ASSERT_ID;let b=BARRETTS.with(|bs|bs[ID].get());assert!(b.m!=0,"modulus of DynamicModInt<{ID}> is not set; call set_modulus first");b}#[inline]pub fn raw(value:u32)->Self{debug_assert!(value<Self::modulus());Self{val:value}}#[inline]pub fn val(self)->u32{self.val}#[inline]pub fn modulus()->u32{Self::barrett().m}}impl<const ID:usize>Add for DynamicModInt<ID>{type Output=Self;#[inline]fn add(self,rhs:Self)->Self{let m=Self::modulus();let mut val=self.val+rhs.val;if val>=m{val-=m;}Self{val}}}impl<const ID:usize>Sub for DynamicModInt<ID>{type Output=Self;#[inline]fn sub(self,rhs:Self)->Self{let m=Self::modulus();let mut val=self.val.wrapping_sub(rhs.val);if val>=m{val=val.wrapping_add(m);}Self{val}}}impl<const ID:usize>Mul for DynamicModInt<ID>{type Output=Self;#[inline]fn mul(self,rhs:Self)->Self{Self{val:Self::barrett().mul(self.val,rhs.val),}}}#[derive(Clone,Copy)]struct Barrett{m:u32,im:u64,}impl Barrett{const UNSET:Self=Self{m:0,im:0};fn new(m:u32)->Self{Self{m,im:(!0u64/m as u64).wrapping_add(1),}}#[inline]fn mul(&self,a:u32,b:u32)->u32{let z=a as u64*b as u64;let x=((z as u128*self.im as u128)>>64)as u64;let v=z.wrapping_sub(x.wrapping_mul(self.m as u64))as u32;if v>=self.m{v.wrapping_add(self.m)}else{v}}}macro_rules!impl_modint_common{($ty:ident,$param:ident,$ptype:ty)=>{impl<const$param:$ptype>$ty<$param>{#[doc=" 剰余を取ってから構築する。負の値も受け付ける。"]#[inline]pub fn new<T:RemEuclidU32>(value:T)->Self{Self::raw(value.rem_euclid_u32(Self::modulus()))}#[doc=" `self^n`。繰り返し二乗法で `O(log n)`。"]pub fn pow(self,mut n:u64)->Self{let mut ret=Self::new(1u32);let mut base=self;while n>0{if n&1==1{ret*=base;}base*=base;n>>=1;}ret}#[doc=" 平方根のひとつ。存在しなければ `None`。"]#[doc=" **法が素数であることを仮定する** (Tonelli-Shanks)。"]#[doc=""]#[doc=" 解が2つある場合にどちらを返すかは決めていない。"]#[doc=" もう一方は `-r` で得られる。"]pub fn sqrt(self)->Option<Self>{let m=Self::modulus();if m==2||self.val<=1{return Some(self);}let one=Self::new(1u32);if self.pow(((m-1)/2)as u64)!=one{return None;}let mut q=m-1;let mut s=0u32;while q%2==0{q/=2;s+=1;}if s==1{return Some(self.pow(((m+1)/4)as u64));}let mut z=Self::new(2u32);while z.pow(((m-1)/2)as u64)==one{z+=one;}let mut level=s;let mut c=z.pow(q as u64);let mut t=self.pow(q as u64);let mut r=self.pow(q.div_ceil(2)as u64);while t!=one{let mut i=0u32;let mut t2=t;while t2!=one{t2*=t2;i+=1;}let b=c.pow(1u64<<(level-i-1));level=i;c=b*b;t*=c;r*=b;}Some(r)}#[doc=" 乗法逆元。法と互いに素でないとパニックする。"]#[doc=" 法が素数でなくても互いに素なら求まる。"]pub fn inv(self)->Self{let m=Self::modulus();let(g,x)=inv_gcd(self.val as i64,m as i64);assert_eq!(g,1,"{} is not invertible modulo {}",self.val,m);Self::raw(x as u32)}}impl<const$param:$ptype>Zero for$ty<$param>{#[inline]fn zero()->Self{Self::raw(0)}}impl<const$param:$ptype>One for$ty<$param>{#[inline]fn one()->Self{Self::new(1u32)}}impl<const$param:$ptype>Neg for$ty<$param>{type Output=Self;#[inline]fn neg(self)->Self{Self::raw(0)-self}}#[allow(clippy::suspicious_arithmetic_impl)]impl<const$param:$ptype>Div for$ty<$param>{type Output=Self;#[inline]fn div(self,rhs:Self)->Self{self*rhs.inv()}}impl<const$param:$ptype>fmt::Display for$ty<$param>{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{self.val.fmt(f)}}impl<const$param:$ptype>fmt::Debug for$ty<$param>{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{self.val.fmt(f)}}impl<const$param:$ptype>Sum for$ty<$param>{fn sum<I:Iterator<Item=Self>>(iter:I)->Self{iter.fold(Self::raw(0),|a,b|a+b)}}impl<'a,const$param:$ptype>Sum<&'a Self>for$ty<$param>{fn sum<I:Iterator<Item=&'a Self>>(iter:I)->Self{iter.fold(Self::raw(0),|a,b|a+*b)}}impl<const$param:$ptype>Product for$ty<$param>{fn product<I:Iterator<Item=Self>>(iter:I)->Self{iter.fold(Self::new(1u32),|a,b|a*b)}}impl<'a,const$param:$ptype>Product<&'a Self>for$ty<$param>{fn product<I:Iterator<Item=&'a Self>>(iter:I)->Self{iter.fold(Self::new(1u32),|a,b|a**b)}}impl_modint_common!(@assign$ty,$param,$ptype,AddAssign,add_assign,+);impl_modint_common!(@assign$ty,$param,$ptype,SubAssign,sub_assign,-);impl_modint_common!(@assign$ty,$param,$ptype,MulAssign,mul_assign,*);impl_modint_common!(@assign$ty,$param,$ptype,DivAssign,div_assign,/);impl_modint_common!(@ref$ty,$param,$ptype,Add,add);impl_modint_common!(@ref$ty,$param,$ptype,Sub,sub);impl_modint_common!(@ref$ty,$param,$ptype,Mul,mul);impl_modint_common!(@ref$ty,$param,$ptype,Div,div);impl_modint_common!(@from$ty,$param,$ptype,u8,u16,u32,u64,u128,usize,i8,i16,i32,i64,i128,isize);};(@assign$ty:ident,$param:ident,$ptype:ty,$trait:ident,$method:ident,$op:tt)=>{impl<const$param:$ptype>$trait for$ty<$param>{#[inline]fn$method(&mut self,rhs:Self){*self=*self$op rhs;}}};(@ref$ty:ident,$param:ident,$ptype:ty,$trait:ident,$method:ident)=>{impl<const$param:$ptype>$trait<&$ty<$param>>for$ty<$param>{type Output=$ty<$param>;#[inline]fn$method(self,rhs:&$ty<$param>)->$ty<$param>{$trait::$method(self,*rhs)}}impl<const$param:$ptype>$trait<$ty<$param>>for&$ty<$param>{type Output=$ty<$param>;#[inline]fn$method(self,rhs:$ty<$param>)->$ty<$param>{$trait::$method(*self,rhs)}}impl<const$param:$ptype>$trait<&$ty<$param>>for&$ty<$param>{type Output=$ty<$param>;#[inline]fn$method(self,rhs:&$ty<$param>)->$ty<$param>{$trait::$method(*self,*rhs)}}};(@from$ty:ident,$param:ident,$ptype:ty,$($t:ty),*)=>{$(impl<const$param:$ptype>From<$t>for$ty<$param>{#[inline]fn from(value:$t)->Self{Self::new(value)}})*};}impl_modint_common!(ModInt,M,u32);impl_modint_common!(DynamicModInt,ID,usize);pub trait RemEuclidU32{fn rem_euclid_u32(self,m:u32)->u32;}macro_rules!impl_rem_euclid{(unsigned:$($t:ty),*)=>{$(impl RemEuclidU32 for$t{#[inline]fn rem_euclid_u32(self,m:u32)->u32{(self as u128%m as u128)as u32}})*};(signed:$($t:ty),*)=>{$(impl RemEuclidU32 for$t{#[inline]fn rem_euclid_u32(self,m:u32)->u32{(self as i128).rem_euclid(m as i128)as u32}})*};}impl_rem_euclid!(unsigned:u8,u16,u32,u64,u128,usize);impl_rem_euclid!(signed:i8,i16,i32,i64,i128,isize);pub fn inv_gcd(a:i64,b:i64)->(i64,i64){let a=a.rem_euclid(b);if a==0{return(b,0);}let(mut s,mut t)=(b,a);let(mut m0,mut m1)=(0i64,1i64);while t!=0{let u=s/t;s-=t*u;m0-=m1*u;std::mem::swap(&mut s,&mut t);std::mem::swap(&mut m0,&mut m1);}if m0<0{m0+=b/s;}(s,m0)}}
}
pub(crate) mod macros {
pub mod cplib_core_algebra {}
pub mod cplib_math_modint {}
}
pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
mod preludes {
pub mod cplib_core_algebra {}
pub mod cplib_math_modint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::cplib_core_algebra as algebra;}
}
}