QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#402521 | #6811. Alice's Dolls | Starrykiller# | AC ✓ | 1348ms | 28876kb | C++23 | 3.9kb | 2024-04-30 19:10:40 | 2024-04-30 19:10:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int MAXN=4e6+10, p=998244353, G=3;
int qpow(int a, int n) {
int res=1;
while (n) {
if (n&1) res=res*a%p;
a=a*a%p; n>>=1;
}
return res;
}
#define inv(x) qpow(x,p-2)
signed rev[MAXN];
using poly=vector<int>;
istream& operator>>(istream& is, poly& f) {
for (auto& i: f) cin>>i;
return is;
}
poly ntt(const poly& a, int n, int sgn=1) {
poly f=a; f.resize(n);
int bit=__lg(n);
for (int i=1; i<n; ++i)
rev[i]=(rev[i>>1]>>1) | ((i&1)<<(bit-1));
for (int i=1; i<n; ++i)
if (i<rev[i]) swap(f[i],f[rev[i]]);
for (int l=1, t=1; l<n; l<<=1, ++t) {
int step=qpow(G,p-1+((p-1)>>t)*sgn);
for (int j=0; j<n; j+=l<<1)
for (int k=j, cur=1; k<j+l; ++k, cur=cur*step%p) {
int g=f[k], h=cur*f[k+l]%p;
f[k]=(g+h)%p, f[k+l]=(p+g-h)%p;
}
}
if (sgn==-1) {
int invn=inv(n);
for (auto &i: f)
i=i*invn%p;
}
return f;
}
poly convolution(const poly& f, const poly& g) {
int n=f.size(), m=g.size(); int N=1ll<<(__lg(n+m+1)+1);
poly a=ntt(f,N), b=ntt(g,N);
for (int i=0; i<N; ++i) a[i]=a[i]*b[i]%p;
a=ntt(a,N,-1);
a.resize(n+m-1);
return a;
}
poly get_inv(const poly& f) {
assert(f[0]%p);
poly g(1); g[0]=inv(f[0]);
int deg=1; int n=f.size();
while (deg<n<<1) {
int N=deg<<1;
auto h=ntt(deg<=n?poly(f.begin(),f.begin()+deg):f,N); g=ntt(g,N);
for (int i=0; i<N; ++i)
g[i]=g[i]*(p+2-g[i]*h[i]%p)%p;
g=ntt(g,N,-1); g.resize(deg);
deg<<=1;
}
g.resize(n);
return g;
}
poly get_deriv(const poly& f) {
int n=f.size();
auto g=poly(n);
for (int i=0; i<n-1; ++i)
g[i]=(i+1)*f[i+1]%p;
return g;
}
poly get_integ(const poly& f) {
int n=f.size();
auto g=poly(n+1);
for (int i=0; i<n; ++i)
g[i+1]=f[i]*inv(i+1)%p;
g[0]=0;
return g;
}
poly get_ln(const poly& f) {
int n=f.size();
assert(f[0]==1);
auto g=get_deriv(f), h=get_inv(f);
g=convolution(g,h); g.resize(n);
g=get_integ(g); g.resize(n);
return g;
}
poly get_exp(const poly& f) {
int n=f.size(); assert(!f[0]);
int deg=1; poly g={1};
while (deg<n<<1) {
int N=deg<<1;
auto lng=get_ln(g);
for (int i=0; i<deg; ++i)
lng[i]=(p+f[i]-lng[i])%p;
lng[0]++;
lng=ntt(lng,N); g=ntt(g,N);
for (int i=0; i<N; ++i)
g[i]=g[i]*lng[i]%p;
g=ntt(g,N,-1);
deg<<=1; g.resize(deg);
}
g.resize(n);
return g;
}
poly qpow(poly a, int n, int deg) {
poly res(deg); res[0]=1;
while (n) {
if (n&1) res=convolution(res,a);
a=convolution(a,a);
res.resize(deg);
a.resize(deg);
n>>=1;
}
return res;
}
int n, m, a, b;
int fac[MAXN], ifac[MAXN];
poly get_f(int pr) {
poly f(m);
for (int i=0; i<m; ++i)
f[i]=(p-pr*ifac[i]%p)%p;
f[0]++;
poly g(m);
for (int i=0,pw=1; i<m; ++i) {
g[i]=pw*ifac[i]%p;
pw=pw*n%p;
}
f=qpow(get_inv(f),n+1,m);
f=convolution(f,g);
return f;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin>>n>>m>>a>>b; m++; n--;
// if (a==b) {
// for (int i=0; i<=m; ++i) cout<<1<<'\n';
// return 0;
// }
fac[0]=ifac[0]=1;
for (int i=1; i<=1e5; ++i) fac[i]=fac[i-1]*i%p, ifac[i]=inv(fac[i]);
int pr=a*inv(b)%p, apr=(p+1-pr)%p;
auto g=get_f(apr); poly f(m);
for (int i=0; i<m; ++i) f[i]=ifac[i];
f=convolution(f,g);
int pw=qpow(pr,n+1);
for (auto &i: f) i=i*pw%p;
for (int i=0; i<m; ++i) {
cout<<f[i]*fac[i]%p<<'\n';
}
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 13ms
memory: 10120kb
input:
1 3 1 2
output:
1 2 6 26
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 6ms
memory: 10724kb
input:
100 5 1 6
output:
1 600 363000 221433000 425510992 941092730
result:
ok 6 lines
Test #3:
score: 0
Accepted
time: 1174ms
memory: 28876kb
input:
82346 94247 998244352 998244352
output:
1 82346 791397598 40508009 538125741 435438716 697592329 964874802 317657163 799962739 585095577 16686097 449113834 769228973 331835396 374844347 218958949 104110468 158094364 333890471 898754640 11498373 509376414 878962890 373081322 784577837 472039442 921273818 635966440 395465507 275355856 33108...
result:
ok 94248 lines
Test #4:
score: 0
Accepted
time: 1348ms
memory: 27480kb
input:
99999 99998 1 1
output:
1 99999 17356471 681058015 897702913 273664856 341242002 872239399 469072873 314324010 366733079 438370760 733355951 836839610 300048400 309433479 458256580 792718955 518709315 637964452 7124024 647052287 379174959 801465042 656610000 821071425 723394325 932065530 543939213 40810170 153274766 279529...
result:
ok 99999 lines
Test #5:
score: 0
Accepted
time: 14ms
memory: 9820kb
input:
234 459 8713247 74362439
output:
1 550308667 652601851 21862568 312504180 301781771 955945774 241922434 687893799 220084008 951866075 223169979 261547613 851721240 108461996 645670062 647827677 740281647 567424949 65300355 783187507 824238091 706909540 715519504 74795499 263740113 795953643 525222901 990470578 720139891 531988015 3...
result:
ok 460 lines
Test #6:
score: 0
Accepted
time: 1125ms
memory: 27336kb
input:
100000 100000 34457 34458
output:
1 110072884 866073590 736351474 206840805 363851986 895119597 144145068 753578218 113903056 711499733 430574479 231258052 694514889 284319691 530696819 535538312 933991851 868518537 888564382 239789947 182502325 355499336 74503434 691778894 327131524 233789093 41501704 639617307 916312185 394659685 ...
result:
ok 100001 lines
Test #7:
score: 0
Accepted
time: 1138ms
memory: 25244kb
input:
100000 100000 998244351 998244352
output:
1 50000 503486294 85094752 335515298 331724101 676123256 80958981 314512322 659052656 12751483 516505166 655297143 652329290 347750398 78055519 290808848 35067066 791903803 995363140 517288436 394436580 430863665 823972579 523698332 746439583 27677016 323067719 660639896 110677907 568717926 25289325...
result:
ok 100001 lines
Test #8:
score: 0
Accepted
time: 13ms
memory: 12676kb
input:
93248 34 1 499122177
output:
1 46624 177285358 111979882 696375359 818605358 237802954 608377035 863173334 196258366 607718397 364819065 360314917 233450239 952902294 131353496 959526592 687802720 477763385 488883348 507982668 818592811 76520370 194416851 590074140 13328434 672264252 42015845 921175397 849890303 603093773 61302...
result:
ok 35 lines
Test #9:
score: 0
Accepted
time: 614ms
memory: 25428kb
input:
53 99997 2394 7681238
output:
1 955048736 470514326 41111193 709347504 116606594 22612570 620495230 589459109 278168830 277523111 890862369 212779039 908656172 927315643 325078855 630813446 435720817 357034897 545024798 456613789 312453851 69393505 463880280 934933770 586168348 444543516 547460238 575392663 993322173 625521110 7...
result:
ok 99998 lines
Test #10:
score: 0
Accepted
time: 9ms
memory: 10404kb
input:
100000 0 123456789 234567890
output:
1
result:
ok single line: '1'