QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#482840#9120. Huge Segment Treeucup-team2307TL 59ms15196kbC++203.8kb2024-07-17 22:31:542024-07-17 22:31:55

Judging History

你现在查看的是最新测评结果

  • [2024-07-17 22:31:55]
  • 评测
  • 测评结果:TL
  • 用时:59ms
  • 内存:15196kb
  • [2024-07-17 22:31:54]
  • 提交

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";

}

详细

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

output:


result: