QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#402518 | #6811. Alice's Dolls | Starrykiller# | WA | 13ms | 12352kb | C++23 | 3.9kb | 2024-04-30 19:05:16 | 2024-04-30 19:05:16 |
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';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 13ms
memory: 12352kb
input:
1 3 1 2
output:
1 2 6 26
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 8ms
memory: 8692kb
input:
100 5 1 6
output:
1 600 363000 221433000 425510992 941092730
result:
ok 6 lines
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 5824kb
input:
82346 94247 998244352 998244352
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:
wrong answer 2nd lines differ - expected: '82346', found: '1'