fixes

adamant-pwn · adamant-pwn · commit f273d92e8ec4 · 2025-04-27T22:34:00.000+02:00
diff --git a/cp-algo/math/cvector.hpp b/cp-algo/math/cvector.hpp
@@ -15,7 +15,9 @@ namespace cp_algo::math::fft {
     using vftype [[gnu::vector_size(bytes)]] = ftype;
     using vpoint = complex<vftype>;
     static constexpr vftype vz = {};
-    static constexpr vpoint vi = {vz, vz + 1};
+    vpoint vi(vpoint const& r) {
+        return {-imag(r), real(r)};
+    }
     vftype abs(vftype a) {
         return a < 0 ? -a : a;
     }
@@ -132,8 +134,8 @@ namespace cp_algo::math::fft {
                             auto D = at(j + 3 * i);
                             at(j) = (A + B + C + D);
                             at(j + 2 * i) = (A + B - C - D) * v2;
-                            at(j +     i) = (A - B - vi * (C - D)) * v1;
-                            at(j + 3 * i) = (A - B + vi * (C - D)) * v3;
+                            at(j +     i) = (A - B - vi(C - D)) * v1;
+                            at(j + 3 * i) = (A - B + vi(C - D)) * v3;
                         }
                     });
                     i *= 2;
@@ -171,8 +173,8 @@ namespace cp_algo::math::fft {
                             auto D = at(j + 3 * i) * v3;
                             at(j)         = (A + C) + (B + D);
                             at(j + i)     = (A + C) - (B + D);
-                            at(j + 2 * i) = (A - C) + vi * (B - D);
-                            at(j + 3 * i) = (A - C) - vi * (B - D);
+                            at(j + 2 * i) = (A - C) + vi(B - D);
+                            at(j + 3 * i) = (A - C) - vi(B - D);
                         }
                     });
                 } else { // radix-2 fallback
diff --git a/cp-algo/math/fft.hpp b/cp-algo/math/fft.hpp
@@ -82,7 +82,7 @@ namespace cp_algo::math::fft {
         }
 
         void recover_mod(auto &&C, auto &res, size_t k) {
-            assert(size(res) % flen == 0);
+            res.assign((k / flen + 1) * flen, base(0));
             size_t n = A.size();
             auto splitsplit = base(split * split).getr();
             base b2x32 = bpow(base(2), 32);
@@ -106,7 +106,7 @@ namespace cp_algo::math::fft {
                     Au = montgomery_mul(Au, mul, mod, imod);
                     Au = Au >= base::mod() ? Au - base::mod() : Au;
                     for(size_t j = 0; j < flen; j++) {
-                        res[i + j].setr(Au[j]);
+                        res[i + j].setr(typename base::UInt(Au[j]));
                     }
                 };
                 set_i(i, Ax, Bx, Cx, cur);
@@ -115,6 +115,7 @@ namespace cp_algo::math::fft {
                 }
                 cur = montgomery_mul(cur, step4, mod, imod);
             }
+            res.resize(k);
             checkpoint("recover mod");
         }
 
@@ -138,13 +139,13 @@ namespace cp_algo::math::fft {
             mul(cvector(B.A), B.B, res, k);
         }
         std::vector<base, big_alloc<base>> operator *= (dft &B) {
-            std::vector<base, big_alloc<base>> res(2 * A.size());
-            mul_inplace(B, res, size(res));
+            std::vector<base, big_alloc<base>> res;
+            mul_inplace(B, res, 2 * A.size());
             return res;
         }
         std::vector<base, big_alloc<base>> operator *= (dft const& B) {
-            std::vector<base, big_alloc<base>> res(2 * A.size());
-            mul(B, res, size(res));
+            std::vector<base, big_alloc<base>> res;
+            mul(B, res, 2 * A.size());
             return res;
         }
         auto operator * (dft const& B) const {
@@ -191,13 +192,11 @@ namespace cp_algo::math::fft {
             std::min(k, size(a)) + std::min(k, size(b)) - 1
         ) / 2);
         auto A = dft<base>(a | std::views::take(k), n);
-        a.assign((k / flen + 1) * flen, 0);
         if(&a == &b) {
             A.mul(A, a, k);
         } else {
             A.mul_inplace(dft<base>(b | std::views::take(k), n), a, k);
         }
-        a.resize(k);
     }
     void mul(auto &a, auto const& b) {
         size_t N = size(a) + size(b) - 1;
diff --git a/cp-algo/math/poly/impl/div.hpp b/cp-algo/math/poly/impl/div.hpp
@@ -87,7 +87,7 @@ namespace cp_algo::math::poly::impl {
         auto q1f = fft::dft<base>(q1.a, N);
         auto qqf = fft::dft<base>(qq.a, N);
         size_t M = q0.deg() + (n + 1) / 2;
-        typename poly::Vector A(M), B(M);
+        typename poly::Vector A, B;
         q0f.mul(qqf, A, M);
         q1f.mul_inplace(qqf, B, M);
         q.a.resize(n + 1);
@@ -120,7 +120,7 @@ namespace cp_algo::math::poly::impl {
         inv_inplace(qq, (n + 1) / 2);
         auto qqf = fft::dft<base>(qq.a, N);
         
-        typename poly::Vector A((n + 1) / 2), B((n + 1) / 2);
+        typename poly::Vector A, B;
         q0f.mul(qqf, A, (n + 1) / 2);
         q1f.mul_inplace(qqf, B, (n + 1) / 2);
         p.a.resize(n + 1);

Original file line number	Diff line number	Diff line change
`@@ -82,7 +82,7 @@ namespace cp_algo::math::fft {`
`82`	`82`	`}`
`83`	`83`
`84`	`84`	`void recover_mod(auto &&C, auto &res, size_t k) {`
`85`		`- assert(size(res) % flen == 0);`
	`85`	`+ res.assign((k / flen + 1) * flen, base(0));`
`86`	`86`	`size_t n = A.size();`
`87`	`87`	`auto splitsplit = base(split * split).getr();`
`88`	`88`	`base b2x32 = bpow(base(2), 32);`
`@@ -106,7 +106,7 @@ namespace cp_algo::math::fft {`
`106`	`106`	`Au = montgomery_mul(Au, mul, mod, imod);`
`107`	`107`	`Au = Au >= base::mod() ? Au - base::mod() : Au;`
`108`	`108`	`for(size_t j = 0; j < flen; j++) {`
`109`		`- res[i + j].setr(Au[j]);`
	`109`	`+ res[i + j].setr(typename base::UInt(Au[j]));`
`110`	`110`	`}`
`111`	`111`	`};`
`112`	`112`	`set_i(i, Ax, Bx, Cx, cur);`
`@@ -115,6 +115,7 @@ namespace cp_algo::math::fft {`
`115`	`115`	`}`
`116`	`116`	`cur = montgomery_mul(cur, step4, mod, imod);`
`117`	`117`	`}`
	`118`	`+ res.resize(k);`
`118`	`119`	`checkpoint("recover mod");`
`119`	`120`	`}`
`120`	`121`
`@@ -138,13 +139,13 @@ namespace cp_algo::math::fft {`
`138`	`139`	`mul(cvector(B.A), B.B, res, k);`
`139`	`140`	`}`
`140`	`141`	`std::vector<base, big_alloc<base>> operator *= (dft &B) {`
`141`		`- std::vector<base, big_alloc<base>> res(2 * A.size());`
`142`		`- mul_inplace(B, res, size(res));`
	`142`	`+ std::vector<base, big_alloc<base>> res;`
	`143`	`+ mul_inplace(B, res, 2 * A.size());`
`143`	`144`	`return res;`
`144`	`145`	`}`
`145`	`146`	`std::vector<base, big_alloc<base>> operator *= (dft const& B) {`
`146`		`- std::vector<base, big_alloc<base>> res(2 * A.size());`
`147`		`- mul(B, res, size(res));`
	`147`	`+ std::vector<base, big_alloc<base>> res;`
	`148`	`+ mul(B, res, 2 * A.size());`
`148`	`149`	`return res;`
`149`	`150`	`}`
`150`	`151`	`auto operator * (dft const& B) const {`
`@@ -191,13 +192,11 @@ namespace cp_algo::math::fft {`
`191`	`192`	`std::min(k, size(a)) + std::min(k, size(b)) - 1`
`192`	`193`	`) / 2);`
`193`	`194`	`auto A = dft<base>(a \| std::views::take(k), n);`
`194`		`- a.assign((k / flen + 1) * flen, 0);`
`195`	`195`	`if(&a == &b) {`
`196`	`196`	`A.mul(A, a, k);`
`197`	`197`	`} else {`
`198`	`198`	`A.mul_inplace(dft<base>(b \| std::views::take(k), n), a, k);`
`199`	`199`	`}`
`200`		`- a.resize(k);`
`201`	`200`	`}`
`202`	`201`	`void mul(auto &a, auto const& b) {`
`203`	`202`	`size_t N = size(a) + size(b) - 1;`