猜数游戏
给出一个长度为
n
的序列和一个正整数
p。
设
n
中的元素组成一个集合
A。
二人交互：
- 一人选出一个
A
的一个非空子集
S
，
- 另一人选出一个极小的集合
S′⊆S，满足：∀ x∈S,∃ y∈S′,s.t.x=ym(modp),代价为
∣S′∣.
求代价的期望
×2n−1mod998244353。
这里只是形式化的定义，不保证清晰。
n≤5000
，p
保证是奇素数幂的形式。
分析
不难发现求期望就是在扯淡。
第一个人总共有
2n−1
种子集的选法，每种选法等概率。那么答案就是：每种选法的代价和×(2n−1)/(2n−1)
，题目要求求出每种选法的代价和。
既然不能枚举子集，一一确定答案，就考虑算每个元素的贡献。
考虑建图，如果一个元素
y,
ym(modp)
能够表示
x，那么就让
y
向
x
连边。
考虑一种合法的最小子集选择方案,一定是靠近入度为 0
的一些点。换句话说，一个点
x
能被选入极小集合
S′
当且仅当，没有别的选中的点可以走到这个点
x.即：这个点对答案有贡献。
考虑一个点的贡献次数，也就是有多少种选点的方案使得任意一个选中的点都不能走到这个点，设可以走到这个点的点有
cnt
个，那么这个点对答案的贡献就是
2n−cnt−1.
但是这个图是存在环的，也就是对于一个非空子集
S
来说，存在多个最优集合，从原根的角度考虑连边条件。
设
p
意义下的原根为
g，点
Ai≡gx(modp), Aj≡gy(modp)
，点
Ai
与
Aj
有边,需要满足：
∃m∈N,mx≡y(modφ(p))
由于：
“若
x
是常数，那么
kx模
m能遍历所有形如
k(x,m)的数”
—— ckw,Mys.C.K.
是会形成环的，所有形如
k(x,m)
的元素之间两两有边。准确的说，每一个强连通分量都是一个团。
但是不重要，考虑每个环都可以任意定向，就是即使
x,y
能相互表示，但是强制
x
表示
y
即可，这样对答案不会造成影响，相当于强制了一种最优集合的选择方式吧。
以上是对牌爷题解里 “显然” 的几点补充，建图方式参见牌爷题解，而且建图也没啥难的。
🔗 Source Hash:
f5bab8344acea45ac89164a139fe257e7c11865e658e9a0a0a7601585d172dd3
Build Logs
Build Log - Filtered
================================================
📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes
• All build status and error messages are kept intact
🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]
================================================
html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「杂题记录」「WC2020」猜数游戏.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「杂题记录」「WC2020」猜数游戏.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT:
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.
====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../867c1edc01.pdf.md', '-o', 'cache/867c1edc01.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT:
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] [makePDF] Temp dir:
.../[temp]
[INFO] [makePDF] Command line:
xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
("TEXINPUTS",".../[temp]
("TEXMFOUTPUT",".../[temp]
("SHELL","/bin/bash")
("PWD",".../[user]/projects/blog")
("HOME",".../[user]
("LANG","zh_CN.UTF-8")
("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
\PassOptionsToPackage{space}{xeCJK}
\documentclass[
]{article}
\usepackage{xcolor}
\usepackage[a4paper,margin=2cm]{geometry}
\usepackage{amsmath,amssymb}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering
\usepackage{iftex}
\ifPDFTeX
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
\usepackage{unicode-math} % this also loads fontspec
\defaultfontfeatures{Scale=MatchLowercase}
\defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
\usepackage{lmodern}
\ifPDFTeX\else
% xetex/luatex font selection
\setmainfont[]{Latin Modern Roman}
\ifXeTeX
\usepackage{xeCJK}
\setCJKmainfont[]{AR PL UKai CN}
\fi
\ifLuaTeX
\usepackage[]{luatexja-fontspec}
\setmainjfont[]{AR PL UKai CN}
\fi
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\usepackage{setspace}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
\KOMAoptions{parskip=half}}
\makeatother
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
% \usepackage{xeCJK}
% \setCJKmainfont{AR PL UKai CN}
% \usepackage{unicode-math}
\setmathfont{Latin Modern Math}
\usepackage{bookmark}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\urlstyle{same}
\hypersetup{
pdftitle={「杂题记录」「WC2020」猜数游戏},
pdfauthor={Jiayi Su (ShuYuMo)},
hidelinks,
pdfcreator={LaTeX via pandoc}}
\title{「杂题记录」「WC2020」猜数游戏}
\author{Jiayi Su (ShuYuMo)}
\date{2021-01-19 15:35:06}
\begin{document}
\maketitle
\setstretch{1.3}
\href{https://www.luogu.com.cn/problem/P6730}{猜数游戏}
给出一个长度为 \(n\) 的序列和一个正整数 \(p\)。
设 \(n\) 中的元素组成一个集合 \(A\)。
二人交互：
\begin{itemize}
\tightlist
\item
一人选出一个 \(A\) 的一个非空子集 \(S\) ，
\item
另一人选出一个极小的集合
\(S' \subseteq S\)，满足：\(\forall\ x \in S, \exists \ y \in S', s.t. x=y^m \pmod{p}\),代价为
\(|S'|\).
\end{itemize}
求代价的期望 \(\times 2^{n}-1 \mod 998244353\)。
这里只是形式化的定义，不保证清晰。
\(n\le 5000\) ，\(p\) 保证是奇素数幂的形式。
\subsection{分析}\label{ux5206ux6790}
不难发现求期望就是在扯淡。
第一个人总共有 \(2^n-1\)
种子集的选法，每种选法等概率。那么答案就是：\({每种选法的代价和} \times (2^n-1) / (2^n-1)\)
，题目要求求出每种选法的代价和。
既然不能枚举子集，一一确定答案，就考虑算每个元素的贡献。
考虑建图，如果一个元素 \(y\), \(y^m \pmod{p}\) 能够表示 \(x\)，那么就让
\(y\) 向 \(x\) 连边。
考虑一种合法的最小子集选择方案,一定是靠近入度为 0
的一些点。换句话说，一个点 \(x\) 能被选入极小集合 \(S'\)
当且仅当，没有别的选中的点可以走到这个点 \(x\).即：这个点对答案有贡献。
考虑一个点的贡献次数，也就是有多少种选点的方案使得任意一个选中的点都不能走到这个点，设可以走到这个点的点有
\(\operatorname{cnt}\) 个，那么这个点对答案的贡献就是
\(2^{n-\operatorname{cnt}-1}\).
但是这个图是存在环的，也就是对于一个非空子集 \(S\)
来说，存在多个最优集合，从原根的角度考虑连边条件。
设 \(p\) 意义下的原根为 \(g\)，点
\(A_i \equiv g^x \pmod{p},\ \ A_j \equiv g^y\pmod{p}\) ，点 \(A_i\) 与
\(A_j\) 有边,需要满足：
\[
\exists m\in \mathbb{N},mx \equiv y \pmod{\varphi(p)}
\]
由于：
\begin{quote}
“若 \(x\) 是常数，那么 \(kx\)模 \(m\)能遍历所有形如 \(k(x,m)\)的数” ——
ckw,Mys.C.K.
\end{quote}
是会形成环的，所有形如 \(k(x, m)\)
的元素之间两两有边。准确的说，每一个强连通分量都是一个团。
但是不重要，考虑每个环都可以任意定向，就是即使 \(x, y\)
能相互表示，但是强制 \(x\) 表示 \(y\)
即可，这样对答案不会造成影响，相当于强制了一种最优集合的选择方式吧。
以上是对牌爷题解里 “\textbf{显然}”
的几点补充，建图方式参见\href{https://www.luogu.com.cn/problem/solution/P6730}{牌爷题解}，而且建图也没啥难的。
\end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
restricted \write18 enabled.
entering extended mode
(.../input.tex
LaTeX2e <2023-11-01> patch level 1
L3 programming layer <2024-01-22>
(.../article.cls
Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
(.../[system]
(.../xcolor.sty
(.../color.cfg)
(.../xetex.def)
(.../[system]
(.../geometry.sty
(.../keyval.sty)
(.../ifvtex.sty
(.../iftex.sty)))
(.../amsmath.sty
For additional information on amsmath, use the `?' option.
(.../amstext.sty
(.../amsgen.sty))
(.../amsbsy.sty)
(.../amsopn.sty))
(.../amssymb.sty
(.../amsfonts.sty))
(.../unicode-math.sty
(.../expl3.sty
(.../l3backend-xetex.def))
(.../unicode-math-xetex.sty
(.../xparse.sty)
(.../l3keys2e.sty)
(.../fontspec.sty
(.../fontspec-xetex.sty
(.../fontenc.sty)
(.../fontspec.cfg)))
(.../fix-cm.sty
(.../ts1enc.def))
(.../unicode-math-table.tex)))
(.../lmodern.sty)
(.../xeCJK.sty
(.../ctexhook.sty)
(.../xtemplate.sty)
(.../xeCJK.cfg))
(.../upquote.sty
(.../textcomp.sty))
(.../microtype.sty
(.../etoolbox.sty)
(.../microtype-xetex.def)
(.../microtype.cfg))
(.../setspace.sty)
(.../parskip.sty
(.../kvoptions.sty
(.../ltxcmds.sty)
(.../kvsetkeys.sty)))
(.../bookmark.sty
(.../hyperref.sty
(.../kvdefinekeys.sty)
(.../pdfescape.sty
(.../pdftexcmds.sty
(.../infwarerr.sty)))
(.../hycolor.sty)
(.../auxhook.sty)
(.../nameref.sty
(.../refcount.sty)
(.../gettitlestring.sty))
(.../pd1enc.def)
(.../intcalc.sty)
(.../puenc.def)
(.../url.sty)
(.../bitset.sty
(.../bigintcalc.sty))
(.../atbegshi-ltx.sty))
(.../hxetex.def
(.../stringenc.sty)
(.../rerunfilecheck.sty
(.../atveryend-ltx.sty)
(.../uniquecounter.sty)))
(.../bkm-dvipdfm.def))
(.../xurl.sty)
No file input.aux.
*geometry* driver: auto-detecting
*geometry* detected driver: xetex
(.../mt-LatinModernRoman.cfg)
Package hyperref Warning: Rerun to get /PageLabels entry.
(.../omllmm.fd)
(.../umsa.fd)
(.../mt-msa.cfg)
(.../umsb.fd)
(.../mt-msb.cfg)
LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
(Font) using `TU/ARPLUKaiCN(0)/m/n' instead on input line 100.
Missing character: There is no 每 (U+6BCF) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
Missing character: There is no 种 (U+79CD) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
Missing character: There is no 选 (U+9009) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
Missing character: There is no 法 (U+6CD5) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
Missing character: There is no 的 (U+7684) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
Missing character: There is no 代 (U+4EE3) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
Missing character: There is no 价 (U+4EF7) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
Missing character: There is no 和 (U+548C) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
[1] [2] (.../input.aux)
LaTeX Font Warning: Some font shapes were not available, defaults substituted.
LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
)
Output written on .../input.pdf (2 pages).
Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
Package hyperref Warning: Rerun to get /PageLabels entry.
LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
restricted \write18 enabled.
entering extended mode
(.../input.tex
LaTeX2e <2023-11-01> patch level 1
L3 programming layer <2024-01-22>
(.../article.cls
Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
(.../[system]
(.../xcolor.sty
(.../color.cfg)
(.../xetex.def)
(.../[system]
(.../geometry.sty
(.../keyval.sty)
(.../ifvtex.sty
(.../iftex.sty)))
(.../amsmath.sty
For additional information on amsmath, use the `?' option.
(.../amstext.sty
(.../amsgen.sty))
(.../amsbsy.sty)
(.../amsopn.sty))
(.../amssymb.sty
(.../amsfonts.sty))
(.../unicode-math.sty
(.../expl3.sty
(.../l3backend-xetex.def))
(.../unicode-math-xetex.sty
(.../xparse.sty)
(.../l3keys2e.sty)
(.../fontspec.sty
(.../fontspec-xetex.sty
(.../fontenc.sty)
(.../fontspec.cfg)))
(.../fix-cm.sty
(.../ts1enc.def))
(.../unicode-math-table.tex)))
(.../lmodern.sty)
(.../xeCJK.sty
(.../ctexhook.sty)
(.../xtemplate.sty)
(.../xeCJK.cfg))
(.../upquote.sty
(.../textcomp.sty))
(.../microtype.sty
(.../etoolbox.sty)
(.../microtype-xetex.def)
(.../microtype.cfg))
(.../setspace.sty)
(.../parskip.sty
(.../kvoptions.sty
(.../ltxcmds.sty)
(.../kvsetkeys.sty)))
(.../bookmark.sty
(.../hyperref.sty
(.../kvdefinekeys.sty)
(.../pdfescape.sty
(.../pdftexcmds.sty
(.../infwarerr.sty)))
(.../hycolor.sty)
(.../auxhook.sty)
(.../nameref.sty
(.../refcount.sty)
(.../gettitlestring.sty))
(.../pd1enc.def)
(.../intcalc.sty)
(.../puenc.def)
(.../url.sty)
(.../bitset.sty
(.../bigintcalc.sty))
(.../atbegshi-ltx.sty))
(.../hxetex.def
(.../stringenc.sty)
(.../rerunfilecheck.sty
(.../atveryend-ltx.sty)
(.../uniquecounter.sty)))
(.../bkm-dvipdfm.def))
(.../xurl.sty)
(.../input.aux)
*geometry* driver: auto-detecting
*geometry* detected driver: xetex
(.../mt-LatinModernRoman.cfg)
(.../omllmm.fd)
(.../umsa.fd)
(.../mt-msa.cfg)
(.../umsb.fd)
(.../mt-msb.cfg)
LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
(Font) using `TU/ARPLUKaiCN(0)/m/n' instead on input line 100.
Missing character: There is no 每 (U+6BCF) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
Missing character: There is no 种 (U+79CD) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
Missing character: There is no 选 (U+9009) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
Missing character: There is no 法 (U+6CD5) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
Missing character: There is no 的 (U+7684) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
Missing character: There is no 代 (U+4EE3) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
Missing character: There is no 价 (U+4EF7) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
Missing character: There is no 和 (U+548C) in font LatinModernMath-Regular/OT:sc
ript=math;language=dflt;!
[1] [2] (.../input.aux)
LaTeX Font Warning: Some font shapes were not available, defaults substituted.
)
Output written on .../input.pdf (2 pages).
Transcript written on .../input.log.
[WARNING] Missing character: There is no 每 (U+6BCF) (U+6BCF) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 种 (U+79CD) (U+79CD) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 选 (U+9009) (U+9009) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 法 (U+6CD5) (U+6CD5) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 的 (U+7684) (U+7684) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 代 (U+4EE3) (U+4EE3) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 价 (U+4EF7) (U+4EF7) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no 和 (U+548C) (U+548C) in font LatinModernMath-Regular/OT:sc