QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#425955 | #6112. Village Planning | HKOI0# | AC ✓ | 513ms | 32868kb | C++20 | 7.1kb | 2024-05-30 19:35:22 | 2024-05-30 19:35:23 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
const int MOD = 998244353, root = 62;
typedef vector<ll> vl;
int pm(int a, int b){
if (b == 0) return 1;
return pm(a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD;
}
int mi(int a){
return pm(a, MOD - 2);
}
void ntt(vl & a) {
int n = a.size(), L = 63 - __builtin_clzll(n);
static vl rt(2, 1);
for (static int k = 2, s = 2; k < n; k *= 2, s++) {
rt.resize(n);
ll z[] = {1, pm(root, MOD >> s)};
for (int i = k; i < k * 2; i++) rt[i] = rt[i / 2] * z[i & 1] % MOD;
}
vi rev(n);
for (int i = 0; i < n; i++)
rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
for (int i = 0; i < n; i++)
if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2)
for (int i = 0; i < n; i += 2 * k) for (int j = 0; j < k; j++) {
int z = rt[j + k] * a[i + j + k] % MOD, &ai = a[i + j];
a[i + j + k] = ai - z + (z > ai ? MOD : 0);
ai += (ai + z >= MOD ? z - MOD : z);
}
}
vl conv(const vl& a, const vl& b) {
if (a.empty() || b.empty()) return {};
int s = a.size() + b.size() - 1, B = 64 - __builtin_clzll(s), n = 1 << B;
int inv = mi(n);
vl L(a), R(b), out(n);
L.resize(n), R.resize(n); ntt(L); ntt(R);
for (int i = 0; i < n; i++) {
out[-i & (n - 1)] = L[i] * R[i] % MOD * inv % MOD;
}
ntt(out);
return {out.begin(), out.begin() + s};
}
const int N = 2e5 + 11;
int fa[N], fi[N];
int binom(int n, int r){
return fa[n] * fi[n - r] % MOD * fi[r] % MOD;
}
struct poly{
vector<int> a;
void normalise() { while (!a.empty() && a.back() == 0) a.pop_back(); }
poly(int v) { a.push_back(v); normalise(); }
poly(vector<int> a) : a(a) { normalise(); }
bool is_zero() const { return a.empty(); }
int size() const { return a.size(); }
int deg() const { return (int) a.size() - 1; }
void resize(int n) { a.resize(n); }
int operator[] (int idx) const { return 0 <= idx && idx < a.size() ? a[idx] : 0; }
int& at(int idx) { assert(0 <= idx && idx < a.size()); return a[idx]; }
void print() const { for (auto x : a) cout << x << ' '; cout << endl; }
poly operator* (const poly& o) const {
return conv(a, o.a);
}
friend poly operator+ (const poly& a, const poly& b){
vector<int> res(max(a.size(), b.size()));
for (int i = 0; i < res.size(); i++) {
res[i] = a[i] + b[i] >= MOD ? a[i] + b[i] - MOD : a[i] + b[i];
}
return res;
}
friend poly operator- (const poly& a, const poly& b){
vector<int> res(max(a.size(), b.size()));
for (int i = 0; i < res.size(); i++) {
res[i] = a[i] - b[i] < 0 ? a[i] - b[i] + MOD : a[i] - b[i];
}
return res;
}
void operator-= (const poly& o) { *this = *this - o; }
poly mod_xk(size_t k) const {
return vector<int>{a.begin(), a.begin() + min(a.size(), k)};
}
poly mul_xk(size_t k) const {
vector<int> b(k, 0); for (auto x : a) b.push_back(x);
return b;
}
poly div_xk(size_t k) const {
return size() < k ? vector<int>{} : vector<int>{a.begin() + k, a.end()};
}
poly substr(size_t l, size_t r) const {
return div_xk(l).mod_xk(r - l);
}
poly deriv () const {
if (size() <= 1) return {0};
vector<int> res(size() - 1);
for (int i = 1; i <= deg(); i++) {
res[i - 1] = a[i] * i % MOD;
}
return res;
}
poly integr () const {
vector<int> res(size() + 1);
for (int i = 0; i <= deg(); i++) {
res[i + 1] = a[i] * mi(i + 1) % MOD;
}
return res;
}
poly negx () const {
vector<int> res(size());
for (int i = 0; i < size(); i++) {
res[i] = i % 2? (MOD - a[i]) % MOD : a[i];
}
return res;
}
poly x2 () const {
if (size() == 0) return {0};
vector<int> res(size() * 2 - 1);
for (int i = 0; i < size(); i++) {
res[i * 2] = a[i];
}
return res;
}
pair<poly, poly> bisect() const {
vector<int> q0, q1;
for (int i = 0; i < size(); i++) {
(i % 2 ? q1 : q0).push_back(a[i]);
}
return {q0, q1};
}
poly recp(size_t k) const {
auto q = mod_xk(k);
if (k == 1) return vector<int>{mi(a[0])};
auto [q0, q1] = q.negx().bisect();
poly t = (q0 * q0 - (q1 * q1).mul_xk(1));
poly it = t.recp((k + 1) / 2);
return ((q0 * it).x2() + (q1 * it).x2().mul_xk(1)).mod_xk(k);
}
poly log(size_t n) const {
assert(a[0] == 1);
return (deriv().mod_xk(n) * recp(n)).integr().mod_xk(n);
}
poly exp(size_t n) const {
if (is_zero()) return 1;
assert(a[0] == 0);
poly ans = 1;
size_t a = 1;
while (a < n) {
poly C = ans.log(a * 2).div_xk(a) - substr(a, a * 2);
ans -= (ans * C).mod_xk(a).mul_xk(a);
a *= 2;
}
return ans.mod_xk(n);
}
poly egf() const {
vector<int> res(size());
for (int i = 0; i <= deg(); i++) {
res[i] = a[i] * fi[i] % MOD;
}
return res;
}
poly ops() const {
vector<int> res(size());
for (int i = 0; i <= deg(); i++) {
res[i] = a[i] * fa[i] % MOD;
}
return res;
}
poly mul_x2(int x) const {
vector<int> res(size());
int m2 = 1, m1 = 1;
for (int i = 1; i <= deg(); i++) {
m2 = m2 * m1 % MOD;
res[i] = a[i] * m2 % MOD;
m1 = m1 * x % MOD;
}
return res;
}
};
int a[4];
void solve() {
int m, k; cin >> m >> k;
for (int i = 0; i <= k; i++) cin >> a[i];
vector<int> t(m + 1);
t[1] = 1; for (int i = 2; i <= m; i++) t[i] = pm(i, i - 2);
a[1] = a[1] * mi(a[0]) % MOD;
a[2] = a[2] * mi(a[0]) % MOD;
poly S1 = poly(t).egf().mul_x2(a[1]);
poly T = poly(t).egf().mul_x2(a[1] * mi(a[2]) % MOD);
T = T.deriv().mul_xk(1);
// poly T = vector<int>{0, 1};
// (((1 - T).log(m + 1) * (-1) - T - T * T * mi(2)) * mi(2)).ops().print();
// poly S2 = (T * T * T * mi(6) + T * T * T * T * mi(8)).mod_xk(m + 1).mul_x2(a[2]);
poly S2 = (((1 - T).log(m + 1) * (-1) - T - T * T * mi(2)) * mi(2)).mul_x2(a[2]);
// T.print(); (S2.ops() * 2).print();
poly S = S1 + S2;
poly ans = S.exp(m + 1).mul_x2(a[0]).ops();
for (int i = 2; i <= m; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
}
signed main() {
fa[0] = 1; for (int i = 1; i < N; i++) fa[i] = fa[i - 1] * i % MOD;
fi[N - 1] = mi(fa[N - 1]); for (int i = N - 2; i >= 0; i--) fi[i] = fi[i + 1] * (i + 1) % MOD;
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 6644kb
input:
4 0 2
output:
2 8 64
result:
ok 3 number(s): "2 8 64"
Test #2:
score: 0
Accepted
time: 3ms
memory: 6928kb
input:
5 1 3 4
output:
7 327 96721 169832849
result:
ok 4 number(s): "7 327 96721 169832849"
Test #3:
score: 0
Accepted
time: 0ms
memory: 6712kb
input:
6 2 5 6 7
output:
11 1566 3000672 306031599 466869291
result:
ok 5 number(s): "11 1566 3000672 306031599 466869291"
Test #4:
score: 0
Accepted
time: 3ms
memory: 6968kb
input:
7 3 8 9 10 11
output:
17 5427 31856976 326774674 449014006 997476587
result:
ok 6 numbers
Test #5:
score: 0
Accepted
time: 357ms
memory: 27096kb
input:
100000 0 12345678
output:
12345678 644056040 211986440 366246078 129089719 221368866 283124263 92530495 602608963 591370683 990229283 164971576 676013258 861632667 266225306 38421683 734331905 954922439 924295443 581924621 641884577 953780417 395588140 569420628 269024687 923445182 812638938 221225256 415075963 833284693 182...
result:
ok 99999 numbers
Test #6:
score: 0
Accepted
time: 351ms
memory: 27168kb
input:
100000 0 1
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 99999 numbers
Test #7:
score: 0
Accepted
time: 335ms
memory: 27064kb
input:
100000 0 998244352
output:
998244352 998244352 1 1 998244352 998244352 1 1 998244352 998244352 1 1 998244352 998244352 1 1 998244352 998244352 1 1 998244352 998244352 1 1 998244352 998244352 1 1 998244352 998244352 1 1 998244352 998244352 1 1 998244352 998244352 1 1 998244352 998244352 1 1 998244352 998244352 1 1 998244352 99...
result:
ok 99999 numbers
Test #8:
score: 0
Accepted
time: 332ms
memory: 25228kb
input:
73812 0 3141592
output:
3141592 502595211 930804156 494129912 890907052 937804910 155794517 312377295 141669564 196035410 418956765 791193589 756093320 361837829 72344530 578759786 313970847 636643125 747705681 676578954 596656200 395491001 81642642 219037384 969715473 813221369 410880484 305249904 367704238 564789451 2855...
result:
ok 73811 numbers
Test #9:
score: 0
Accepted
time: 348ms
memory: 27076kb
input:
100000 1 1 1
output:
2 7 38 291 2932 36961 561948 10026505 205608536 774463267 589147789 829299664 243375906 66263611 965270387 154777431 601662699 929537049 893635200 219507261 392236640 775545378 714600599 56551872 187837583 189925757 50494333 611131417 258806070 413153890 109986030 618449809 731781234 408507333 28278...
result:
ok 99999 numbers
Test #10:
score: 0
Accepted
time: 345ms
memory: 27248kb
input:
100000 1 3127218 14172129
output:
17299347 544607138 680226212 305869647 912178269 916199911 125174848 307445424 256318706 16877857 462417641 298914440 279886537 287167270 564531297 111249855 460247698 805600287 58601732 199348757 45669640 366398551 149741463 906663559 976291245 366968697 90322856 347392377 225958266 867152353 84926...
result:
ok 99999 numbers
Test #11:
score: 0
Accepted
time: 353ms
memory: 27260kb
input:
100000 1 998244352 998244352
output:
998244351 998244346 38 291 998241421 998207392 561948 10026505 792635817 223781086 589147789 829299664 754868447 931980742 965270387 154777431 396581654 68707304 893635200 219507261 606007713 222698975 714600599 56551872 810406770 808318596 50494333 611131417 739438283 585090463 109986030 618449809 ...
result:
ok 99999 numbers
Test #12:
score: 0
Accepted
time: 350ms
memory: 27048kb
input:
100000 1 1 998244352
output:
0 998244348 2 211 998244033 998216494 84828 7784137 960946049 213292735 225093311 837100977 925933466 413576187 774455991 727906343 96771916 604528716 51075694 784377733 280737476 769195767 101561083 881507340 731348568 702337822 594671739 556715938 256133261 758927779 131639043 21463936 216796323 5...
result:
ok 99999 numbers
Test #13:
score: 0
Accepted
time: 360ms
memory: 25928kb
input:
99999 1 9 99
output:
108 2935683 905844104 884930131 610271296 167794683 874562044 144589021 654900997 739155189 156126745 259210590 364360898 474007353 202797476 105542 287700849 491427578 861300599 773784742 92662708 677626795 300989836 644734128 859127006 985588013 222572430 241496128 218066520 262003703 218365187 63...
result:
ok 99998 numbers
Test #14:
score: 0
Accepted
time: 493ms
memory: 31744kb
input:
100000 2 1 1 1
output:
2 8 57 608 8524 145800 2918123 66617234 706669081 384399752 501322809 82724887 450722832 428972217 181542374 652797702 609850214 874870984 765605342 147495034 696875380 556350159 263684494 785985697 927559849 434848582 197878990 406693583 792170563 800087590 373988208 3254512 227893387 739644336 696...
result:
ok 99999 numbers
Test #15:
score: 0
Accepted
time: 500ms
memory: 32868kb
input:
100000 2 998244352 998244352 998244352
output:
998244351 998244345 57 608 998235829 998098553 2918123 66617234 291575272 613844601 501322809 82724887 547521521 569272136 181542374 652797702 388394139 123373369 765605342 147495034 301368973 441894194 263684494 785985697 70684504 563395771 197878990 406693583 206073790 198156763 373988208 3254512 ...
result:
ok 99999 numbers
Test #16:
score: 0
Accepted
time: 493ms
memory: 31988kb
input:
100000 2 281937 171272 818181
output:
453209 512671672 278512868 972903940 963889823 375524158 428852795 714712820 193423966 165771254 162267306 204045783 876959521 473792164 304361203 460808773 98690013 488934388 435599530 450870701 792671254 1256206 718918641 426372134 650280375 627518981 362622544 779950240 420558947 804518581 306136...
result:
ok 99999 numbers
Test #17:
score: 0
Accepted
time: 513ms
memory: 32568kb
input:
100000 2 1 1 998244352
output:
2 6 25 148 444 2980 998007724 994444067 789019707 937713401 652696128 460709735 933939061 959266124 30637590 479943383 784813821 248526178 48920653 405125075 70154041 788942931 905407075 251620484 726975243 817166755 787087127 286858468 497248937 892303208 21757780 391004220 259168724 448745923 2696...
result:
ok 99999 numbers
Test #18:
score: 0
Accepted
time: 50ms
memory: 9960kb
input:
12345 2 12 34 56
output:
46 309944 696841896 34097 839911467 962123005 585561425 462868037 206865996 449479312 891836115 711985062 231298365 616854842 434054154 804312719 994410789 195833040 464775852 182224638 659030740 144745347 320691427 558457264 976986661 856936949 776831877 304530749 948340836 185453762 923617027 4324...
result:
ok 12344 numbers
Test #19:
score: 0
Accepted
time: 498ms
memory: 31744kb
input:
100000 3 1 1 1 1
output:
2 8 57 608 8524 145800 2918123 66617234 706669081 384399752 501322809 82724887 450722832 428972217 181542374 652797702 609850214 874870984 765605342 147495034 696875380 556350159 263684494 785985697 927559849 434848582 197878990 406693583 792170563 800087590 373988208 3254512 227893387 739644336 696...
result:
ok 99999 numbers
Test #20:
score: 0
Accepted
time: 488ms
memory: 31788kb
input:
100000 3 998244352 998244352 998244352 998244352
output:
998244351 998244345 57 608 998235829 998098553 2918123 66617234 291575272 613844601 501322809 82724887 547521521 569272136 181542374 652797702 388394139 123373369 765605342 147495034 301368973 441894194 263684494 785985697 70684504 563395771 197878990 406693583 206073790 198156763 373988208 3254512 ...
result:
ok 99999 numbers
Test #21:
score: 0
Accepted
time: 496ms
memory: 32568kb
input:
100000 3 1 1 1 998244352
output:
2 8 57 608 8524 145800 2918123 66617234 706669081 384399752 501322809 82724887 450722832 428972217 181542374 652797702 609850214 874870984 765605342 147495034 696875380 556350159 263684494 785985697 927559849 434848582 197878990 406693583 792170563 800087590 373988208 3254512 227893387 739644336 696...
result:
ok 99999 numbers
Test #22:
score: 0
Accepted
time: 500ms
memory: 31844kb
input:
100000 3 998244352 998244352 998244352 1
output:
998244351 998244345 57 608 998235829 998098553 2918123 66617234 291575272 613844601 501322809 82724887 547521521 569272136 181542374 652797702 388394139 123373369 765605342 147495034 301368973 441894194 263684494 785985697 70684504 563395771 197878990 406693583 206073790 198156763 373988208 3254512 ...
result:
ok 99999 numbers
Test #23:
score: 0
Accepted
time: 511ms
memory: 31920kb
input:
100000 3 39812 123981239 1290381 1283
output:
124021051 67339975 610940933 408695057 796120558 732352050 742684798 578755915 503423632 235119013 52640117 305547363 180205489 607460460 640936318 451441684 625594117 112271482 373199741 61881167 584975048 735163526 826958338 177994457 564490691 515336777 188170717 14714304 123547987 955921656 4472...
result:
ok 99999 numbers
Test #24:
score: 0
Accepted
time: 58ms
memory: 10196kb
input:
14141 3 14 1414 141414 14141414
output:
1428 945752601 419407338 158119279 300328028 268761179 344561129 762205485 365322155 382686822 562338952 664038583 58768435 150681229 319859602 215939428 298859979 361628698 332192869 242965952 140893160 904129517 921097456 654528502 906182473 473885111 536944482 344305087 540463307 642375040 802417...
result:
ok 14140 numbers
Test #25:
score: 0
Accepted
time: 349ms
memory: 27244kb
input:
100000 1 2137823 976866230
output:
979004053 685468134 789996596 45315913 734252866 114071945 227042021 607285911 6127041 313213017 262099069 41798701 310215621 339746433 773820973 760546987 20536197 958021016 391852714 130791407 69534615 385424002 927181151 954069501 620988719 894425458 857430548 138216414 59805573 582619921 3385707...
result:
ok 99999 numbers
Test #26:
score: 0
Accepted
time: 512ms
memory: 32568kb
input:
100000 2 333333333 664911020 3141592
output:
0 539258907 807446860 639440248 372497013 966644648 26618326 92668364 524085158 762416710 132072582 648218139 78338897 869553104 917456438 803122375 111752795 178884244 432005206 107545093 716582369 668087725 697533485 951887327 403870585 48142129 681202611 787661753 685854292 137355353 15775756 167...
result:
ok 99999 numbers
Test #27:
score: 0
Accepted
time: 501ms
memory: 31840kb
input:
100000 3 876543210 121701143 341287 234918
output:
0 489859077 963922989 839484222 354669793 734128410 360680805 298312130 493734073 937432342 397795686 348825298 101928832 887477366 876716304 876644325 217490999 828534006 772562207 907689566 966968848 34764183 351354852 557088404 975230095 531895571 637255401 909706248 962657325 937587650 813263917...
result:
ok 99999 numbers