| 记录编号 |
538184 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[HZOI 2015] 帕秋莉的超级多项式 |
最终得分 |
100 |
| 用户昵称 |
 神利·代目 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
12.244 s |
| 提交时间 |
2019-07-22 20:22:16 |
内存使用 |
26.07 MiB |
显示代码纯文本
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#define ll long long
#define P 998244353
#define g 3
ll inv[263000];
void work_inv(int n) {
inv[1] = 1;
for (int i = 2; i <= n; ++i) inv[i] = inv[P % i] * (P - P / i) % P;
}
inline ll POW(ll x, ll y) {
for (ll z = 1;; x = x * x % P, y >>= 1)
if (y & 1) z = z * x % P;
else if (!y) return z;
}
void NTT(int* o, int n, bool op) {
for (int i = 0, j = 0; i < n; ++i) {
if (i > j)std::swap(o[i], o[j]);
for (int k = n >> 1; (j ^= k) < k; k >>= 1);
}
for (int i = 2, y; i <= n; i <<= 1)
for (ll wn = POW(g, op ? (P - 1) / i : P - 1 - (P - 1) / i), j = 0; j < n; j += i)
for (ll w = 1, k = 0, p = i >> 1; k < p; ++k, w = w * wn % P)
y = w * o[j + k + p] % P, o[j + k + p] = (o[j + k] - y + P) % P, o[j + k] = (o[j + k] + y) % P;
if (!op) {
ll invn = POW(n, P - 2);
for (int i = 0; i < n; ++i)o[i] = invn * o[i] % P;
}
}
inline void get_inv(int a[], int b[], int n) {
if (n == 1) { b[0] = POW(a[0], P - 2); return; }
static int tmp[262144];
get_inv(a, b, n >> 1);
memcpy(tmp, a, sizeof(a[0]) * n);
memset(tmp + n, 0, sizeof(a[0]) * n);
NTT(tmp, n << 1, 1), NTT(b, n << 1, 1);
for (int i = 0, r = n << 1; i < r; ++i) b[i] = (ll)b[i] * (2 - (ll)tmp[i] * b[i] % P + P) % P;
NTT(b, n << 1, 0), memset(b + n, 0, sizeof(a[0]) * n);
}
inline void get_root(int a[], int b[], int n) {
if (n == 1) { b[0] = sqrt(a[0]); return; }
static int tmp[263000], binv[263000];
get_root(a, b, n >> 1);
memset(binv, 0, sizeof(binv[0]) * n);
get_inv(b, binv, n);
memcpy(tmp, a, sizeof(a[0]) * n);
memset(tmp + n, 0, sizeof(a[0]) * n);
NTT(tmp, n << 1, 1), NTT(b, n << 1, 1), NTT(binv, n << 1, 1);
for (int i = 0, r = n << 1; i < r; ++i) b[i] = inv[2] * (b[i] + (ll)tmp[i] * binv[i] % P) % P;
NTT(b, n << 1, 0), memset(b + n, 0, sizeof(a[0]) * n);
}
inline void get_ln(int a[], int b[], int n) {
static int a_[262144], ainv[262144];
memset(ainv, 0, sizeof(ainv[0]) * (n << 1));
memset(a_, 0, sizeof(a_[0]) * (n << 1));
get_inv(a, ainv, n);
for (int i = 0; i < n - 1; ++i)a_[i] = (ll)a[i + 1] * (i + 1) % P;
NTT(ainv, n << 1, 1), NTT(a_, n << 1, 1);
for (int i = 0, r = n << 1; i < r; ++i) b[i] = (ll)a_[i] * ainv[i] % P;
NTT(b, n << 1, 0);
for (int i = n - 1; i; --i) b[i] = inv[i] * b[i - 1] % P;
b[0] = 0, memset(b + n, 0, sizeof(b[0]) * n);
}
inline void get_exp(int a[], int b[], int n) {
if (n == 1) { b[0] = 1; return; }
get_exp(a, b, n >> 1);
static int tmp[262144];
memset(tmp, 0, sizeof(tmp[0]) * (n << 1));
get_ln(b, tmp, n);
for (int i = 0; i < n; ++i) tmp[i] = ((i == 0) - tmp[i] + P + a[i]) % P;
NTT(tmp, n << 1, 1), NTT(b, n << 1, 1);
for (int i = 0, r = n << 1; i < r; ++i) b[i] = (ll)b[i] * tmp[i] % P;
NTT(b, n << 1, 0), memset(b + n, 0, sizeof(b[0]) * n);
}
inline void get_pow(int a[], int b[], int k, int n) {
static int lna[263000];
get_ln(a, lna, n);
for (int i = 0; i < n; ++i) lna[i] = (ll)k * lna[i] % P;
get_exp(lna, b, n);
}
inline void in(int& TEMP) { int EPX; for (TEMP = getchar(); TEMP < 48 || TEMP>57; TEMP = getchar()); for (TEMP ^= 48, EPX = getchar(); EPX < 58 && EPX>47; EPX = getchar())TEMP = (TEMP << 3) + (TEMP << 1) + (EPX ^ 48); }
int len, n, k, o[263000], o_root[263000], o_inv[263000], o_exp[263000];
int o_inv2[263000], ln[263000], ans[263000];
int t1[263000], t2[263000];
int main() {
freopen("polynomial.in", "r", stdin);
freopen("polynomial.out", "w", stdout);
in(n), in(k); for (int i = 0; i < n; ++i)in(o[i]);
for (len = 1; len <= n; len <<= 1);
work_inv(len << 1);
get_root(o, o_root, len);
get_inv(o_root, o_inv, len);
for (int i = n - 1; i; --i)o_inv[i] = inv[i] * o_inv[i - 1] % P;
o_inv[0] = 0;
get_exp(o_inv, o_exp, len);
get_inv(o_exp, o_inv2, len);
o_inv2[0] = (o_inv2[0] + 1) % P;
get_ln(o_inv2, ln, len);
ln[0] = (ln[0] + 1) % P;
get_pow(ln, ans, k, len);
for (int i = n; i < len << 1; ++i)ans[i] = 0;
for (int i = 1; i <= n; ++i) printf("%lld ", (ll)ans[i] * i % P);
//while(1);
}
/*
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define P 998244353
#define g 3
#define ll long long
//快速幂,PS:0^0 = 1
int mypow(int x, int y) {
int res = 1;
while (y) {
if (y & 1)res = 1ll * res * x % P;
y >>= 1;
x = 1ll * x * x % P;
}
return res;
}
//o是次数界为n的多项式系数,op=1时,对o做NTT;op=0时,对o做逆NTT
void NTT(int* o, int n, bool op) {
for (int i = 0, j = 0; i < n; ++i) {
if (i > j)std::swap(o[i], o[j]);
for (int k = n >> 1; (j ^= k) < k; k >>= 1);
}
for(int i=2,y;i<=n;i<<=1)
for(ll wn=mypow(g, op?(P-1)/i:P-1-(P-1)/i),j=0;j<n;j+=i)
for(ll w=1,k=0,p=i>>1;k<p;++k,w=w*wn%P)
y = w * o[j + k + p] % P, o[j + k + p] = (o[j + k] - y + P) % P, o[j + k] = (o[j + k] + y) % P;
if (!op) {
ll invn = mypow(n, P - 2);
for (int i = 0; i < n; ++i)o[i] = invn * o[i] % P;
}
}
int lena, lenb;
char a[150010], b[150010];
int A[150010], B[150010], C[150010];
int main() {
scanf("%s%s", a, b);
lena = strlen(a);
for (int i = lena - 1; i >= 0; --i)
A[lena - i - 1] = a[i];
lenb = strlen(b);
for (int i = lenb - 1; i >= 0; --i)
B[lenb - i - 1] = b[i];
int len = 1;
while ((len >> 1) < lena || (len >> 1) < lenb)len <<= 1;
NTT(A, len, 1), NTT(B, len, 1);
for (int i = 0; i < len; ++i)
C[i] = 1ll * A[i] * B[i] % P;
NTT(C, len, 0);
for (int i = 0; i < len; ++i) {
C[i + 1] += C[i] / 10;
C[i] %= 10;
putchar(C[i] + '0');
}
}
*/