约定记号popcnt(s)⁡\operatorname{popcnt(s)}popcnt(s)01 串sss中 1 的个数对于 01 串s,ts,ts,ts⊆t⟺sand⁡tss\subseteq t\Longleftrightarrow s\operatorname{and} tss⊆t⟺sandts题目给定正整数n≥5n\ge 5n≥5设所有长度为nnn的 01 串集合为UUU。设A⊆UA\subseteq UA⊆U如果AAA同时满足∀a∈A,popcnt⁡(a)4\forall a\in A,\operatorname{popcnt}(a)4∀a∈A,popcnt(a)4∀b∈{u∈U∣popcnt⁡(u)2},∃a∈A,b⊆a\forall b\in \{u\in U|\operatorname{popcnt}(u)2\},\exists a\in A,b\subseteq a∀b∈{u∈U∣popcnt(u)2},∃a∈A,b⊆a则称AAA具有性质PPP。Subtask 1当n8n8n8时若集合AAA具有性质PPP求AAA中元素个数最小值。我们尝试先证一个足够紧的下界然后构造出下界。注意到111个aaa最多覆盖C426C_4^26C42​6个bbb共C8228C_8^228C82​28种bbb。得到下界⌈28/6⌉5\lceil28/6\rceil5⌈28/6⌉5。这还不够紧。我们考虑维护一个初始为000的数组cntcntcnt。每当一个bbb被一个aaa覆盖就在两个为111位置上各111。每个bbb至少被覆盖一次最后cntcntcnt至少是(7,7,7,7,7,7,7,7)(7,7,7,7,7,7,7,7)(7,7,7,7,7,7,7,7)。注意到每个aaa都会在对应444个位置各333。因此最终cntcntcnt数组至少是(9,9,9,9,9,9,9,9)(9,9,9,9,9,9,9,9)(9,9,9,9,9,9,9,9)考虑总和得到下界⌈72/12⌉6\lceil72/12\rceil6⌈72/12⌉6。给出一组构造A0{11110000,00001111,11001100,11000011,00111100,00110011} A_0\left\{ \begin{aligned} \texttt{11110000},\\ \texttt{00001111},\\ \texttt{11001100},\\ \texttt{11000011},\\ \texttt{00111100},\\ \texttt{00110011} \end{aligned} \right\}A0​⎩⎨⎧​​11110000,00001111,11001100,11000011,00111100,00110011​⎭⎬⎫​可以看成用666个444阶完全图覆盖888阶完全图。可以看成是888个维度两两分组然后444个组两两连边。性质 1每个维度恰好被覆盖333次。由于cnti≥9cnt_i\ge 9cnti​≥9而总和727272cntcntcnt数组最终一定等于(9,9,9,9,9,9,9,9)(9,9,9,9,9,9,9,9)(9,9,9,9,9,9,9,9)因此每维恰好被覆盖三次。性质 2如果AAA满足性质PPP那么{not⁡a∣a∈A}\{\operatorname{not} a|a\in A\}{nota∣a∈A}满足性质PPP。我们考察每个bbb的两个1\texttt{1}1对应的两列必然形如111?1?0?0?0? \begin{aligned} \texttt{11}\\ \texttt{1?}\\ \texttt{1?}\\ \texttt{0?}\\ \texttt{0?}\\ \texttt{0?} \end{aligned}​111?1?0?0?0?​由于第二列恰好有333个1\texttt{1}1因此一定有一行为00\texttt{00}00取反后变成11\texttt{11}11。证毕。Subtask 2设σ\sigmaσ为一个1∼81\sim 81∼8的排列。对于任意长888的 01 串ss1s2…s8ss_1s_2\dots s_8ss1​s2​…s8​定义σ(s)sσ(1)sσ(2)…sσ(8)\sigma(s)s_{\sigma(1)}s_{\sigma(2)}\dots s_{\sigma(8)}σ(s)sσ(1)​sσ(2)​…sσ(8)​。我们定义等价关系≅\cong≅A1≅A2⟺∃σ,{σ(a)∣a∈A1}A2A_1\cong A_2\Longleftrightarrow \exists \sigma, \{\sigma(a)|a\in A_1\}A_2A1​≅A2​⟺∃σ,{σ(a)∣a∈A1​}A2​。不难验证自反性、对称性、传递性。找出所有等价类。写程序暴力枚举得到共333个等价类代表元素A0{11110000,00001111,11001100,11000011,00111100,00110011},A1{11110000,00001111,11001100,10100011,00111100,01010011},A2{11110000,11001100,11000011,00101011,00011110,00110101} A_0\left\{ \begin{aligned} \texttt{11110000},\\ \texttt{00001111},\\ \texttt{11001100},\\ \texttt{11000011},\\ \texttt{00111100},\\ \texttt{00110011} \end{aligned} \right\}, A_1\left\{ \begin{aligned} \texttt{11110000},\\ \texttt{00001111},\\ \texttt{11001100},\\ \texttt{10100011},\\ \texttt{00111100},\\ \texttt{01010011} \end{aligned} \right\}, A_2\left\{ \begin{aligned} \texttt{11110000},\\ \texttt{11001100},\\ \texttt{11000011},\\ \texttt{00101011},\\ \texttt{00011110},\\ \texttt{00110101} \end{aligned} \right\}A0​⎩⎨⎧​​11110000,00001111,11001100,11000011,00111100,00110011​⎭⎬⎫​,A1​⎩⎨⎧​​11110000,00001111,11001100,10100011,00111100,01010011​⎭⎬⎫​,A2​⎩⎨⎧​​11110000,11001100,11000011,00101011,00011110,00110101​⎭⎬⎫​