QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#6660 | #621. 多项式指数函数 | little_sun | Compile Error | / | / | C++14 | 5.5kb | 2021-03-08 16:12:42 | 2021-12-19 09:21:39 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2021-12-19 09:21:39]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2021-03-08 16:12:42]
- 提交
answer
#include <bits/stdc++.h>
#define R register
#define ll unsigned long long
#define meow(cat...) fprintf(stderr, cat)
#define sum(a, b, mod) (((a) + (b)) % mod)
const int G = 3;
const int inv2 = 499122177;
const int MaxN = 1e6 + 10;
const int mod = 998244353;
int n, k, lim, w[MaxN], rev[MaxN], _inv[MaxN];
void Mod(int &x) { x += x >> 31 & mod; }
void __init()
{
_inv[1] = 1;
for (int i = 2; i < MaxN; i++)
_inv[i] = (ll)(mod - mod / i) * _inv[mod % i] % mod;
}
int fast_pow(int a, int b)
{
int ret = 1;
while (b)
{
if (b & 1)
ret = (ll)ret * a % mod;
a = (ll)a * a % mod, b >>= 1;
}
return ret;
}
void init(int n)
{
int l = 32 - __builtin_clz(n - 1);
lim = (1 << l);
for (int i = 0, ri = 0; i < lim; i++)
{
rev[i] = ri;
for (int k = lim >> 1; (ri ^= k) < k;)
k >>= 1;
}
int wn = fast_pow(G, (mod - 1) >> l);
w[lim >> 1] = 1;
for (int i = (lim >> 1) + 1; i < lim; i++)
w[i] = (ll)w[i - 1] * wn % mod;
for (int i = (lim >> 1) - 1; i; --i)
w[i] = w[i << 1];
lim = l;
}
struct poly
{
std::vector<int> v;
inline poly() {}
inline poly(int n) : v(n) {}
inline poly(const poly &r) : v(r.v) {}
inline poly(const std::vector<int> &r) : v(r) {}
inline size_t size() { return v.size(); }
inline bool empty() { return v.empty(); }
inline void resize(int n) { v.resize(n); }
inline void clear() { v.clear(); }
inline void shl() { v.insert(v.begin(), 0); }
void shrink()
{
while (!v.empty() && !v.back())
v.pop_back();
}
inline int &operator[](int i) { return v[i]; }
inline static int len(int n) { return 1 << (32 - __builtin_clz(n - 1)); }
void deriv()
{
for (int i = 1; i < v.size(); i++)
v[i - 1] = (ll)i * v[i] % mod;
v.pop_back();
}
void intg()
{
shl();
for (int i = 1; i < v.size(); i++)
v[i] = (ll)v[i] * _inv[i] % mod;
}
void dft(int n)
{
static ll tmp[MaxN];
int ofs = lim - __builtin_ctz(n);
resize(n);
if (n <= 1) return;
for (int i = 0; i < n; i++)
tmp[rev[i] >> ofs] = v[i];
for (int i = 0; i < n; i += 2)
{
int x = tmp[i], y = tmp[i + 1];
tmp[i] = x + y, tmp[i + 1] = x + mod - y;
}
for (int i = 2; i < n; i <<= 1)
for (int j = 0; j < n; j += (i << 1))
for (int k = 0; k < i; ++k)
{
int y = (ll)tmp[i + j + k] * w[i + k] % mod;
tmp[i + j + k] = tmp[j + k] + mod - y, tmp[j + k] += y;
}
for (int i = 0; i < n; i++)
v[i] = tmp[i] % mod;
}
void idft(int n)
{
dft(n);
if (n <= 1) return;
std::reverse(v.begin() + 1, v.end());
int tmp = mod - (mod - 1) / n;
for (int i = 0; i < n; i++)
v[i] = (ll)v[i] * tmp % mod;
}
void mul(poly r)
{
int n = len(size() + r.size() - 1);
dft(n), r.dft(n);
for (int i = 0; i < n; i++)
v[i] = (ll)v[i] * r[i] % mod;
idft(n), shrink();
}
void inv()
{
std::vector<int> va(1);
int n = size(), m = len(n);
va[0] = fast_pow(v[0], mod - 2);
poly a; v.resize(m), v.swap(va);
for (int i = 1; i <= m; i <<= 1)
{
a.resize(i);
for (int j = 0; j < i; j++)
a[j] = va[j];
a.dft(i << 1), dft(i << 1);
for (int j = 0; j < (i << 1); j++)
v[j] = v[j] * (2 + mod - (ll)v[j] * a[j] % mod) % mod;
idft(i << 1), resize(i);
}
resize(n);
}
void ln()
{
poly f0 = *this;
int n = size();
deriv(), f0.inv(), mul(f0);
resize(n), intg(), resize(n);
}
void exp()
{
std::vector<int> va(1);
va[0] = 1; poly a;
int n = size(), m = len(n);
v.resize(m), v.swap(va);
for (int i = 1; i <= m; i *= 2)
{
a = *this, a.resize(i), a.ln();
for (int j = 0; j < i; j++)
a[j] = (va[j] + !j + mod - a[j]) % mod;
mul(a), resize(i);
}
resize(n);
}
void pw(int k)
{
ln();
for (int i = 0; i < n; i++)
v[i] = (ll)v[i] * k % mod;
exp();
}
void sqrt()
{
std::vector<int> va(1);
int n = size(), m = len(n);
poly a, b; va[0] = 1;
v.resize(m), v.swap(va);
for (int i = 1; i <= m; i <<= 1)
{
a.resize(i << 1), b.resize(i << 1);
for (int j = 0; j < i; j++)
a[j] = va[j], b[j] = v[j];
b.inv(), a.mul(b);
for (int j = 0; j < (i << 1); j++)
v[j] = (ll)(v[j] + a[j]) % mod * inv2 % mod;
resize(i);
}
resize(n);
}
} a;
inline int read()
{
ll x = 0;
char ch = getchar();
while (ch > '9' || ch < '0')
ch = getchar();
while (ch <= '9' && ch >= '0')
x = ((x * 10) + (ch ^ 48), ch = getchar();
return x;
}
signed main()
{
n = read(), __init();
a.resize(n), init(n * 2);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
a.exp();
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
Details
answer.code: In function ‘int read()’: answer.code:205:50: error: expected ‘)’ before ‘;’ token 205 | x = ((x * 10) + (ch ^ 48), ch = getchar(); | ~ ^ | ) answer.code: In function ‘int main()’: answer.code:214:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 214 | scanf("%d", &a[i]); | ~~~~~^~~~~~~~~~~~~