fix

adamant-pwn · adamant-pwn · commit 2d03521039b4 · 2025-05-13T17:08:52.000+02:00
diff --git a/cp-algo/math/fft.hpp b/cp-algo/math/fft.hpp
@@ -282,12 +282,15 @@ namespace cp_algo::math::fft {
         }
         cp_algo::checkpoint("mod join");
     }
+    auto make_copy(auto &&x) {
+        return x;
+    }
     void cyclic_mul(auto &a, auto const& b, size_t k) {
         return cyclic_mul(a, make_copy(b), k);
     }
     void mul(auto &a, auto &&b) {
         size_t N = size(a) + size(b) - 1;
-    if(N > (1 << 19)) {
+        if(N > (1 << 19)) {
             size_t NN = std::bit_ceil(N);
             a.resize(NN);
             b.resize(NN);
@@ -298,7 +301,12 @@ namespace cp_algo::math::fft {
         }
     }
     void mul(auto &a, auto const& b) {
-        mul(a, make_copy(b));
+        size_t N = size(a) + size(b) - 1;
+        if(N > (1 << 19)) {
+            mul(a, make_copy(b));
+        } else {
+            mul_truncate(a, b, N);
+        }
     }
 }
 #endif // CP_ALGO_MATH_FFT_HPP

Original file line number	Diff line number	Diff line change
`@@ -282,12 +282,15 @@ namespace cp_algo::math::fft {`
`282`	`282`	`}`
`283`	`283`	`cp_algo::checkpoint("mod join");`
`284`	`284`	`}`
	`285`	`+ auto make_copy(auto &&x) {`
	`286`	`+ return x;`
	`287`	`+ }`
`285`	`288`	`void cyclic_mul(auto &a, auto const& b, size_t k) {`
`286`	`289`	`return cyclic_mul(a, make_copy(b), k);`
`287`	`290`	`}`
`288`	`291`	`void mul(auto &a, auto &&b) {`
`289`	`292`	`size_t N = size(a) + size(b) - 1;`
`290`		`- if(N > (1 << 19)) {`
	`293`	`+ if(N > (1 << 19)) {`
`291`	`294`	`size_t NN = std::bit_ceil(N);`
`292`	`295`	`a.resize(NN);`
`293`	`296`	`b.resize(NN);`
`@@ -298,7 +301,12 @@ namespace cp_algo::math::fft {`
`298`	`301`	`}`
`299`	`302`	`}`
`300`	`303`	`void mul(auto &a, auto const& b) {`
`301`		`- mul(a, make_copy(b));`
	`304`	`+ size_t N = size(a) + size(b) - 1;`
	`305`	`+ if(N > (1 << 19)) {`
	`306`	`+ mul(a, make_copy(b));`
	`307`	`+ } else {`
	`308`	`+ mul_truncate(a, b, N);`
	`309`	`+ }`
`302`	`310`	`}`
`303`	`311`	`}`
`304`	`312`	`#endif // CP_ALGO_MATH_FFT_HPP`