QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #848994 | #9945. Circular Convolution | Capps | Compile Error | / | / | C++11 | 12.6kb | 2025-01-09 11:10:08 | 2025-01-09 11:10:08 |
Judging History
This is the latest submission verdict.
- [2025-01-09 11:10:08]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2025-01-09 11:10:08]
- Submitted
answer
#include <bits/stdc++.h>
using i64 = long long;
template <class T>
constexpr T power(T a, long long b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b & 1) {
res *= a;
}
}
return res;
}
template <class T, T P>
class ModuloInteger {
T x;
static T Mod;
using i64 = long long;
static constexpr int multip(int a, int b, const int Mod) {
return 1LL * a * b % Mod;
}
static constexpr i64 multip(i64 a, i64 b, const i64 p) {
// i64 res = a * b - i64(1.L * a * b / p) * p;
// res %= p;
// if (res < 0) {
// res += p;
// }
// return res;
return (__int128)a * b % p;
}
constexpr T norm(T x) const {
return (x < 0 ? x + getMod() : (x >= getMod() ? x - getMod() : x));
}
public:
typedef T ValueType;
constexpr ModuloInteger() : x{} {}
constexpr ModuloInteger(i64 x) : x{norm(x % getMod())} {}
static constexpr T getMod() {
return (P > 0 ? P : Mod);
}
static constexpr void setMod(T Mod_) {
Mod = Mod_;
}
constexpr T val() const {
return x;
}
explicit constexpr operator T() const {
return x;
}
constexpr ModuloInteger operator-() const {
return ModuloInteger(getMod() - x);
}
constexpr ModuloInteger power(i64 m) const {
if (m < 0) {
return ::power(inv(), -m);
}
return ::power((*this), m);
}
constexpr ModuloInteger inv() const {
assert(x != 0);
return this->power(getMod() - 2);
}
constexpr ModuloInteger &operator*=(ModuloInteger rhs) & {
x = multip(x, rhs.x, getMod());
return *this;
}
constexpr ModuloInteger &operator+=(ModuloInteger rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr ModuloInteger &operator-=(ModuloInteger rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr ModuloInteger &operator/=(ModuloInteger rhs) & {
return *this *= rhs.inv();
}
friend constexpr ModuloInteger operator+(ModuloInteger lhs, ModuloInteger rhs) {
return lhs += rhs;
}
friend constexpr ModuloInteger operator-(ModuloInteger lhs, ModuloInteger rhs) {
return lhs -= rhs;
}
friend constexpr ModuloInteger operator*(ModuloInteger lhs, ModuloInteger rhs) {
return lhs *= rhs;
}
friend constexpr ModuloInteger operator/(ModuloInteger lhs, ModuloInteger rhs) {
return lhs /= rhs;
}
friend constexpr std::istream &operator>>(std::istream &is, ModuloInteger &a) {
i64 v;
is >> v;
a = ModuloInteger(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const ModuloInteger &a) {
return os << a.val();
}
friend constexpr bool operator==(ModuloInteger lhs, ModuloInteger rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(ModuloInteger lhs, ModuloInteger rhs) {
return lhs.val() != rhs.val();
}
};
template <>
int ModuloInteger<int, 0>::Mod = 998244353;
template <>
long long ModuloInteger<long long, 0>::Mod = 4179340454199820289;
constexpr i64 P = 4179340454199820289;
using Z = ModuloInteger<i64, P>;
template <class T>
struct Polynomial : public std::vector<T> {
static std::vector<T> w;
static constexpr auto P = T::getMod();
static void initW(int r) {
if (w.size() >= r) {
return;
}
w.assign(r, 0);
w[r >> 1] = 1;
T s = ::power(T(3), (P - 1) / r);
for (int i = r / 2 + 1; i < r; i++) {
w[i] = w[i - 1] * s;
}
for (int i = r / 2 - 1; i > 0; i--) {
w[i] = w[i * 2];
}
}
constexpr friend void dft(Polynomial &a) {
const int n = a.size();
assert((n & (n - 1)) == 0);
initW(n);
for (int k = n >> 1; k; k >>= 1) {
for (int i = 0; i < n; i += k << 1) {
for (int j = 0; j < k; j++) {
T v = a[i + j + k];
a[i + j + k] = (a[i + j] - v) * w[k + j];
a[i + j] = a[i + j] + v;
}
}
}
}
constexpr friend void idft(Polynomial &a) {
const int n = a.size();
assert((n & (n - 1)) == 0);
initW(n);
for (int k = 1; k < n; k <<= 1) {
for (int i = 0; i < n; i += k << 1) {
for (int j = 0; j < k; j++) {
T x = a[i + j];
T y = a[i + j + k] * w[j + k];
a[i + j + k] = x - y;
a[i + j] = x + y;
}
}
}
a *= P - (P - 1) / n;
std::reverse(a.begin() + 1, a.end());
}
public:
using std::vector<T>::vector;
constexpr Polynomial truncate(int k) const {
Polynomial p = *this;
p.resize(k);
return p;
}
constexpr friend Polynomial operator+(const Polynomial &a, const Polynomial &b) {
Polynomial p(std::max(a.size(), b.size()));
for (int i = 0; i < a.size(); i++) {
p[i] += a[i];
}
for (int i = 0; i < b.size(); i++) {
p[i] += b[i];
}
return p;
}
constexpr friend Polynomial operator-(const Polynomial &a, const Polynomial &b) {
Polynomial p(std::max(a.size(), b.size()));
for (int i = 0; i < a.size(); i++) {
p[i] += a[i];
}
for (int i = 0; i < b.size(); i++) {
p[i] -= b[i];
}
return p;
}
constexpr friend Polynomial operator-(const Polynomial &a) {
int n = a.size();
Polynomial p(n);
for (int i = 0; i < n; i++) {
p[i] = -a[i];
}
return p;
}
constexpr friend Polynomial operator*(T a, Polynomial b) {
for (int i = 0; i < b.size(); i++) {
b[i] *= a;
}
return b;
}
constexpr friend Polynomial operator*(Polynomial a, T b) {
for (int i = 0; i < a.size(); i++) {
a[i] *= b;
}
return a;
}
constexpr friend Polynomial operator/(Polynomial a, T b) {
b = b.inv();
for (int i = 0; i < a.size(); i++) {
a[i] *= b;
}
return a;
}
constexpr Polynomial mulxk(int k) const {
assert(k >= 0);
Polynomial b = (*this);
b.insert(b.begin(), k, 0);
return b;
}
constexpr Polynomial modxk(int k) const {
assert(k > 0);
return Polynomial(this->begin(), this->begin() + k);
}
constexpr Polynomial divxk(int k) const {
assert(k >= 0);
if (this->size() <= k) {
return Polynomial{};
}
return Polynomial(this->begin() + k, this->end());
}
constexpr T whenXis(T x) const {
T ans = T{};
for (int i = (int)this->size() - 1; i >= 0; i--) {
ans = ans * x + this->at(i);
}
return ans;
}
constexpr Polynomial &operator+=(Polynomial b) {
return (*this) = (*this) + b;
}
constexpr Polynomial &operator-=(Polynomial b) {
return (*this) = (*this) - b;
}
constexpr Polynomial &operator*=(Polynomial b) {
return (*this) = (*this) * b;
}
constexpr Polynomial &operator*=(T b) {
return (*this) = (*this) * b;
}
constexpr Polynomial &operator/=(T b) {
return (*this) = (*this) / b;
}
constexpr friend Polynomial operator*(const Polynomial &a, const Polynomial &b) {
if (a.size() == 0 or b.size() == 0) {
return Polynomial();
}
int n = a.size() + b.size() - 1;
int s = 1 << std::__lg(2 * n - 1);
if (((P - 1) & (s - 1)) != 0 or std::min(a.size(), b.size()) < 128) {
Polynomial p(n);
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < b.size(); j++) {
p[i + j] += a[i] * b[j];
}
}
return p;
}
Polynomial f = a.truncate(s);
Polynomial g = b.truncate(s);
dft(f), dft(g);
for (int i = 0; i < s; i++) {
f[i] *= g[i];
}
idft(f);
return f.truncate(n);
}
constexpr Polynomial deriv() const {
int n = this->size();
if (n <= 1) {
return Polynomial();
}
Polynomial p(n - 1);
for (int i = 1; i < n; i++) {
p[i - 1] = i * this->at(i);
}
return p;
}
constexpr Polynomial integr() const {
int n = this->size();
Polynomial p(n + 1);
std::vector<T> _inv(n + 1);
_inv[1] = 1;
for (int i = 2; i <= n; i++) {
_inv[i] = _inv[P % i] * (P - P / i);
}
for (int i = 0; i < n; ++i) {
p[i + 1] = this->at(i) * _inv[i + 1];
}
return p;
}
// assert(this->at(0) != 0);
constexpr Polynomial inv(int m = -1) const {
const int n = this->size();
m = m < 0 ? n : m;
Polynomial p = Polynomial{this->at(0).inv()};
p.reserve(4 * m);
for (int k = 2; k / 2 < m; k <<= 1) {
Polynomial q = Polynomial(this->begin(), this->begin() + std::min(k, n)).truncate(2 * k);
p.resize(2 * k);
dft(q), dft(p);
for (int i = 0; i < 2 * k; i++) {
p[i] = p[i] * (2 - p[i] * q[i]);
}
idft(p);
p.resize(k);
}
return p.truncate(m);
}
constexpr Polynomial ln(int m = -1) const {
m = m < 0 ? this->size() : m;
return (deriv() * inv(m)).integr().truncate(m);
}
constexpr Polynomial exp(int m = -1) const {
m = m < 0 ? this->size() : m;
Polynomial p{1};
int k = 1;
while (k < m) {
k <<= 1;
p = (p * (Polynomial{1} - p.ln(k) + truncate(k))).truncate(k);
}
return p.truncate(m);
}
constexpr Polynomial power(i64 k, int m, i64 k2 = -1) const {
if (0 < k and k <= (1 << 10)) {
Polynomial p = (*this);
Polynomial ans{1};
for (; k; k >>= 1) {
if (k & 1) {
ans *= p;
if (ans.size() > m) {
ans.truncate(m);
}
}
p *= p;
if (p.size() > m) {
p.truncate(m);
}
}
return ans.truncate(m);
}
k2 = k2 < 0 ? k : k2;
int i = 0;
while (i < this->size() and this->at(i) == T{}) {
i++;
}
if (i == this->size() or k * i >= m) {
return Polynomial(m, T{});
}
T v = this->at(i);
Polynomial f = divxk(i) / v;
return (f.ln(m - i * k) * k).exp(m - i * k).mulxk(i * k) * ::power(v, k2);
}
constexpr Polynomial sqrt(int m = -1) const {
m = m < 0 ? this->size() : m;
Polynomial p{1};
int k = 1;
constexpr T INV2 = T(1) / 2;
while (k < m) {
k <<= 1;
p = (p + (truncate(k) * p.inv(k)).truncate(k)) * INV2;
}
return p.truncate(m);
}
friend constexpr std::istream &operator>>(std::istream &is, Polynomial &a) {
int n = a.size();
for (int i = 0; i < n; i++) {
is >> a[i];
}
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const Polynomial &a) {
int n = a.size();
if (n >= 1) {
os << a[0];
}
for (int i = 1; i < n; i++) {
os << ' ' << a[i];
}
return os;
}
};
template <class T>
std::vector<T> Polynomial<T>::w;
using Poly = Polynomial<Z>;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
Poly p(n), q(n);
std::cin >> p >> q;
p *= q;
for (int i = n; i < p.size(); i++) {
p[i - n] += p[i];
}
p.resize(n);
for (int i = 0; i < n; i++) {
i64 x = i64(p[i]);
if (x > P / 2) {
x -= P;
}
std::cout << x << " \n"[i + 1 == n];
}
return 0;
}
詳細信息
answer.code: In instantiation of ‘Polynomial<T>& Polynomial<T>::operator*=(Polynomial<T>) const [with T = ModuloInteger<long long int, 4179340454199820289>]’:
answer.code:495:10: required from here
answer.code:298:24: error: passing ‘const Polynomial<ModuloInteger<long long int, 4179340454199820289> >’ as ‘this’ argument discards qualifiers [-fpermissive]
298 | return (*this) = (*this) * b;
| ~~~~~~~~^~~~~~~~~~~~~
answer.code:142:8: note: in call to ‘Polynomial<ModuloInteger<long long int, 4179340454199820289> >& Polynomial<ModuloInteger<long long int, 4179340454199820289> >::operator=(Polynomial<ModuloInteger<long long int, 4179340454199820289> >&&)’
142 | struct Polynomial : public std::vector<T> {
| ^~~~~~~~~~
answer.code: In instantiation of ‘constexpr ModuloInteger<T, P>& ModuloInteger<T, P>::operator+=(ModuloInteger<T, P>) const & [with T = long long int; T P = 4179340454199820289]’:
answer.code:497:24: required from here
answer.code:84:11: error: assignment of member ‘ModuloInteger<long long int, 4179340454199820289>::x’ in read-only object
84 | x = norm(x + rhs.x);
| ~~^~~~~~~~~~~~~~~~~
answer.code:85:17: error: binding reference of type ‘ModuloInteger<long long int, 4179340454199820289>&’ to ‘const ModuloInteger<long long int, 4179340454199820289>’ discards qualifiers
85 | return *this;
| ^~~~
answer.code: In instantiation of ‘constexpr ModuloInteger<T, P>& ModuloInteger<T, P>::operator*=(ModuloInteger<T, P>) const & [with T = long long int; T P = 4179340454199820289]’:
answer.code:332:18: required from ‘constexpr Polynomial<ModuloInteger<long long int, 4179340454199820289> > operator*(const Polynomial<ModuloInteger<long long int, 4179340454199820289> >&, const Polynomial<ModuloInteger<long long int, 4179340454199820289> >&)’
answer.code:298:34: required from ‘Polynomial<T>& Polynomial<T>::operator*=(Polynomial<T>) const [with T = ModuloInteger<long long int, 4179340454199820289>]’
answer.code:495:10: required from here
answer.code:80:11: error: assignment of member ‘ModuloInteger<long long int, 4179340454199820289>::x’ in read-only object
80 | x = multip(x, rhs.x, getMod());
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:81:17: error: binding reference of type ‘ModuloInteger<long long int, 4179340454199820289>&’ to ‘const ModuloInteger<long long int, 4179340454199820289>’ discards qualifiers
81 | return *this;
| ^~~~
answer.code: In instantiation of ‘Polynomial<T>& Polynomial<T>::operator*=(T) const [with T = ModuloInteger<long long int, 4179340454199820289>]’:
answer.code:195:11: required from ‘constexpr void idft(Polynomial<ModuloInteger<long long int, 4179340454199820289> >&)’
answer.code:335:13: required from ‘constexpr Polynomial<ModuloInteger<long long int, 4179340454199820289> > operator*(const Polynomial<ModuloInteger<long long int, 4179340454199820289> >&, const Polynomial<ModuloInteger<long long int, 4179340454199820289> >&)’
answer.code:298:34: required from ‘Polynomial<T>& Polynomial<T>::operator*=(Polynomial<T>) const [with T = ModuloInteger<long long int, 4179340454199820289>]’
answer.code:495:10: required from here
answer.code:301:24: error: passing ‘const Polynomial<ModuloInteger<long long int, 4179340454199820289> >’ as ‘this’ argument discards qualifiers [-fpermissive]
301 | return (*this) = (*this) * b;
| ~~~~~~~~^~~~~~~~~~~~~
answer.code:142:8: note: in call to ‘Polynomial<ModuloInteger<long long int, 4179340454199820289> >& Polynomial<ModuloInteger<long long int, 4179340454199820289> >::operator=(Polynomial<ModuloInteger<long long int, 4179340454199820289> >&&)’
142 | struct Polynomial : public std::vector<T> {
| ^~~~~~~~~~
answer.code: In instantiation of ‘constexpr ModuloInteger<T, P>& ModuloInteger<T, P>::operator-=(ModuloInteger<T, P>) const & [with T = long long int; T P = 4179340454199820289]’:
answer.code:100:20: required from ‘constexpr ModuloInteger<long long int, 4179340454199820289> operator-(ModuloInteger<long long int, 4179340454199820289>, ModuloInteger<long long int, 4179340454199820289>)’
answer.code:172:46: required from ‘constexpr void dft(Polynomial<ModuloInteger<long long int, 4179340454199820289> >&)’
answer.code:329:12: required from ‘constexpr Polynomial<ModuloInteger<long long int, 4179340454199820289> > operator*(const Polynomial<ModuloInteger<long long int, 4179340454199820289> >&, const Polynomial<ModuloInteger<long long int, 4179340454199820289> >&)’
answer.code:298:34: required from ‘Polynomial<T>& Polynomial<T>::operator*=(Polynomial<T>) const [with T = ModuloInteger<long long int, 4179340454199820289>]’
answer.code:495:10: required from here
answer.code:88:11: error: assignment of member ‘ModuloInteger<long long int, 4179340454199820289>::x’ in read-only object
88 | x = norm(x - rhs.x);
| ...