Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

Commit1d34554

Browse files
committed
v0.3 with const generics
1 parenta2d9598 commit1d34554

File tree

5 files changed

+45
-43
lines changed

5 files changed

+45
-43
lines changed

‎.travis.yml

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
language:rust
22
rust:
3-
#- 1.51.0 # Version currently supported by Codeforces
3+
-1.51.0# Version currently supported by Codeforces
44
-stable
55
-beta
66
-nightly

‎Cargo.toml

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
[package]
22
name ="contest-algorithms"
3-
version ="0.2.1"
3+
version ="0.3.0"
44
authors = ["Aram Ebtekar"]
55
edition ="2018"
66

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -43,7 +43,7 @@ For help in getting started, you may check out [some of my past submissions](htt
4343

4444
My other goal is to appeal to developers who feel limited by ancient (yet still mainstream) programming languages, by demonstrating the power of modern techniques.
4545

46-
Rather than try to persuade you with words, this repository aims to show by example. If you're new toRust, see[Jim Blandy's*Why Rust?*](http://www.oreilly.com/programming/free/files/why-rust.pdf) for a brief introduction,orjust[dive in!](https://doc.rust-lang.org/book/)
46+
Rather than try to persuade you with words, this repository aims to show by example. If you'd like tolearn the language, I recommend[the official book](https://doc.rust-lang.org/book/)or[Programming Rust](https://www.amazon.com/Programming-Rust-Fast-Systems-Development-dp-1492052590/dp/1492052590).
4747

4848
#Contents
4949

‎src/math/fft.rs

Lines changed: 7 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
//! The Fast Fourier Transform (FFT) and Number Theoretic Transform (NTT)
2-
usesuper::num::{Complex,Field,PI};
2+
usesuper::num::{CommonField,Complex,PI};
33
use std::ops::{Add,Div,Mul,Neg,Sub};
44

55
// We can delete this struct once f64::reverse_bits() stabilizes.
@@ -30,6 +30,7 @@ impl Iterator for BitRevIterator {
3030
}
3131
}
3232

33+
#[allow(clippy::upper_case_acronyms)]
3334
pubtraitFFT:Sized +Copy{
3435
typeF:Sized
3536
+Copy
@@ -77,7 +78,7 @@ impl FFT for f64 {
7778
// 440564289 and 1713844692 are inverses and 2^27th roots of 1 mod (15<<27)+1
7879
// 125 and 2267742733 are inverses and 2^30th roots of 1 mod (3<<30)+1
7980
implFFTfori64{
80-
typeF =Field;
81+
typeF =CommonField;
8182

8283
constZERO:Self =0;
8384

@@ -197,9 +198,9 @@ mod test {
197198
let dft_v =dft_from_reals(&v, v.len());
198199
let new_v:Vec<i64> =idft_to_reals(&dft_v, v.len());
199200

200-
let seven =Field::from(7);
201-
let one =Field::from(1);
202-
let prim =Field::from(15_311_432).pow(1 <<21);
201+
let seven =CommonField::from(7);
202+
let one =CommonField::from(1);
203+
let prim =CommonField::from(15_311_432).pow(1 <<21);
203204
let prim2 = prim* prim;
204205

205206
let eval0 = seven + one + one;
@@ -230,6 +231,6 @@ mod test {
230231
let m =convolution(&vec![999],&vec![1_000_000]);
231232

232233
assert_eq!(z, vec![14,30,6,4]);
233-
assert_eq!(m, vec![999_000_000 -Field::MOD]);
234+
assert_eq!(m, vec![999_000_000 -super::super::num::COMMON_PRIME]);
234235
}
235236
}

‎src/math/num.rs

Lines changed: 35 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -165,87 +165,88 @@ impl Div for Complex {
165165
}
166166
}
167167

168-
/// Represents an element of the finite (Galois) field of prime order, given by
169-
/// MOD. Until Rust gets const generics, MOD must be hardcoded, but any prime in
170-
/// [1, 2^31.5] will work. If MOD is not prime, ring operations are still valid
168+
/// Represents an element of the finite (Galois) field of prime order M, where
169+
/// 1 <= M < 2^31.5. If M is not prime, ring operations are still valid
171170
/// but recip() and division are not. Note that the latter operations are also
172171
/// the slowest, so precompute any inverses that you intend to use frequently.
173172
#[derive(Clone,Copy,Eq,PartialEq,Debug,Hash)]
174-
pubstructField{
173+
pubstructModulo<constM:i64>{
175174
pubval:i64,
176175
}
177-
implField{
178-
pubconstMOD:i64 =998_244_353;// 2^23 * 7 * 17 + 1
179-
180-
/// Computes self^exp in O(log(exp)) time
181-
pubfnpow(mutself,mutexp:u64) ->Self{
176+
impl<constM:i64>Modulo<M>{
177+
/// Computes self^n in O(log n) time
178+
pubfnpow(mutself,mutn:u64) ->Self{
182179
letmut result =Self::from_small(1);
183-
whileexp >0{
184-
ifexp %2 ==1{
180+
whilen >0{
181+
ifn %2 ==1{
185182
result = result*self;
186183
}
187184
self =self*self;
188-
exp /=2;
185+
n /=2;
189186
}
190187
result
191188
}
192189
/// Computes inverses of 1 to n in O(n) time
193190
pubfnvec_of_recips(n:i64) ->Vec<Self>{
194191
letmut recips =vec![Self::from(0),Self::from(1)];
195192
for iin2..=n{
196-
let(md, dv) =(Self::MOD % i,Self::MOD / i);
193+
let(md, dv) =(M % i,M / i);
197194
recips.push(recips[mdasusize]*Self::from_small(-dv));
198195
}
199196
recips
200197
}
201-
/// Computes self^-1 in O(log(Self::MOD)) time
198+
/// Computes self^-1 in O(log M) time
202199
pubfnrecip(self) ->Self{
203-
self.pow(Self::MODasu64 -2)
200+
self.pow(Masu64 -2)
204201
}
205-
/// Avoids the % operation but requires -Self::MOD <= x <Self::MOD
202+
/// Avoids the % operation but requires -M <= x <M
206203
fnfrom_small(s:i64) ->Self{
207-
let val =if s <0{ s +Self::MOD}else{ s};
204+
let val =if s <0{ s +M}else{ s};
208205
Self{ val}
209206
}
210207
}
211-
implFrom<i64>forField{
208+
impl<constM:i64>From<i64>forModulo<M>{
212209
fnfrom(val:i64) ->Self{
213-
// Self { val: val.rem_euclid(Self::MOD) }
214-
Self::from_small(val %Self::MOD)
210+
// Self { val: val.rem_euclid(M) }
211+
Self::from_small(val %M)
215212
}
216213
}
217-
implNegforField{
214+
impl<constM:i64>NegforModulo<M>{
218215
typeOutput =Self;
219216
fnneg(self) ->Self{
220217
Self::from_small(-self.val)
221218
}
222219
}
223-
implAddforField{
220+
impl<constM:i64>AddforModulo<M>{
224221
typeOutput =Self;
225222
fnadd(self,other:Self) ->Self{
226-
Self::from_small(self.val + other.val -Self::MOD)
223+
Self::from_small(self.val + other.val -M)
227224
}
228225
}
229-
implSubforField{
226+
impl<constM:i64>SubforModulo<M>{
230227
typeOutput =Self;
231228
fnsub(self,other:Self) ->Self{
232229
Self::from_small(self.val - other.val)
233230
}
234231
}
235-
implMulforField{
232+
impl<constM:i64>MulforModulo<M>{
236233
typeOutput =Self;
237234
fnmul(self,other:Self) ->Self{
238235
Self::from(self.val* other.val)
239236
}
240237
}
241238
#[allow(clippy::suspicious_arithmetic_impl)]
242-
implDivforField{
239+
impl<constM:i64>DivforModulo<M>{
243240
typeOutput =Self;
244241
fndiv(self,other:Self) ->Self{
245242
self* other.recip()
246243
}
247244
}
248245

246+
/// Prime modulus that's commonly used in programming competitions
247+
pubconstCOMMON_PRIME:i64 =998_244_353;// 2^23 * 7 * 17 + 1;
248+
pubtypeCommonField =Modulo<COMMON_PRIME>;
249+
249250
#[derive(Clone,PartialEq,Debug)]
250251
pubstructMatrix{
251252
cols:usize,
@@ -268,15 +269,15 @@ impl Matrix {
268269
let inner = vec.to_vec().into_boxed_slice();
269270
Self{ cols, inner}
270271
}
271-
pubfnpow(&self,mutexp:u64) ->Self{
272+
pubfnpow(&self,mutn:u64) ->Self{
272273
letmut base =self.clone();
273274
letmut result =Self::one(self.cols);
274-
whileexp >0{
275-
ifexp %2 ==1{
275+
whilen >0{
276+
ifn %2 ==1{
276277
result =&result*&base;
277278
}
278279
base =&base*&base;
279-
exp /=2;
280+
n /=2;
280281
}
281282
result
282283
}
@@ -417,10 +418,10 @@ mod test {
417418

418419
#[test]
419420
fntest_field(){
420-
let base =Field::from(1234);
421+
let base =CommonField::from(1234);
421422
let zero = base - base;
422423
let one = base.recip()* base;
423-
let two =Field::from(2 -5*Field::MOD);
424+
let two =CommonField::from(2 -5*COMMON_PRIME);
424425

425426
assert_eq!(zero.val,0);
426427
assert_eq!(one.val,1);
@@ -430,11 +431,11 @@ mod test {
430431

431432
#[test]
432433
fntest_vec_of_recips(){
433-
let recips =Field::vec_of_recips(20);
434+
let recips =CommonField::vec_of_recips(20);
434435

435436
assert_eq!(recips.len(),21);
436437
for iin1..recips.len(){
437-
assert_eq!(recips[i],Field::from(iasi64).recip());
438+
assert_eq!(recips[i],CommonField::from(iasi64).recip());
438439
}
439440
}
440441

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp