QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#482840 | #9120. Huge Segment Tree | ucup-team2307 | TL | 59ms | 15196kb | C++20 | 3.8kb | 2024-07-17 22:31:54 | 2024-07-17 22:31:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back
typedef complex<double> C;
typedef vector<double> vd;
void fft(vector<C>& a) {
int n = sz(a), L = 31 - __builtin_clz(n);
static vector<complex<long double>> R(2, 1);
static vector<C> rt(2, 1); // (^ 10% faster if double)
for (static int k = 2; k < n; k *= 2) {
R.resize(n); rt.resize(n);
auto x = polar(1.0L, acos(-1.0L) / k);
rep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i/2] * x : R[i/2];
}
vi rev(n);
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
rep(i,0,n) 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) rep(j,0,k) {
// C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled) /// include-line
auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k]; /// exclude-line
C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]); /// exclude-line
a[i + j + k] = a[i + j] - z;
a[i + j] += z;
}
}
vd conv(const vd& a, const vd& b) {
if (a.empty() || b.empty()) return {};
vd res(sz(a) + sz(b) - 1);
int L = 32 - __builtin_clz(sz(res)), n = 1 << L;
vector<C> in(n), out(n);
copy(all(a), begin(in));
rep(i,0,sz(b)) in[i].imag(b[i]);
fft(in);
for (C& x : in) x *= x;
rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]);
fft(out);
rep(i,0,sz(res)) res[i] = imag(out[i]) / (4 * n);
return res;
}
typedef vector<ll> vl;
template<int M> vl convMod(const vl &a, const vl &b) {
if (a.empty() || b.empty()) return {};
vl res(sz(a) + sz(b) - 1);
int B=32-__builtin_clz(sz(res)), n=1<<B, cut=int(sqrt(M));
vector<C> L(n), R(n), outs(n), outl(n);
rep(i,0,sz(a)) L[i] = C((int)a[i] / cut, (int)a[i] % cut);
rep(i,0,sz(b)) R[i] = C((int)b[i] / cut, (int)b[i] % cut);
fft(L), fft(R);
rep(i,0,n) {
int j = -i & (n - 1);
outl[j] = (L[i] + conj(L[j])) * R[i] / (2.0 * n);
outs[j] = (L[i] - conj(L[j])) * R[i] / (2.0 * n) / 1i;
}
fft(outl), fft(outs);
rep(i,0,sz(res)) {
ll av = ll(real(outl[i])+.5), cv = ll(imag(outs[i])+.5);
ll bv = ll(imag(outl[i])+.5) + ll(real(outs[i])+.5);
res[i] = ((av % M * cut + bv) % M * cut + cv) % M;
}
return res;
}
const int mod = 998244353;
const int N = 500500;
int n;
vl a[N], b[N];
int bpow(int a, int b)
{
int r = 1;
while (b>0)
{
if (b&1)
r = r*a%mod;
a = a*a%mod;
b /= 2;
}
return r;
}
vl add(vl a, vl b)
{
vl c(max(a.size(), b.size()));
for (int i=0; i<int(a.size()); i++)
c[i] += a[i];
for (int i=0; i<int(b.size()); i++)
c[i] += b[i];
return c;
}
pair<vl, vl> solve(int l, int r)
{
if (l == r)
return {a[l], b[l]};
else
{
int m = (l+r)/2;
auto A = solve(l, m);
auto B = solve(m+1, r);
//(A1*x+A2)*B1+B2
return {convMod<mod>(A.fi, B.fi), add(convMod<mod>(A.se, B.fi), B.se)};
}
}
int fact[2*N];
int rfact[2*N];
int cnk(int n, int k)
{
return fact[n]*rfact[n-k]%mod*rfact[k]%mod;
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
fact[0] = rfact[0] = 1;
for (int i=1; i<N; i++)
fact[i] = fact[i-1]*i%mod, rfact[i] = bpow(fact[i], mod-2);
cin>>n;
for (int i=1; i<=n; i++)
{
a[i] = {1, 2, 1};
b[i] = {(bpow(2, i)+mod-2)%mod, (bpow(2, i-1)+mod-1)%mod };
}
auto ans = solve(1, n).se;
ans.resize(2*n-2);
for (int i=0; i<n; i++)
ans[i] = (ans[i] + 2*cnk(n, i+1))%mod;
ans[0]++;
for (int i : ans)
cout<<i<<" ";
cout<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 59ms
memory: 14672kb
input:
2
output:
7 3
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 59ms
memory: 15196kb
input:
3
output:
15 14 6 1
result:
ok 4 tokens
Test #3:
score: 0
Accepted
time: 59ms
memory: 14168kb
input:
4
output:
31 43 36 19 6 1
result:
ok 6 tokens
Test #4:
score: 0
Accepted
time: 55ms
memory: 14900kb
input:
5
output:
63 110 132 114 70 30 8 1
result:
ok 8 tokens
Test #5:
score: 0
Accepted
time: 55ms
memory: 14292kb
input:
6
output:
127 255 384 448 400 272 136 47 10 1
result:
ok 10 tokens
Test #6:
score: 0
Accepted
time: 59ms
memory: 14836kb
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: 59ms
memory: 14728kb
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: 55ms
memory: 14164kb
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: 59ms
memory: 15004kb
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: 51ms
memory: 13800kb
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
Time Limit Exceeded
input:
500000