QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#67461 | #2578. Minimax 搜索 | alpha1022 | 100 ✓ | 323ms | 34980kb | C++14 | 5.3kb | 2022-12-10 16:11:07 | 2022-12-10 16:11:10 |
Judging History
answer
#include <cstdio>
#include <utility>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 2e5;
const int mod = 998244353;
const int inv = 499122177;
inline int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
return ret;
}
int n,L,R;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
struct Linear
{
int k,b;
inline Linear(int x = 1,int y = 0)
{
k = x,b = y;
}
inline Linear operator*(const Linear &o) const
{
return Linear((long long)k * o.k % mod,(b + (long long)k * o.b) % mod);
}
};
struct node
{
Linear f,g;
} seg[(N << 2) + 5];
void insert(int x,Linear f,Linear g,int p,int tl,int tr)
{
if(tl == tr)
{
seg[p].f = f,seg[p].g = g;
return ;
}
int mid = tl + tr >> 1;
x <= mid ? insert(x,f,g,ls,tl,mid) : insert(x,f,g,rs,mid + 1,tr);
seg[p].f = seg[ls].f * seg[rs].f,
seg[p].g = seg[ls].g * seg[rs].g;
}
inline pair<Linear,Linear> operator*(const pair<Linear,Linear> &a,const pair<Linear,Linear> &b)
{
return make_pair(a.first * b.first,a.second * b.second);
}
pair<Linear,Linear> query(int l,int r,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
return make_pair(seg[p].f,seg[p].g);
int mid = tl + tr >> 1;
pair<Linear,Linear> ret;
ret.first = Linear(),ret.second = Linear();
l <= mid && (ret = ret * query(l,r,ls,tl,mid),1);
r > mid && (ret = ret * query(l,r,rs,mid + 1,tr),1);
return ret;
}
struct Value
{
int v,cnt;
inline Value(int x = 0)
{
x ? (v = x,cnt = 0) : (v = 1,cnt = 1);
}
inline Value(int x,int y)
{
v = x,cnt = y;
}
inline Value operator*(const Value &o) const
{
return Value((long long)v * o.v % mod,cnt + o.cnt);
}
inline Value operator/(const Value &o) const
{
return Value((long long)v * fpow(o.v,mod - 2) % mod,cnt - o.cnt);
}
inline int val()
{
return cnt ? 0 : v;
}
} f[N + 5],g[N + 5];
int F[N + 5],G[N + 5];
int ans[N + 5];
int w[N + 5],W;
int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5],id[N + 5],ed[N + 5];
int leaf[N + 5],pw = inv;
void dfs1(int p)
{
sz[p] = 1;
if(!(dep[p] & 1))
w[p] = 0x3f3f3f3f;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
{
fa[to[i]] = p,dep[to[i]] = dep[p] + 1,dfs1(to[i]),sz[p] += sz[to[i]];
if(!son[p] || sz[son[p]] < sz[to[i]])
son[p] = to[i];
(dep[p] & 1) ? (w[p] = max(w[p],w[to[i]])) : (w[p] = min(w[p],w[to[i]]));
}
if(!son[p])
leaf[p] = 1,pw = 2LL * pw % mod,w[p] = p;
}
void dfs2(int p)
{
static int tot = 0;
id[p] = ++tot,F[p] = G[p] = 1,f[p] = g[p] = Value(1);
if(son[p])
top[son[p]] = top[p],dfs2(son[p]),ed[p] = ed[son[p]],
F[p] = (long long)F[p] * (1 - F[son[p]] + mod) % mod,
G[p] = (long long)G[p] * (1 - G[son[p]] + mod) % mod;
else
ed[p] = p,
F[p] = p > W,G[p] = p < W,
(dep[p] & 1) ? (F[p] = (1 - F[p] + mod) % mod) : (G[p] = (1 - G[p] + mod) % mod),
f[p] = Value(F[p]),g[p] = Value(G[p]);
for(register int i = first[p];i;i = pre[i])
if(!id[to[i]])
top[to[i]] = to[i],dfs2(to[i]),
F[p] = (long long)F[p] * (1 - F[to[i]] + mod) % mod,
G[p] = (long long)G[p] * (1 - G[to[i]] + mod) % mod,
f[p] = f[p] * Value((1 - F[to[i]] + mod) % mod),
g[p] = g[p] * Value((1 - G[to[i]] + mod) % mod);
}
void update(int x)
{
for(;x;x = fa[x])
{
insert(id[x],Linear((mod - f[x].val()) % mod,f[x].val()),Linear((mod - g[x].val()) % mod,g[x].val()),1,1,n),x = top[x];
pair<Linear,Linear> cur = query(id[x],id[ed[x]],1,1,n);
if(fa[x])
f[fa[x]] = f[fa[x]] / Value((1 - F[x] + mod) % mod),
g[fa[x]] = g[fa[x]] / Value((1 - G[x] + mod) % mod);
F[x] = cur.first.b,G[x] = cur.second.b;
if(fa[x])
f[fa[x]] = f[fa[x]] * Value((1 - F[x] + mod) % mod),
g[fa[x]] = g[fa[x]] * Value((1 - G[x] + mod) % mod);
}
}
int main()
{
scanf("%d%d%d",&n,&L,&R);
int u,v;
for(register int i = 2;i <= n;++i)
scanf("%d%d",&u,&v),add(u,v),add(v,u);
dep[1] = top[1] = 1,dfs1(1),W = w[1],dfs2(1);
for(register int i = 1;i <= n;++i)
insert(id[i],Linear((mod - f[i].val()) % mod,f[i].val()),Linear((mod - g[i].val()) % mod,g[i].val()),1,1,n);
for(register int i = 2;i < n;++i)
{
if(W - i + 1 > 0 && leaf[W - i + 1])
f[W - i + 1] = Value(inv),update(W - i + 1);
if(W + i - 1 <= n && leaf[W + i - 1])
g[W + i - 1] = Value(inv),update(W + i - 1);
ans[i] = (1 - (long long)F[1] * (1 - G[1] + mod) % mod + mod) * pw % mod;
}
ans[n] = pw - 1;
for(register int i = 1;i <= n;++i)
ans[i] = (ans[i] + pw) % mod;
for(register int i = n;i;--i)
ans[i] = (ans[i] - ans[i - 1] + mod) % mod;
for(register int i = L;i <= R;++i)
printf("%d%c",ans[i]," \n"[i == R]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 1ms
memory: 17284kb
input:
10 10 10 3 10 5 3 2 7 2 3 3 9 4 1 3 8 1 2 3 6
output:
27
result:
ok 1 number(s): "27"
Test #2:
score: 10
Accepted
time: 1ms
memory: 17280kb
input:
50 50 50 8 6 4 29 11 9 6 31 6 37 6 40 3 2 24 23 24 10 38 29 5 11 18 22 14 18 3 22 6 50 2 39 21 28 35 6 25 6 7 1 42 6 6 48 2 1 29 45 33 45 6 5 4 5 6 13 15 6 6 36 34 38 43 6 17 19 45 41 30 6 6 16 46 6 4 3 22 23 6 49 27 6 6 32 19 7 12 7 6 26 6 47 24 20 18 21 6 44
output:
268435455
result:
ok 1 number(s): "268435455"
Test #3:
score: 10
Accepted
time: 0ms
memory: 17136kb
input:
50 50 50 42 50 16 6 45 29 11 20 31 6 6 36 6 38 4 3 42 4 1 2 14 12 23 17 7 22 37 42 7 8 6 13 3 8 45 42 34 6 6 27 9 10 39 6 48 6 3 2 14 5 14 23 9 1 6 5 19 6 25 6 6 35 12 18 40 6 32 2 11 18 30 6 26 6 44 6 4 5 15 22 49 6 47 42 6 33 9 21 32 41 28 6 6 46 8 24 43 6
output:
94371839
result:
ok 1 number(s): "94371839"
Test #4:
score: 10
Accepted
time: 11ms
memory: 17612kb
input:
5000 5000 5000 3391 4162 1887 100 4806 2707 3384 4352 360 1060 4138 4214 1779 1103 2745 100 3191 2839 1054 815 100 3050 2140 821 2298 2006 4839 2857 4799 3088 4389 4821 100 1218 4538 2668 3948 100 437 759 4958 2943 100 2929 1016 100 4514 2626 3211 4464 4412 100 100 4290 3754 3464 317 139 3543 4038 1...
output:
290613167
result:
ok 1 number(s): "290613167"
Test #5:
score: 10
Accepted
time: 5ms
memory: 17480kb
input:
5000 5000 5000 4416 4742 3447 100 100 2139 2595 100 2730 100 2149 100 4132 4652 100 920 1171 93 4466 100 100 3056 1560 2330 980 100 4579 3690 4534 3402 3704 3658 100 4930 100 2544 4731 3198 346 2059 100 4645 261 2135 1496 2110 2796 4020 4152 3963 202 1395 100 4476 2664 100 292 100 100 1848 670 1093 ...
output:
672429329
result:
ok 1 number(s): "672429329"
Test #6:
score: 10
Accepted
time: 289ms
memory: 34976kb
input:
200000 64514 64564 166899 160082 60000 64526 33102 33103 85144 46777 2004 2005 60000 112699 54273 60449 186175 58944 38006 38007 57273 57274 60000 103775 60000 155227 141800 17902 101772 60000 29188 29187 199105 60000 77650 62888 197631 15538 60000 125137 13692 13693 17616 17617 81823 27527 121752 9...
output:
0 12553453 0 0 505398903 0 0 751821628 375910814 0 0 781055287 296549940 0 148274970 0 0 74137485 767217636 0 0 0 0 0 0 152582101 786828790 0 0 181998832 0 0 136499124 22749854 0 0 0 0 11374927 0 0 504809640 252404820 0 0 0 189303615 530672779 764458566 0 0
result:
ok 51 numbers
Test #7:
score: 10
Accepted
time: 279ms
memory: 34956kb
input:
200000 56869 56919 17597 17596 178411 181603 103240 63527 111797 38549 85990 117256 6726 6725 48441 48442 55270 177787 15041 15040 16877 16878 39504 185195 89404 38539 36826 36827 190491 60000 36740 36741 88429 60000 14220 14221 960 961 17416 17415 60000 170695 60000 94416 60000 186798 43121 63148 9...
output:
0 0 0 0 305716403 325990189 494053730 0 612498716 0 0 0 0 434831237 0 857391074 0 287842258 143921129 0 0 0 571082741 0 784663547 0 0 0 891453950 0 0 445726975 0 0 721985664 360992832 0 0 0 180496416 0 90248208 0 0 0 0 0 45124104 22562052 0 11281026
result:
ok 51 numbers
Test #8:
score: 10
Accepted
time: 311ms
memory: 34956kb
input:
200000 1 200000 184410 36878 13415 107366 68975 107143 106233 47847 16430 16429 191196 60000 46312 195146 41972 41971 20134 20133 164221 60000 194109 12132 60000 107792 60000 195701 7233 7232 35452 138684 41288 41287 13034 13035 43109 68299 178092 60000 29369 29368 137533 60000 60000 104755 97630 60...
output:
208949170 104474585 0 0 0 551359469 0 0 0 0 774801911 0 886523132 0 0 0 443261566 221630783 609937568 0 0 304968784 0 0 152484392 0 0 0 0 0 0 76242196 0 38121098 0 0 0 0 0 0 19060549 508652451 0 0 0 0 0 753448402 376724201 0 687484277 842864315 0 0 0 0 0 0 0 0 920554334 460277167 0 0 0 0 0 729260760...
result:
ok 200000 numbers
Test #9:
score: 10
Accepted
time: 305ms
memory: 34964kb
input:
200000 1 200000 60000 177996 29350 29351 60000 137658 60000 104670 60000 97458 6864 6863 87382 119869 82861 55561 60000 120168 10383 115806 15616 169696 112943 60000 54306 54307 60000 88032 181816 60000 60284 115176 178527 18228 85284 70160 69368 60000 82772 60000 4197 4198 101756 60000 60000 124381...
output:
7773226 0 0 0 3886613 0 501065483 0 749654918 0 0 374827459 0 0 0 31559506 670756153 834500253 0 0 0 0 0 0 916372303 957308328 0 0 0 478654164 239327082 119663541 0 558953947 169654372 0 0 0 0 0 0 693771964 346885982 0 173442991 585843672 0 292921836 0 0 0 0 0 0 0 146460918 0 73230459 0 0 0 53573740...
result:
ok 200000 numbers
Test #10:
score: 10
Accepted
time: 323ms
memory: 34980kb
input:
200000 1 200000 126513 83099 5686 5685 190737 50666 60000 175645 45263 45264 64096 60000 60000 88117 26201 26200 50979 50978 166070 43900 6611 72182 168284 60000 13093 69143 8233 120546 60000 125398 22942 22941 143390 144759 33279 128246 19415 19416 60000 74434 167203 60000 36776 191353 17351 17352 ...
output:
330236643 0 0 0 0 0 0 0 664240498 332120249 0 0 0 665182301 0 0 831713327 0 914978840 0 0 0 0 0 0 457489420 0 0 0 0 0 0 228744710 0 0 114372355 0 556308354 0 278154177 0 638199265 818221809 0 0 908233081 0 953238717 0 975741535 0 0 986992944 0 0 0 740244708 0 0 0 0 123374118 61687059 0 0 0 794948559...
result:
ok 200000 numbers
Extra Test:
score: 0
Extra Test Passed