fn pow64(x: u64, y: u64, br: &BarrettReduction<u128>) -> u64Examples found in repository?
crates/competitive/src/math/arbitrary_mod_binomial.rs (line 200)
102 fn combination(&self, mut n: u64, mut k: u64) -> u64 {
103 if k > n {
104 return 0;
105 }
106 assert!(self.size as u64 >= n.min(self.m - 1));
107 if self.m < 1 << 31 {
108 let mut res = 1u64;
109 if self.e == 1 {
110 while n > 0 {
111 let (nn, n0) = self.bp.div_rem(n);
112 let (nk, k0) = self.bp.div_rem(k);
113 if n0 < k0 {
114 return 0;
115 }
116 res = self.bm.rem(res * self.fact[n0 as usize]);
117 res = self.bm.rem(res * self.inv_fact[k0 as usize]);
118 res = self.bm.rem(res * self.inv_fact[(n0 - k0) as usize]);
119 n = nn;
120 k = nk;
121 }
122 } else {
123 let mut r = n - k;
124 let mut e0 = 0;
125 let mut eq = 0;
126 let mut i = 0;
127 while n > 0 {
128 res = self.bm.rem(res * self.fact[self.bm.rem(n) as usize]);
129 res = self.bm.rem(res * self.inv_fact[self.bm.rem(k) as usize]);
130 res = self.bm.rem(res * self.inv_fact[self.bm.rem(r) as usize]);
131 n = self.bp.div(n);
132 k = self.bp.div(k);
133 r = self.bp.div(r);
134 let eps = n - k - r;
135 e0 += eps;
136 if e0 >= self.e as u64 {
137 return 0;
138 }
139 i += 1;
140 if i >= self.e {
141 eq ^= eps & 1;
142 }
143 }
144 if eq == 1 {
145 res = self.bm.rem(res * self.delta);
146 }
147 res = self
148 .bm
149 .rem(res * pow32(self.p as _, e0 as _, &self.bm) as u64);
150 }
151 res
152 } else {
153 let mut res = 1u128;
154 if self.e == 1 {
155 while n > 0 {
156 let (nn, n0) = self.bp.div_rem(n);
157 let (nk, k0) = self.bp.div_rem(k);
158 if n0 < k0 {
159 return 0;
160 }
161 res = self.bm128.rem(res * self.fact[n0 as usize] as u128);
162 res = self.bm128.rem(res * self.inv_fact[k0 as usize] as u128);
163 res = self
164 .bm128
165 .rem(res * self.inv_fact[(n0 - k0) as usize] as u128);
166 n = nn;
167 k = nk;
168 }
169 } else {
170 let mut r = n - k;
171 let mut e0 = 0;
172 let mut eq = 0;
173 let mut i = 0;
174 while n > 0 {
175 res = self
176 .bm128
177 .rem(res * self.fact[self.bm.rem(n) as usize] as u128);
178 res = self
179 .bm128
180 .rem(res * self.inv_fact[self.bm.rem(k) as usize] as u128);
181 res = self
182 .bm128
183 .rem(res * self.inv_fact[self.bm.rem(r) as usize] as u128);
184 n = self.bp.div(n);
185 k = self.bp.div(k);
186 r = self.bp.div(r);
187 let eps = n - k - r;
188 e0 += eps;
189 if e0 >= self.e as u64 {
190 return 0;
191 }
192 i += 1;
193 if i >= self.e {
194 eq ^= eps & 1;
195 }
196 }
197 if eq == 1 {
198 res = self.bm128.rem(res * self.delta as u128);
199 }
200 res = self.bm128.rem(res * pow64(self.p, e0, &self.bm128) as u128);
201 }
202 res as u64
203 }
204 }