QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#474100 | #9120. Huge Segment Tree | PhantomThreshold# | RE | 11ms | 21300kb | C++17 | 3.0kb | 2024-07-12 16:06:44 | 2024-07-12 16:06:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
namespace NTT{
const int MOD=998244353,g=3,ig=332748118;
const int MAXN=1077777;
inline long long poww(long long x,long long y){
long long ret=1;
while (y){
if (y&1) ret*=x,ret%=MOD;
x*=x,x%=MOD;
y>>=1;
}
return ret;
}
inline long long inv(long long x){return poww(x,MOD-2);}
int R[MAXN];
inline void fft(vector<long long> &a,int L,int ty){
for (int i=0;i<L;i++) i>R[i]?swap(a[i],a[R[i]]):void(0);
for (int i=1;i<L;i<<=1){
long long w=poww(ty,(MOD-1)/(i<<1));
for (int j=0;j<L;j+=(i<<1)){
long long wn=1;
for (int k=j;k<i+j;k++){
long long t=wn*a[i+k]%MOD;
a[i+k]=a[k]-t;a[i+k]<0?a[i+k]+=MOD:0;
a[k]+=t;a[k]>=MOD?a[k]-=MOD:0;
wn=wn*w%MOD;
}
}
}
}
inline vector<long long> mul(vector<long long> A,vector<long long> B){
int L=1,n=A.size()-1,m=B.size()-1;
while (L<=n+m) L<<=1;
A.resize(L);
B.resize(L);
for (int i=1;i<L;i<<=1)
for (int j=0;j<i;j++)
R[i+j]=R[j]+L/(i<<1);
fft(A,L,g);
fft(B,L,g);
vector<long long> ret(L);
for (int i=0;i<L;i++) ret[i]=A[i]*B[i]%MOD;
fft(ret,L,ig);
long long invL=inv(L);
for (int i=0;i<L;i++) ret[i]=ret[i]*invL%MOD;
ret.resize(n+m+1);
return ret;
}
}
typedef long long ll;
const int maxn=1000000;
const ll mod=998244353;
inline void add(ll &A,ll B){A+=B;if (A>=mod) A-=mod;}
inline void sub(ll &A,ll B){A-=B;if (A<0) A+=mod;}
ll ksm(ll a,ll x){
ll ret=1;
for (;x;x>>=1,a=a*a%mod) if (x&1) ret=ret*a%mod;
return ret;
}
ll inv(ll a){return ksm(a,mod-2);}
ll fac[maxn+50];
ll ifac[maxn+50];
void prepare(){
fac[0]=1;
for (int i=1;i<=maxn;i++) fac[i]=fac[i-1]*i%mod;
ifac[maxn]=inv(fac[maxn]);
for (int i=maxn-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
//
// for (int i=0;i<=10;i++) cout << fac[i] << " ";
// cout << endl;
//
// for (int i=0;i<=10;i++) cout << ifac[i] << " ";
// cout << endl;
//
}
ll C(ll n,ll m){
if (m<0 || m>n) return 0;
return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
ll K;
int main(){
ios_base::sync_with_stdio(false);
prepare();
cin >> K;
vector<ll> A(2*K-1);
vector<ll> ans(2*K-1);
for (ll c=0;c<=K-1;c++){
ll coef=ksm(2,c);
ll d=K-1-c;
sub(ans[2],coef);
add(ans[1],coef);
add(A[2*d],coef);
add(A[d+1],coef*2%mod);
sub(A[d],coef*4%mod);
add(A[2],coef);
sub(A[1],coef*4%mod);
add(A[0],coef*4%mod);
}
for (ll i=0;i<=2*K-2;i++) A[i]=A[i]*fac[i]%mod;
reverse(A.begin(),A.end());
vector<ll> tmp(2*K-1);
for (ll i=0;i<=2*K-2;i++) tmp[i]=ifac[i];
vector<ll> B=NTT::mul(A,tmp);
B.resize(2*K-1);
reverse(B.begin(),B.end());
for (ll i=0;i<=2*K-2;i++) B[i]=B[i]*ifac[i]%mod;
// vector<ll> B(2*K-1);
// for (int i=0;i<=2*K-2;i++){
// for (int j=i;j<=2*K-2;j++){
// add(B[i],A[j]*C(j,i)%mod);
// }
// }
for (int i=0;i<=2*K-2;i++) add(ans[i],B[i]);
add(ans[1],ksm(2,K));
for (int i=1;i<=2*K-2;i++) cout << ans[i] << " \n"[i==2*K-2];
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 20004kb
input:
2
output:
7 3
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 7ms
memory: 20640kb
input:
3
output:
15 14 6 1
result:
ok 4 tokens
Test #3:
score: 0
Accepted
time: 7ms
memory: 20324kb
input:
4
output:
31 43 36 19 6 1
result:
ok 6 tokens
Test #4:
score: 0
Accepted
time: 7ms
memory: 20176kb
input:
5
output:
63 110 132 114 70 30 8 1
result:
ok 8 tokens
Test #5:
score: 0
Accepted
time: 0ms
memory: 20188kb
input:
6
output:
127 255 384 448 400 272 136 47 10 1
result:
ok 10 tokens
Test #6:
score: 0
Accepted
time: 10ms
memory: 19724kb
input:
7
output:
255 558 978 1401 1610 1478 1066 589 240 68 12 1
result:
ok 12 tokens
Test #7:
score: 0
Accepted
time: 7ms
memory: 20348kb
input:
8
output:
511 1179 2292 3803 5250 5987 5576 4183 2482 1137 388 93 14 1
result:
ok 14 tokens
Test #8:
score: 0
Accepted
time: 11ms
memory: 20228kb
input:
9
output:
1023 2438 5088 9398 14896 20038 22632 21250 16406 10282 5144 2006 588 122 16 1
result:
ok 16 tokens
Test #9:
score: 0
Accepted
time: 7ms
memory: 21300kb
input:
10
output:
2047 4975 10896 21772 38360 58724 77184 86312 81448 64324 42112 22576 9744 3304 848 155 18 1
result:
ok 18 tokens
Test #10:
score: 0
Accepted
time: 7ms
memory: 20612kb
input:
11
output:
4095 10070 22782 48209 92140 156292 232068 298744 330926 313422 252186 171122 97008 45368 17200 5155 1176 192 20 1
result:
ok 20 tokens
Test #11:
score: -100
Runtime Error
input:
500000