fn reduced_transform<T, C>(fps: &FormalPowerSeries<T, C>, length: usize) -> C::FExamples found in repository?
crates/competitive/src/math/formal_power_series/berlekamp_massey.rs (line 79)
77 fn transform(&self, length: usize) -> FrequencyMatrix<C> {
78 FrequencyMatrix {
79 a00: reduced_transform(&self.a00, length),
80 a01: reduced_transform(&self.a01, length),
81 a10: reduced_transform(&self.a10, length),
82 a11: reduced_transform(&self.a11, length),
83 }
84 }
85
86 fn extend_transform(&self, frequency: FrequencyMatrix<C>, length: usize) -> FrequencyMatrix<C> {
87 fn extend<T, C>(fps: &FormalPowerSeries<T, C>, frequency: C::F, length: usize) -> C::F
88 where
89 T: FormalPowerSeriesCoefficient,
90 C: NttReuse<T = Vec<T>>,
91 C::F: Clone,
92 {
93 if fps.length() <= length / 2 {
94 C::ntt_doubling(frequency, false)
95 } else {
96 reduced_transform(fps, length)
97 }
98 }
99
100 FrequencyMatrix {
101 a00: extend(&self.a00, frequency.a00, length),
102 a01: extend(&self.a01, frequency.a01, length),
103 a10: extend(&self.a10, frequency.a10, length),
104 a11: extend(&self.a11, frequency.a11, length),
105 }
106 }
107}
108
109impl<T, C> FrequencyMatrix<C>
110where
111 T: FormalPowerSeriesCoefficient,
112 C: NttReuse<T = Vec<T>>,
113 C::F: Clone,
114{
115 fn product_sum(left_a: &C::F, right_a: &C::F, left_b: &C::F, right_b: &C::F) -> C::F {
116 let mut result = left_a.clone();
117 C::multiply_prefix(&mut result, right_a);
118 C::multiply_add(&mut result, left_b, right_b);
119 result
120 }
121
122 fn multiply(&self, right: &Self) -> Self {
123 Self {
124 a00: Self::product_sum(&self.a00, &right.a00, &self.a01, &right.a10),
125 a01: Self::product_sum(&self.a00, &right.a01, &self.a01, &right.a11),
126 a10: Self::product_sum(&self.a10, &right.a00, &self.a11, &right.a10),
127 a11: Self::product_sum(&self.a10, &right.a01, &self.a11, &right.a11),
128 }
129 }
130
131 fn apply(&self, p: &C::F, q: &C::F, length: usize) -> (Vec<T>, Vec<T>) {
132 (
133 C::inverse_transform_ntt(Self::product_sum(p, &self.a00, q, &self.a01), length),
134 C::inverse_transform_ntt(Self::product_sum(p, &self.a10, q, &self.a11), length),
135 )
136 }
137
138 fn left_multiply_step(self, quotient: &FormalPowerSeries<T, C>, length: usize) -> Self {
139 let negative_quotient = reduced_transform(&(-quotient), length);
140 let mut a10 = self.a00;
141 C::multiply_add(&mut a10, &negative_quotient, &self.a10);
142 let mut a11 = self.a01;
143 C::multiply_add(&mut a11, &negative_quotient, &self.a11);
144 let result = Self {
145 a00: self.a10,
146 a01: self.a11,
147 a10,
148 a11,
149 };
150 if C::MULTIPLE {
151 result.inverse_transform(length).transform(length)
152 } else {
153 result
154 }
155 }