QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#303364 | #621. 多项式指数函数 | _LAP_ | 100 ✓ | 2696ms | 86424kb | C++14 | 9.5kb | 2024-01-12 10:03:19 | 2024-01-12 10:03:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> poly;
const int N = 5e6 + 10, MOD = 998244353;
inline int Plus(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b; }
inline int Minus(int a, int b) {return a - b < 0 ? a - b + MOD : a - b; }
inline int ksm(long long a, int b) {
long long r = 1;
for(; b; b >>= 1, a = a * a % MOD)
if(b & 1) r = r * a % MOD;
return r;
}
namespace My_poly {
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
int rev[N], iv[N];
inline void make_iv() {
// 处理 [1, N - 1] 的逆元并存到 iv[] 中
iv[1] = 1;
for(int i = 2; i < N; i ++)
iv[i] = Minus(0, 1ll * iv[MOD % i] * (MOD / i) % MOD);
}
inline void make_rev(int n) {
for(int i = 1; i < n; i ++)
rev[i] = ((rev[i >> 1] >> 1) | (i & 1) * (n >> 1));
}
inline void NTT(poly &A, int type) {
// 调用前请确保 rev[] 数组的正确
// type == 1:= DFT
// type == -1:= IDFT
static const int g = 3; // 原根
int n = A.size();
for(int i = 0; i < n; i ++)
if(i < rev[i]) swap(A[i], A[rev[i]]);
for(int h = 2; h <= n; h <<= 1) {
long long step = ksm(g, (MOD - 1) / h);
if(type == -1) step = ksm(step, MOD - 2);
for(int i = 0; i < n; i += h)
for(int j = i, mul = 1; j < i + (h >> 1); j ++, mul = mul * step % MOD) {
int u = A[j], v = 1ll * A[j + (h >> 1)] * mul % MOD;
A[j] = Plus(u, v), A[j + (h >> 1)] = Minus(u, v);
}
}
if(type == -1) {
long long mul = ksm(n, MOD - 2);
for(int i = 0; i < n; i ++)
A[i] = A[i] * mul % MOD;
}
}
poly operator + (const poly &lhs, const poly &rhs) {
poly res = lhs; res.resize(max(lhs.size(), rhs.size()), 0);
for(int i = 0; i < rhs.size(); i ++) res[i] = Plus(res[i], rhs[i]);
return res;
}
poly operator - (const poly &lhs, const poly &rhs) {
poly res = lhs; res.resize(max(lhs.size(), rhs.size()), 0);
for(int i = 0; i < rhs.size(); i ++) res[i] = Minus(res[i], rhs[i]);
return res;
}
poly operator * (const int lhs, const poly &rhs) {
poly res = rhs;
for(int i = 0; i < rhs.size(); i ++)
res[i] = 1ll * res[i] * lhs % MOD;
return res;
}
poly operator * (const poly &lhs, const int rhs) {
poly res = lhs;
for(int i = 0; i < lhs.size(); i ++)
res[i] = 1ll * res[i] * rhs % MOD;
return res;
}
poly operator * (poly A, poly B) {
int h = 1;
while(h <= A.size() + B.size()) h <<= 1;
A.resize(h, 0), B.resize(h, 0);
make_rev(h);
NTT(A, 1), NTT(B, 1);
for(int i = 0; i < h; i ++) A[i] = 1ll * A[i] * B[i] % MOD;
NTT(A, -1); return A;
}
inline poly derivative(poly A) {
// 多项式求导
for(int i = 1; i < A.size(); i ++)
A[i - 1] = 1ll * i * A[i] % MOD;
if(!A.empty()) A.pop_back();
return A;
}
inline poly integrate(poly A) {
// 多项式积分
// 使用前请保证调用过make_iv函数或init函数
A.emplace_back(0);
for(int i = A.size() - 1; i >= 1; i --)
A[i] = 1ll * A[i - 1] * iv[i] % MOD;
A[0] = 0; // 不定积分的常数 C
return A;
}
inline poly inv(poly A, int n) {
// 多项式求逆
// 返回模 x^n 意义下 A 的逆元
int h = 1; while(h < n) h <<= 1; A.resize(h, 0);
if(A.empty()) return poly();
poly res(1, ksm(A[0], MOD - 2));
for(int i = 2; i <= h; i <<= 1) {
poly q(A.begin(), A.begin() + i);
res.resize(2 * i, 0), q.resize(2 * i, 0);
make_rev(2 * i), NTT(res, 1), NTT(q, 1);
for(int j = 0; j < 2 * i; j ++) res[j] = 1ll * res[j] * Minus(2, 1ll * res[j] * q[j] % MOD) % MOD;
NTT(res, -1); res.resize(i);
}
res.resize(n); return res;
}
inline poly ln(poly A, int n) {
// 多项式 ln,返回 ln A 在模 x^n 意义下的结果
// 调用前请保证 A[0] = 1
A.resize(n, 0);
A = derivative(A) * inv(A, n); A.resize(n);
return integrate(A);
}
inline poly exp(poly A, int n) {
// 多项式 exp,返回exp A 在模 x^n 意义下的结果
// 调用前请保证 A[0] = 0
if(n == 1) return poly(1, 1);
int t = (n + 1) >> 1;
poly res = exp(poly(A.begin(), A.begin() + t), t);
res = res * (poly(1, 1) - ln(res, n) + A);
res.resize(n); return res;
}
inline poly power(poly A, int k, int n) {
// 多项式快速幂,返回 A^k 在模 x^n 意义下的结果
// 不要求 A[0] = 1
int p = -1; A.resize(n, 0);
for(int i = 0; i < n; i ++)
if(A[i] != 0) {p = i; break; }
if(p == -1) return A; // A = 0
long long val = ksm(A[p], k), mul = ksm(A[p], MOD - 2);
for(int i = p; i < n; i ++) A[i - p] = A[i] * mul % MOD;
for(int i = n - p; i < n; i ++) A[i] = 0;
A = exp(k * ln(A, n), n);
p = min(1ll * p * k, 1ll * n);
for(int i = p; i < n; i ++) A[i] = A[i - p] * val % MOD;
for(int i = 0; i < p; i ++) A[i] = 0;
return A;
}
inline poly power(poly A, string k, int n) {
// 多项式快速幂,返回 A^k 在模 x^n 意义下的结果
// 不要求 A[0] = 1
long long mod1 = 0, mod2 = 0;
bool zero = false; // 答案是否为 0
int p = -1; A.resize(n, 0);
for(int i = 0; i < n; i ++)
if(A[i] != 0) {p = i; break; }
if(p == -1) return A; // A = 0
for(int i = 0; i < k.size(); i ++) {
if((mod1 * 10 + (k[i] - '0')) * p >= n) {zero = true; break; }
mod1 = (mod1 * 10 + (k[i] - '0')) % MOD;
mod2 = (mod2 * 10 + (k[i] - '0')) % (MOD - 1); // 指数对 \varphi(MOD) 取模
}
if(zero) return poly(n, 0);
long long val = ksm(A[p], mod2), mul = ksm(A[p], MOD - 2);
for(int i = p; i < n; i ++) A[i - p] = A[i] * mul % MOD;
for(int i = n - p; i < n; i ++) A[i] = 0;
A = exp(mod1 * ln(A, n), n);
p = p * mod1;
for(int i = n - 1; i >= p; i --) A[i] = A[i - p] * val % MOD;
for(int i = 0; i < p; i ++) A[i] = 0;
return A;
}
inline poly sqrt1(poly A, int n) {
// 多项式开根,返回 \sqrt{A} 在模 x^n 意义下的结果
// 调用时请保证 A[0] = 1,可以稍加修改得到 A[0] 为完全平方数时的算法
int h = 1; while(h < n) h <<= 1;
A.resize(h, 0); poly res(1, 1);
for(int i = 2; i <= h; i <<= 1) {
res = (res * res + poly(A.begin(), A.begin() + i)) * inv(2 * res, i);
res.resize(i);
}
res.resize(n); return res;
}
// 二次剩余相关
long long w;
struct Complex {
int x, y;
Complex(int _x = 0, int _y = 0): x(_x), y(_y) {}
};
Complex operator * (const Complex &lhs, const Complex &rhs)
{return Complex(Plus(1ll * lhs.x * rhs.x % MOD, 1ll * lhs.y * rhs.y % MOD * w % MOD),
Plus(1ll * lhs.x * rhs.y % MOD, 1ll * lhs.y * rhs.x % MOD)); }
inline Complex complex_ksm(Complex A, int b) {
Complex r(1, 0);
for(; b; b >>= 1, A = A * A)
if(b & 1) r = r * A;
return r;
}
long long Cipolla(long long x) {
if (ksm(x,(MOD - 1) >> 1) == MOD - 1) return -1;
while(true) {
long long a = Rand() % MOD;
w = (a * a % MOD + MOD - x) % MOD;
if(ksm(w,(MOD - 1) >> 1) == MOD - 1) {
int res = complex_ksm(Complex(a, 1), (MOD + 1) >> 1).x;
return std::min(res, MOD - res); // 选用首项较小的解
}
}
}
inline poly sqrt(poly A, int n) {
// 多项式开根,返回 \sqrt{A} 在模 x^n 意义下的结果
// 调用时不需要保证 A[0] = 1
if(A.empty()) return A;
A.resize(n, 0);
long long val = A[0], mul = ksm(A[0], MOD - 2);
for(int i = 0; i < n; i ++) A[i] = A[i] * mul % MOD;
A = sqrt1(A, n);
val = Cipolla(val);
for(int i = 0; i < n; i ++) A[i] = A[i] * val % MOD;
return A;
}
inline void Rev(poly &A) {
// 反转系数
int n = (int)A.size() - 1;
for(int i = 0; 2 * i < n; i ++)
swap(A[i], A[n - i]);
}
inline pair<poly, poly> Div(poly A, poly B) {
// 多项式除法,返回的 std::pair 中第一维是商,第二维是余数
while(!A.empty() && A.back() == 0) A.pop_back();
while(!B.empty() && B.back() == 0) B.pop_back();
if(A.size() < B.size()) return {poly(1, 0), A};
int n = (int)A.size() - 1, m = (int)B.size() - 1;
Rev(A), Rev(B); poly p = A * inv(B, n - m + 1); p.resize(n - m + 1, 0);
Rev(A), Rev(B), Rev(p); poly r = A - B * p; r.resize(m, 0);
return {p, r};
}
inline void init() {make_iv(); }
} // namespace My_poly
using namespace My_poly;
int main() {
ios::sync_with_stdio(false), cin.tie(0);
init(); // poly 初始化
int n; cin >> n; poly f(n);
for(int i = 0; i < n; i ++) cin >> f[i];
f = exp(f, n);
for(int i = 0; i < n; i ++)
cout << f[i] << " \n"[i == n - 1];
return 0;
}
详细
Test #1:
score: 20
Accepted
time: 31ms
memory: 23128kb
input:
100 0 158447743 737554986 671332600 489297184 754299210 115728600 816221630 819073359 691660913 910093246 562505672 355119917 385019894 611338034 123976316 122342952 82142434 796101450 994778874 575255638 493217967 652609142 662045597 783871340 470398790 241710709 754059035 534582325 836438174 95789...
output:
1 158447743 989903074 918187254 200068193 455062373 11196740 759336019 312075964 992242039 123230223 144998958 189062409 420150911 170942299 432890803 760087114 639614944 787205333 63667632 243571846 141993017 450288335 173318832 743144111 879389773 95666186 453410000 569486107 512729334 226210545 5...
result:
ok 100 numbers
Test #2:
score: 20
Accepted
time: 40ms
memory: 23264kb
input:
5000 0 354399910 26360255 630255958 717224815 366941345 333979504 905420494 38176634 475666562 611197455 433060682 509600868 845217181 520468365 529689763 431747498 192834976 685184103 287994809 273221518 522219732 427553800 10872482 525061651 448069946 183539744 610476003 840167561 241104955 404100...
output:
1 354399910 51676417 184411965 928033808 589971658 936383703 745898312 943454394 65252947 270867254 772620225 995104944 58521883 96491645 326592384 283913887 140742590 960115688 684602174 623426872 184484323 952879775 315489867 167038509 580362327 164714100 833258994 345402076 261957154 469710461 98...
result:
ok 5000 numbers
Test #3:
score: 20
Accepted
time: 91ms
memory: 24640kb
input:
30000 0 147199510 293972908 780683378 633744119 800282266 162025013 919460711 939176222 298044997 277962122 729446209 455723129 756791462 84697115 579989768 945113433 549318980 229266945 869577376 103161009 960973464 440149102 836285074 687333626 638404974 184096947 370164754 454531549 142629528 150...
output:
1 147199510 30930552 734023222 564008583 299902819 450980389 806779390 654937901 981162061 206882721 35851319 707998765 357594654 305814262 734562024 591099032 543969413 539432668 154163976 451201740 856569012 898961429 732819402 243444529 673245321 601964526 206333661 876679409 438174247 903706710 ...
result:
ok 30000 numbers
Test #4:
score: 20
Accepted
time: 310ms
memory: 30028kb
input:
100000 0 279349013 196667718 617497154 78288698 996674429 180463729 304956112 173800460 352061138 224505321 119706982 726737325 564797383 757014824 888433954 747100108 723246918 645172013 184990722 321964667 456686646 138153830 701558524 317746193 650472945 49496183 864461799 982372868 582778782 242...
output:
1 279349013 426120005 205100346 421201310 474118168 879116053 749708347 23319122 872190753 903275287 797670709 327019687 707029564 46014243 838268797 28223150 48499086 927009654 52188573 200586020 4624185 827007182 201682326 552029133 820855946 97607062 601649418 37529652 24405665 116064030 62051631...
result:
ok 100000 numbers
Test #5:
score: 20
Accepted
time: 2696ms
memory: 86424kb
input:
1000000 0 204517192 162156394 729093416 352181074 335898409 357987855 386581690 26622360 437289663 34104646 938411413 659876244 293619518 291093969 909364118 179765868 89417259 632261731 375051702 493701794 771716785 682264158 329653513 86558030 9195128 957504298 22555222 384175297 128022431 5957444...
output:
1 204517192 619471860 517479130 453571099 756084155 250936574 733632267 123356262 736823877 36879005 134860159 91607107 898896915 410588432 269428255 936285724 807500080 148699607 694600424 104902381 245153045 814276600 610840817 459421157 797608659 275590448 967892574 251820609 688675003 675994534 ...
result:
ok 1000000 numbers