-
Notifications
You must be signed in to change notification settings - Fork 0
/
bernoulli.rs
34 lines (29 loc) · 828 Bytes
/
bernoulli.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
use super::*;
use enumeration::Enumeration;
use acl_modint::*;
use fft::*;
pub fn bernoulli<T: ModIntBase, C: Clone + Convolution<T>>(n: usize) -> Vec<T> {
let mut x = FPS::<T, C>::with_deg(n + 1);
let f = Enumeration::<T>::new();
//TODO: replace with thread-local Enumeration struct
for i in 0 ..= n {
x[i] = f.fact_inv(i + 1);
}
let mut y = x.inv();
for i in 0 ..= n {
y[i] *= f.fact(i);
}
let y: Vec<_> = y.into();
y[..= n].to_vec()
}
#[cfg(test)]
pub mod test {
use acl_modint::*;
use super::*;
#[test]
fn test_bernoulli() {
let b = bernoulli::<ModInt998244353, ConvolutionStatic<Mod998244353>>(10);
let b = b.into_iter().map(|x| x.val()).collect::<Vec<_>>();
assert_eq!(b, vec![1, 499122176, 166374059, 0, 565671800, 0, 308980395, 0, 565671800, 0, 892369952]);
}
}