为什么不能对 x^n 取模?

@longlongzhu123 2019-06-01 22:52 回复

在做这道题的时候突然想到一个问题:为什么下面这段代码会跑出错误的答案?

LL tmp1[kMaxN << 2], tmp2[kMaxN << 2];
void GetLn(LL* f, LL* g, int n) {
  Derivative(f, tmp1, n >> 1); // 先求出 mod x ^ n/2 意义下的 tmp1
  GetInv(f, tmp2, n >> 1); // 再求出 mod x ^ n/2 意义下的 tmp2
  Multiply(tmp1, tmp2, n); // 难道两者相乘不会得到 mod x^n 意义下的乘积吗?
  Integral(tmp1, g, n);
}

我们不是要在 $\mod x ^ n$ 下求出 $\ln$ 吗?那么为什么不能分别求出 $\mod x ^ {n / 2}$ 下的导数和逆,然后相乘得到 $\mod x ^ n$ 的乘积呢?

望大佬解答一下,谢谢 QwQ


另:这才是正确的代码:

LL tmp1[kMaxN << 2], tmp2[kMaxN << 2];
void GetLn(LL* f, LL* g, int n) {
  Derivative(f, tmp1, n);
  GetInv(f, tmp2, n);
  Multiply(tmp1, tmp2, n << 1);
  Integral(tmp1, g, n << 1);
}
// 注意到所有的 n 都乘了 2
@longlongzhu123 2019-06-01 23:30 回复 举报

@SSerxhs 啊不好意思刚刚走开了一下

您指的超出是指对两个 $n$ 次的多项式进行 Multiply(a, b, n) 这样的操作吗?

代码里面 GetInv(f, tmp2, n) 只会取 tmp2 的前 $n$ 位哦

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。