【Gym-102331】300iq Contest 2

好,开始补坑。

这场打得实在有点问题,中途我去体测,廷廷又要提前回家,实际打的时间都没多少。。。

两年后我居然开始补这套题了。

[A Apollonian Network]

[B Bitwise Xor]

solution

题意:有 $n$ 个数,给出一个数 $x$,询问满足任意两个数异或和大于等于 $x$ 的子序列的数量。

数据范围:$1\leq n\leq 300000,0\leq x,a_i\leq 2^{60}-1$

做法:一个子序列内添加进去一个新的数需要满足这个子序列的其他数和这个数的异或和都大于等于 $x$,即只要找到最小的异或和大于等于 $x$ 即可。于是每次添加一个数的时候在线段树上查找一下即可,复杂度 $O(60n)$。

[C Counting Cactus]

solution

题意:给定一个无向简单图,求它的生成仙人掌的数量模 $998244353$。

做法:考虑每次添加一个点进入图中,然后新增加的仙人掌数量。维护当点集为 $S$ 的时候的仙人掌数量,注意到新添加的那个点,要么是在一个环上,要么是单独连接的。单独连接是容易计算的,因为我们可以通过前面的计算得知前 $n$ 个点的所有子集的仙人掌数的 $\mathrm{GF}$,那么这个就等价于新的点连若干个点,而以这若干个点为根的子仙人掌不重合,不重合的条件可以用欧拉变换( $\exp$ )得到。而在环上的情况,我们以新的点为起点,绕一圈这个环,则这个的 $\mathrm{GF}$ 就是这环上若干个点不在环上的子仙人掌 $\mathrm{GF}$ 的积,再略微化简一下可以只枚举与新的点直接相连的那个点,然后其余剩下的是个 $\mathrm{GF}$ 的和。而这些东西用上 $\mathrm{FWT}$ 再分析一下复杂度就是 $O(2^nn^3)$,具体可看代码。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//2021.12.19 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=19;
namespace MAIN{
int E[N];
int inv[N];
inline void addvec(res *a,const res *b,const res &l){
for(res i=0;i<=l;i++)add(a[i],b[i]);
}
inline void decvec(res *a,const res *b,const res &l){
for(res i=0;i<=l;i++)add(a[i],kcz-b[i]);
}
inline void Exp(const res *a,res *b,const res &l){
static int u[N];
for(res i=1;i<=l;i++)u[i]=mul(i,a[i]);
b[0]=1;
for(res i=1;i<=l;i++){
RG LL ret=u[i];
for(res j=1;j<i;j++)ret+=(LL)u[j]*b[i-j];
b[i]=int(ret%kcz*inv[i]%kcz);
}
}
typedef int mat[1<<N][N],(*pmat)[N];
inline void FWT(pmat F,const res &l,const res &typ){
for(res i=0,len=1,L=1<<l;i<l;i++,len<<=1)
for(res j=0;j<L;j+=len<<1)
for(res k=j;k<j+len;k++){
if(typ==1)addvec(F[k+len],F[k],l);
else decvec(F[k+len],F[k],l);
}
}
mat cyc[N];
mat G[N];
int ans[1<<N];
inline void reset(pmat a,const res &l){
for(res i=0,L=1<<l;i<L;i++)memset(a[i],0,(l+1)<<2);
}
inline void copy(pmat a,const pmat &b,const res &l){
for(res i=0,L=1<<l;i<L;i++)memcpy(a[i],b[i],(l+1)<<2);
}
mat F,eF;
inline void solve(const res &n){
for(res i=0;i<n;i++){
pmat f=G[i];
reset(f,n);
for(res S=0,L=1<<n;S<L;S++)f[S][pc(S)]=S>>i&1?ans[S]:0;
FWT(f,n,1);
if(E[n]>>i&1)copy(cyc[i],f,n);
else reset(cyc[i],n);
}
reset(F,n);
for(res i=0,L=1<<n;i<L;i++){
for(res j=1;j<=n;j++){
for(res v=0;v<n;v++){
res *g=G[v][i],*c=cyc[v][i],ret=0;
for(res S=E[v];S;S&=S-1)add(ret,cyc[ctz(S)][i][j]);
for(res k=1;k+j<=n;k++)add(c[j+k],mul(ret,g[k]));
}
}
for(res S=E[n];S;S&=S-1)addvec(F[i],cyc[ctz(S)][i],n),addvec(F[i],G[ctz(S)][i],n);
#define half(x) (((x)>>1)+(-((x)&1)&inv[2]))
for(res j=0;j<=n;j++)F[i][j]=half(F[i][j]);
Exp(F[i],eF[i],n);
}
FWT(eF,n,-1);
for(res S=0,nS=1<<n,L=nS;S<L;S++,nS++)ans[nS]=eF[S][pc(S)];
}
int n,m;
inline void MAIN(){
inv[0]=inv[1]=1,n=read(),m=read();
for(res i=2;i<=n;i++)inv[i]=mul(inv[kcz%i],kcz-kcz/i);
for(res i=1;i<=m;i++){
res u=read()-1,v=read()-1;
E[u]|=1<<v,E[v]|=1<<u;
}
ans[1]=1;
for(res i=1;i<n;i++)solve(i);
printf("%d\n",ans[(1<<n)-1]);
}
}

[D Determinant]

[E Easy Win]

[F Fast Spanning Tree]

[G Grammarly]

solution

题意:给出一个长度为 $n$ 的串 $s$,若 $a,b\in s\ and\ b\in a\ and\ |b|+1=|a|$,则由 $a$ 连一条边向 $b$,求从 $s$ 出发的简单路径数,答案模 $99824453$。

数据范围:$1\leq n\leq 300000$。

做法:如果没有重复的字符,则答案显然为 $2^n-1$。于是对极长重复字符段组合数容斥一下即可,复杂度是 $O(n)$。

[H Honorable Mention]

[I Interactive Vertex]

solution

题意:给出一棵 $n$ 个点的树,其中有一个关键点 $A$。交互,每次你可以给出类似 $?\ k\ x\ y_1\ y_2\ …\ y_k$ 的询问,返回 $dis(A,x)\geq min(dis(A,y_i))$ 的 bool 值,要求交互次数不超过 $4\lceil log_2n\rceil$。

数据范围:$1\leq n\leq 200000$。

做法:首先对于每个连通块,你可以暴力判断关键点在哪个连通块。这里的判断即是每次拿走一半大小的子树判一判,如果在这一半里,就递归进去继续做,如果不在,那么就继续做。如果都不在,说明当前枚举的连通块的根就是答案。然而这样做交互次数和时间复杂度都有点小炸,那你就点分优化一下这个过程,保证了交互次数和复杂度。

[J Jiry Matchings]

[K K-pop Strings]

solution

题意:定义一个串重复两次后的串为 $tandem$。给出一个 $k$,定义一个长度为$n$的串合法当且仅当其中最长 $tandem$ 长度小于 $n-k$,求长度为 $n$ 的合法串的数量。

数据范围:$1\leq n\leq 100,0\leq k\leq 16$。

做法:神奇的暴力题。

我们先预处理出所有合法的长度及其位置,是否合法利用并查集维护相同的串的连通性即可。然后呢,直接暴搜所有合法长度和位置,一旦搜出不合法串就退出,并查集带撤销即可。这样复杂度显然错的,然后你 rand_shuffle 一样所有合法长度及其位置,就能过了。好玄学啊。