RE with convolution in ACL v1.4
Yianlaen opened this issue · 3 comments
This submission got accepted while this got runtime error.
Their only difference is the accepted one uses a naive convolution method and the RE one uses atcoder::convolution.
I think this might be a problem from ACL v1.4, because in my local v1.3 environment atcoder::convolution works well, while switching to v1.4 results in RE.
(Also v1.4 has many warnings while compiling and v1.3 doesn't)
atcoder::convolution cannot handle arbitrary mod.
about warnings. I checked that v1.4 can compile without warnings in a few environments, but of course, warning maybe issued in other environments... if you give me a bit more information (your environment, warning messages), I can investigate
Not sure if this is the same issue, but I believe running atcoder::convolution for mod = 10^9 + 7 will always crash. It'd be nice if somehow the library would state that it can't compute the convolution and the reason. Otherwise, I thought it is working as I tested my solution on samples which all had for n<=20 and it uses a naive implementation that doesn't have the aforementioned problem.
As for the reason, I believe its here - https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp#L107 . The info.rate3 table is of size 0, because rank2 = bsf_constexpr( mod - 1 ) = 2, and the array is of size 2 - 3 + 1 = 0.
`#include
using namespace std;
#define rep(x, b, e) for(int x=(b); x<(e); ++x)
#include <atcoder/convolution>
#include <atcoder/modint>
using namespace atcoder;
// using mint = modint998244353; - ok, because bsf(mod - 1) = 23
using mint = modint1000000007; // breaks because bsf(mod - 1) = 1, rank2 = 1, and we try to reach outside of the array in convolution::butterfly() on line 107
int main() {
int n = 61; // needed > 60 to skip the naive method of computing the convolution
vector a(n);
vector b(n);
rep(i, 0, n) {
a[i] = i;
b[i] = n - i;
}
vector c = convolution(a, b);
rep(i, 0, c.size()) {
printf("%d ", c[i].val());
}
}`
Yes, there is a constraint in atcoder::convolution (https://atcoder.github.io/ac-library/production/document_en/convolution.html).
- There is an integer c with 2^c | (m - 1) and |a| + |b| - 1 <= 2^c
This constraint means, we have to satisfy |a| + |b| - 1 <= 2 when we use 10^9 + 7 as mod because 10^9 + 6 isn't a multiple of 4.
The reason we need such a curious constraint is due to the algorithm we use to convolution. If you interested, there are many tutorials (e.g. https://codeforces.com/blog/entry/43499) about convolution, please refer this.