「比赛总结」洛谷 10 月赛

📅 Last Updated: 2020-10-19
📊 Word Count: 606
⏱️ Estimated Reading Time: 4 minutes
📄 PDF 📝 Source

洛谷 2020 年 10 月 月赛 有两道期望题分数拿的还不错 .

Pro. A

给出一张无向图，从任意一点出发，规定每条边只能经过一次（正向 反向都算一次）。求最长的合法路径长度。

考虑每次经过一个点 x ，就会使点 x 的可用度数减 2 。如果走到一个合法度数为 0 的点，那么路径终止。要求是求最长路径长度，那么显然应该以此减少每个点的可用度数。每个点的初始度数为 n - 1。特殊考虑有偶数个点的完全图，初始度数为奇数，那么最后一次仍然可以走一步到达一个点。

n−12×n+[n mod 2 = 0] \frac{n-1}{2} \times n + [n\ \texttt{mod}\ 2\ =\ 0]

code

# python3 
T = int(input())
for i in range(T):
    now = int(input())
    print((now - 1) // 2 * now + ((now & 1) ^ 1))

Pro. B

总共有 nn 条带 「圣盾」的「胖头鱼」和 mm 条不带圣盾的胖头鱼，每次等概率对一条存活的胖头鱼造成「剧毒」伤害。 现在 Amazing John 想知道，期望造成多少次伤害可以杀死全部胖头鱼？
答案对 998244353998244353 取模。

  • 「圣盾」：当拥有圣盾的胖头鱼受到伤害时，免疫这条鱼所受到的本次伤害。免疫伤害后，圣盾被破坏。
  • 「胖头鱼」：在一条胖头鱼的圣盾被破坏后，给予其他所有没有死亡且没有圣盾的胖头鱼圣盾。
  • 「剧毒」：立即杀死没有圣盾的胖头鱼。

本题共有 2020 个数据点，数据点从 11 到 2020 编号。对于一个子任务，只有通过其中所有数据点才能获得该子任务的分数。

子任务 数据点 数据范围 分数
11 1∼31\sim3 n,m≤5×103n,m≤5×10^3 1515
22 4∼54\sim5 n≤106，m=0n≤10^6，m=0 1010
33 6∼106\sim10 n,m≤106n,m≤10^6 2525
44 11∼1411\sim14 n≤1014，m=0n≤10^{14}，m=0 2020
55 15∼2015\sim20 n≤1014，m≤106n≤10^{14}，m≤10^6 3030

为描述方便，使用 0 代表无圣盾的胖头鱼， 1 代表有圣盾的胖头鱼。即，局面可以使用一串 0-1 串表示。

考虑一个局面：有 n 个 0 ， m 个 1（000000000000011111111）。 - 如果一次操作作用在 0 上，那么会使其死亡 局面变成有（n - 1）个 0， m 个 1。其概率为 nn+m\frac{n}{n + m}。 - 如果一次操作作用在 1 上，那么会使其死亡 局面变成有 1 个 0， (n + m) 个 1。其概率为 mn+m\frac{m}{n + m}。 设: 一个局面的期望结束操作步数函数为 f(n,m)f(n, m) 。特殊的，设 有 n 个 1 的局面的期望奇数操作步数函数g⁡(n)=f⁡(0,n)\operatorname{g}(n) = \operatorname{f}(0, n)

易知： f⁡(n,m)=1+nn+m×f⁡(n−1,m)+mn+m×[ g⁡(n+m)−1 ]\operatorname{f}(n, m) = 1 + \frac{n}{n + m}\times\operatorname{f}(n - 1, m) + \frac{m}{n + m}\times[\ \operatorname{g}(n + m) - 1\ ]

g⁡(n)=2+1n×g⁡(n−1)+n−1n×[ g⁡(n)−1 ]\operatorname{g}(n) = 2 + \frac{1}{n}\times\operatorname{g}(n - 1) + \frac{n - 1}{n}\times[\ \operatorname{g}(n) - 1\ ]

化简得

g⁡(n)=n×(n+1)2+n\operatorname{g}(n) = \frac{n \times (n + 1)}{2} + n

最后答案就是 f⁡(n,m)\operatorname{f}(n, m), 递归求解即可。

code

#define int long long
int inv(int x) { x %= MOD; int a = x, b = MOD - 2, ans = 1; while(b) { if(b & 1) ans = (ans *1ll* a) % MOD; a = (a *1ll* a) % MOD; b >>= 1; } return ans; }
int f(int n) { n %= MOD; return ((n) *1ll* (n + 1) % MOD * inv(2) % MOD + n) % MOD; }
int g(int n) { return (f(n) - 1 + MOD )% MOD; }
int doit(int n, int m){
    if(m <= 0) return f(n);
    return (((n % MOD) * inv(n + m) % MOD) * g(n + m) % MOD + (m *1ll* inv(n + m) % MOD) * doit(n, m - 1) % MOD  + 1)% MOD;
}
signed main(){
    int n = read(), m = read();
    printf("%lld\n", doit(n, m));
    return 0;
}

Pro. C

给出一个长度为 nn 的序列（保证Ai∈[1,2]A_i \in [1, 2]）， mm 次操作。 - 询问操作格式为 A s，表示询问是否有一种散步方案使得美丽值之和为 ss。 - 修改操作格式为 C i val，表示将第 ii 朵花的美丽值改成 val(val=1val(val=1 或 2)2)。

对于每一个询问，若有合法的方案，输出这个方案的左右端点位置（多种方案时输出左端点最小的方案），否则输出 none。

Subtask 1⁡ (20pts)\operatorname{Subtask\ 1}\ (20pts)：对于数据点 1∼51\sim 5，满足 1≤n,m≤10001\leq n,m\leq 1000。

Subtask 2⁡ (30pts)\operatorname{Subtask\ 2}\ (30pts)：对于数据点 6∼106\sim 10，满足 1≤n,m≤2.5×1051\leq n,m\leq 2.5\times 10^5。

Subtask 3⁡ (50pts)\operatorname{Subtask\ 3}\ (50pts)：对于数据点 11∼1511\sim 15，满足 1≤n,m≤2×1061\leq n,m\leq 2\times 10^6。

对于 100%100\% 的数据，有 1≤n,m≤2×106,0≤s≤231−11\leq n,m\leq 2\times 10^6,0\leq s\leq 2^{31}-1。每次修改操作时 i∈[1,n],val∈{1,2}i\in[1,n],val\in\{1,2\}。

对于所有数据点，时间限制 2000ms⁡2000\operatorname{ms}，空间限制 256MB⁡256\operatorname{MB}。

留坑！

Pro. D

有一个无限大的棋盘来下马棋。

有一个马最开始在 (0,0)(0,0)，它的每一步可以走一个 a×ba\times b 的矩形（ 即能够从(x,y)(x,y)到达 (x±a,y±b)(x\pm a,y\pm b) 或 (x±b,y±a)(x\pm b,y\pm a) ）。

若马通过上述移动方式可以到达棋盘中任意一个点，那么 p(a,b)=1p(a,b)=1，否则 p(a,b)=0p(a,b)=0。

现在 Amazing John 给你 TT 组询问，每组询问他会给出一个正整数 nn，他想知道

(∑a=1n∑b=1np(a,b)) mod  264\left ( \sum_{a=1}^n\sum_{b=1}^np(a,b) \right )\bmod\ 2^{64}

的值。

本题开启Subtask

子任务 数据点 数据范围 分数
11 11 n≤10,T≤5n\leq 10,T\leq5 55
22 2∼52\sim 5 n≤3000,T≤5n\leq 3000,T\leq5 1515
33 6∼106\sim 10 n≤105,T≤5n\leq 10^5,T\leq 5 1515
44 11∼1511\sim 15 n≤107,T≤5n\leq 10^7,T\leq5 1515
55 16∼1816\sim 18 n≤109,T≤5n\leq10^9,T\leq 5 1515
66 19∼2519\sim 25 n×T≤1011,T≤5n\times T\leq 10^{11},T\leq 5 3535

注 1：对于 n×T≥5∗1010n\times T\geq 5*10^{10} 的数据点，时限为 4s ，其余均为 2.5s 。且对于所有数据点，空间限制为 500MB 。

注 2：输出答案  mod  264\bmod\ 2^{64} 即对 64位无符号整数 自然溢出。

通过打表可知：其中的函数 p⁡\operatorname{p}， p⁡(a,b)=[a⊥b] [(a−b) mod⁡ 2 = 1]\operatorname{p}(a, b) = [a \perp b]\ [(a - b) \ \operatorname{mod} \ 2\ = \ 1]

考虑每个数字的贡献，因为 aa bb 的差为奇数 所以aa bb 的奇偶性不同。 - 对于偶数 xx 贡献为 φ(x)\varphi(x) - 对于奇数 xx 贡献为 φ(x)2\frac{\varphi(x)}{2}，即 与 xx 互质的偶数个数。

答案就是： 2×[ ∑i=1n[i mod⁡ 2 =1]φ(i)2+∑i=1n[i mod⁡ 2 =0]φ(i) ]2\times[\ \sum_{i=1}^{n}\limits{[i\ \operatorname{mod} \ 2\ = 1]\frac{\varphi(i)}{2}} + \sum_{i=1}^{n}\limits{[i\ \operatorname{mod} \ 2\ = 0]\varphi(i)}\ ]

50pts 不知道怎么杜教筛降复杂度。

code

// 线性筛 phi
#define ULL unsigned long long 
void doit(){
    int n = read();
    ULL ans = 0;
    for(int i = 1; i <= n; i++){
        ans += (i & 1) ? (phi[i] >> 1) : phi[i];
    }
    printf("%llu\n", ans << 1);
}
int main(){ 
    int T = read(); euler(1e7 + 2); while(T--) doit(); return 0; 
}

📚 Version History

Source Code Change History
v1
🔗 Source Hash: 3b70424b6144b0d46dfc76dd0de85cee3048e1624ee332037d1b1a71fb571b97
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_「比赛总结」洛谷-10-月赛.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「比赛总结」洛谷-10-月赛.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.../978d0c1fd3.pdf.md', '-o', 'cache/978d0c1fd3.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 RawInline (Format "html") ""
[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
  \usepackage{color}
  \usepackage{fancyvrb}
  \newcommand{\VerbBar}{|}
  \newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
  \DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
  % Add ',fontsize=\small' for more characters per line
  \newenvironment{Shaded}{}{}
  \newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
  \newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
  \newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\BuiltInTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{#1}}
  \newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
  \newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
  \newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
  \newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
  \newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
  \newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
  \newcommand{\ExtensionTok}[1]{#1}
  \newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
  \newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
  \newcommand{\ImportTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{\textbf{#1}}}
  \newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
  \newcommand{\NormalTok}[1]{#1}
  \newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
  \newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
  \newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
  \newcommand{\RegionMarkerTok}[1]{#1}
  \newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
  \newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
  \newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
  \newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
  \usepackage{longtable,booktabs,array}
  \usepackage{calc} % for calculating minipage widths
  % Correct order of tables after \paragraph or \subparagraph
  \usepackage{etoolbox}
  \makeatletter
  \patchcmd\longtable{\par}{\if@noskipsec\mbox{}\fi\par}{}{}
  \makeatother
  % Allow footnotes in longtable head/foot
  \IfFileExists{footnotehyper.sty}{\usepackage{footnotehyper}}{\usepackage{footnote}}
  \makesavenoteenv{longtable}
  \ifLuaTeX
    \usepackage{luacolor}
    \usepackage[soul]{lua-ul}
  \else
    \usepackage{soul}
    \ifXeTeX
      % soul's \st doesn't work for CJK:
      \usepackage{xeCJKfntef}
      \renewcommand{\st}[1]{\sout{#1}}
    \fi
  \fi
  \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={「比赛总结」洛谷 10 月赛},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「比赛总结」洛谷 10 月赛}
  \author{Jiayi Su (ShuYuMo)}
  \date{2020-10-19 15:35:06}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  洛谷 2020 年 10 月 月赛 有两道期望题分数拿的还不错 .
  
  \section{Pro. A}\label{pro.-a}
  
  给出一张无向图，从任意一点出发，规定每条边只能经过一次（正向
  反向都算一次）。求最长的合法路径长度。
  
  考虑每次经过一个点 x ，就会使点 x 的可用度数减 2
  。如果走到一个合法度数为 0
  的点，那么路径终止。要求是求最长路径长度，那么显然应该以此减少每个点的可用度数。每个点的初始度数为
  n -
  1。特殊考虑有偶数个点的完全图，初始度数为奇数，那么最后一次仍然可以走一步到达一个点。
  
  \[
  \frac{n-1}{2} \times n + [n\ \texttt{mod}\ 2\ =\ 0]
  \]
  
  \subsection{code}\label{code}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \CommentTok{\# python3 }
  \NormalTok{T }\OperatorTok{=} \BuiltInTok{int}\NormalTok{(}\BuiltInTok{input}\NormalTok{())}
  \ControlFlowTok{for}\NormalTok{ i }\KeywordTok{in} \BuiltInTok{range}\NormalTok{(T):}
  \NormalTok{    now }\OperatorTok{=} \BuiltInTok{int}\NormalTok{(}\BuiltInTok{input}\NormalTok{())}
      \BuiltInTok{print}\NormalTok{((now }\OperatorTok{{-}} \DecValTok{1}\NormalTok{) }\OperatorTok{//} \DecValTok{2} \OperatorTok{*}\NormalTok{ now }\OperatorTok{+}\NormalTok{ ((now }\OperatorTok{\&} \DecValTok{1}\NormalTok{) }\OperatorTok{\^{}} \DecValTok{1}\NormalTok{))}
  \end{Highlighting}
  \end{Shaded}
  
  \section{Pro. B}\label{pro.-b}
  
  总共有 \(n\) 条带 「圣盾」的「胖头鱼」和 \(m\)
  条不带圣盾的胖头鱼，每次等概率对一条存活的胖头鱼造成「剧毒」伤害。 现在
  Amazing John 想知道，期望造成多少次伤害可以杀死全部胖头鱼？\\
  答案对 \(998244353\) 取模。
  
  \begin{itemize}
  \tightlist
  \item
    「圣盾」：当拥有圣盾的胖头鱼受到伤害时，免疫这条鱼所受到的本次伤害。免疫伤害后，圣盾被破坏。
  \item
    「胖头鱼」：在一条胖头鱼的圣盾被破坏后，给予其他所有没有死亡且没有圣盾的胖头鱼圣盾。
  \item
    「剧毒」：立即杀死没有圣盾的胖头鱼。
  \end{itemize}
  
  本题共有 \(20\) 个数据点，数据点从 \(1\) 到 \(20\)
  编号。对于一个子任务，只有通过其中所有数据点才能获得该子任务的分数。
  
  \begin{longtable}[]{@{}llll@{}}
  \toprule\noalign{}
  子任务 & 数据点 & 数据范围 & 分数 \\
  \midrule\noalign{}
  \endhead
  \bottomrule\noalign{}
  \endlastfoot
  \(1\) & \(1\sim3\) & \(n,m≤5×10^3\) & \(15\) \\
  \(2\) & \(4\sim5\) & \(n≤10^6，m=0\) & \(10\) \\
  \(3\) & \(6\sim10\) & \(n,m≤10^6\) & \(25\) \\
  \(4\) & \(11\sim14\) & \(n≤10^{14}，m=0\) & \(20\) \\
  \(5\) & \(15\sim20\) & \(n≤10^{14}，m≤10^6\) & \(30\) \\
  \end{longtable}
  
  为描述方便，使用 0 代表无圣盾的胖头鱼， 1
  代表有圣盾的胖头鱼。即，局面可以使用一串 0-1 串表示。
  
  考虑一个局面：有 n 个 0 ， m 个 1（\texttt{000000000000011111111}）。 -
  如果一次操作作用在 0 上，那么会使其死亡 局面变成有（n - 1）个 0， m 个
  1。其概率为 \(\frac{n}{n + m}\)。 - 如果一次操作作用在 1
  上，那么会使其死亡 局面变成有 1 个 0， (n + m) 个 1。其概率为
  \(\frac{m}{n + m}\)。 设: 一个局面的期望结束操作步数函数为 \(f(n, m)\)
  。特殊的，设 有 n 个 1
  的局面的期望奇数操作步数函数\(\operatorname{g}(n) = \operatorname{f}(0, n)\)
  
  易知：
  \[\operatorname{f}(n, m) = 1 + \frac{n}{n + m}\times\operatorname{f}(n - 1, m) + \frac{m}{n + m}\times[\ \operatorname{g}(n + m) - 1\ ]\]
  
  \[\operatorname{g}(n) = 2 + \frac{1}{n}\times\operatorname{g}(n - 1) + \frac{n - 1}{n}\times[\ \operatorname{g}(n) - 1\ ]\]
  
  化简得
  
  \[\operatorname{g}(n) = \frac{n \times (n + 1)}{2} + n\]
  
  最后答案就是 \(\operatorname{f}(n, m)\), 递归求解即可。
  
  \subsection{code}\label{code-1}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \PreprocessorTok{\#define int }\DataTypeTok{long}\PreprocessorTok{ }\DataTypeTok{long}
  \DataTypeTok{int}\NormalTok{ inv}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ x}\OperatorTok{)} \OperatorTok{\{}\NormalTok{ x }\OperatorTok{\%=}\NormalTok{ MOD}\OperatorTok{;} \DataTypeTok{int}\NormalTok{ a }\OperatorTok{=}\NormalTok{ x}\OperatorTok{,}\NormalTok{ b }\OperatorTok{=}\NormalTok{ MOD }\OperatorTok{{-}} \DecValTok{2}\OperatorTok{,}\NormalTok{ ans }\OperatorTok{=} \DecValTok{1}\OperatorTok{;} \ControlFlowTok{while}\OperatorTok{(}\NormalTok{b}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{if}\OperatorTok{(}\NormalTok{b }\OperatorTok{\&} \DecValTok{1}\OperatorTok{)}\NormalTok{ ans }\OperatorTok{=} \OperatorTok{(}\NormalTok{ans }\OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ a}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}\NormalTok{ a }\OperatorTok{=} \OperatorTok{(}\NormalTok{a }\OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ a}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;}\NormalTok{ b }\OperatorTok{\textgreater{}\textgreater{}=} \DecValTok{1}\OperatorTok{;} \OperatorTok{\}} \ControlFlowTok{return}\NormalTok{ ans}\OperatorTok{;} \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ f}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ n}\OperatorTok{)} \OperatorTok{\{}\NormalTok{ n }\OperatorTok{\%=}\NormalTok{ MOD}\OperatorTok{;} \ControlFlowTok{return} \OperatorTok{((}\NormalTok{n}\OperatorTok{)} \OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*} \OperatorTok{(}\NormalTok{n }\OperatorTok{+} \DecValTok{1}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD }\OperatorTok{*}\NormalTok{ inv}\OperatorTok{(}\DecValTok{2}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD }\OperatorTok{+}\NormalTok{ n}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{;} \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ g}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ n}\OperatorTok{)} \OperatorTok{\{} \ControlFlowTok{return} \OperatorTok{(}\NormalTok{f}\OperatorTok{(}\NormalTok{n}\OperatorTok{)} \OperatorTok{{-}} \DecValTok{1} \OperatorTok{+}\NormalTok{ MOD }\OperatorTok{)\%}\NormalTok{ MOD}\OperatorTok{;} \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ doit}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ n}\OperatorTok{,} \DataTypeTok{int}\NormalTok{ m}\OperatorTok{)\{}
      \ControlFlowTok{if}\OperatorTok{(}\NormalTok{m }\OperatorTok{\textless{}=} \DecValTok{0}\OperatorTok{)} \ControlFlowTok{return}\NormalTok{ f}\OperatorTok{(}\NormalTok{n}\OperatorTok{);}
      \ControlFlowTok{return} \OperatorTok{(((}\NormalTok{n }\OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{)} \OperatorTok{*}\NormalTok{ inv}\OperatorTok{(}\NormalTok{n }\OperatorTok{+}\NormalTok{ m}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{)} \OperatorTok{*}\NormalTok{ g}\OperatorTok{(}\NormalTok{n }\OperatorTok{+}\NormalTok{ m}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD }\OperatorTok{+} \OperatorTok{(}\NormalTok{m }\OperatorTok{*}\DecValTok{1}\BuiltInTok{ll}\OperatorTok{*}\NormalTok{ inv}\OperatorTok{(}\NormalTok{n }\OperatorTok{+}\NormalTok{ m}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD}\OperatorTok{)} \OperatorTok{*}\NormalTok{ doit}\OperatorTok{(}\NormalTok{n}\OperatorTok{,}\NormalTok{ m }\OperatorTok{{-}} \DecValTok{1}\OperatorTok{)} \OperatorTok{\%}\NormalTok{ MOD  }\OperatorTok{+} \DecValTok{1}\OperatorTok{)\%}\NormalTok{ MOD}\OperatorTok{;}
  \OperatorTok{\}}
  \DataTypeTok{signed}\NormalTok{ main}\OperatorTok{()\{}
      \DataTypeTok{int}\NormalTok{ n }\OperatorTok{=}\NormalTok{ read}\OperatorTok{(),}\NormalTok{ m }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
  \NormalTok{    printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%lld\textbackslash{}n}\StringTok{"}\OperatorTok{,}\NormalTok{ doit}\OperatorTok{(}\NormalTok{n}\OperatorTok{,}\NormalTok{ m}\OperatorTok{));}
      \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;}
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  \section{Pro. C}\label{pro.-c}
  
  给出一个长度为 \(n\) 的序列（保证\(A_i \in [1, 2]\)）， \(m\) 次操作。 -
  询问操作格式为 \texttt{A\ s}，表示询问是否有一种散步方案使得美丽值之和为
  \(s\)。 - 修改操作格式为 \texttt{C\ i\ val}，表示将第 \(i\)
  朵花的美丽值改成 \(val(val=1\) 或 \(2)\)。
  
  对于每一个询问，若有合法的方案，输出这个方案的左右端点位置（多种方案时输出左端点最小的方案），否则输出
  \texttt{none}。
  
  \(\operatorname{Subtask\ 1}\ (20pts)\)：对于数据点 \(1\sim 5\)，满足
  \(1\leq n,m\leq 1000\)。
  
  \(\operatorname{Subtask\ 2}\ (30pts)\)：对于数据点 \(6\sim 10\)，满足
  \(1\leq n,m\leq 2.5\times 10^5\)。
  
  \(\operatorname{Subtask\ 3}\ (50pts)\)：对于数据点 \(11\sim 15\)，满足
  \(1\leq n,m\leq 2\times 10^6\)。
  
  对于 \(100\%\) 的数据，有
  \(1\leq n,m\leq 2\times 10^6,0\leq s\leq 2^{31}-1\)。每次修改操作时
  \(i\in[1,n],val\in\{1,2\}\)。
  
  对于所有数据点，时间限制 \(2000\operatorname{ms}\)，空间限制
  \(256\operatorname{MB}\)。
  
  留坑！
  
  \section{Pro. D}\label{pro.-d}
  
  有一个无限大的棋盘来下马棋。
  
  有一个马最开始在 \((0,0)\)，它的每一步可以走一个 \(a\times b\) 的矩形（
  即能够从\((x,y)\)到达 \((x\pm a,y\pm b)\) 或 \((x\pm b,y\pm a)\) ）。
  
  若马通过上述移动方式可以到达棋盘中任意一个点，那么 \(p(a,b)=1\)，否则
  \(p(a,b)=0\)。
  
  现在 Amazing John 给你 \(T\) 组询问，每组询问他会给出一个正整数
  \(n\)，他想知道
  
  \[\left ( \sum_{a=1}^n\sum_{b=1}^np(a,b) \right )\bmod\ 2^{64}\]
  
  的值。
  
  \textbf{本题开启Subtask}
  
  \begin{longtable}[]{@{}llll@{}}
  \toprule\noalign{}
  子任务 & 数据点 & 数据范围 & 分数 \\
  \midrule\noalign{}
  \endhead
  \bottomrule\noalign{}
  \endlastfoot
  \(1\) & \(1\) & \(n\leq 10,T\leq5\) & \(5\) \\
  \(2\) & \(2\sim 5\) & \(n\leq 3000,T\leq5\) & \(15\) \\
  \(3\) & \(6\sim 10\) & \(n\leq 10^5,T\leq 5\) & \(15\) \\
  \(4\) & \(11\sim 15\) & \(n\leq 10^7,T\leq5\) & \(15\) \\
  \(5\) & \(16\sim 18\) & \(n\leq10^9,T\leq 5\) & \(15\) \\
  \(6\) & \(19\sim 25\) & \(n\times T\leq 10^{11},T\leq 5\) & \(35\) \\
  \end{longtable}
  
  注 1：对于 \(n\times T\geq 5*10^{10}\) 的数据点，时限为 \textbf{4s}
  ，其余均为 \textbf{2.5s} 。且对于所有数据点，空间限制为 \textbf{500MB}
  。
  
  注 2：输出答案 \(\bmod\ 2^{64}\) 即对 \textbf{64位无符号整数} 自然溢出。
  
  \st{通过打表可知：}其中的函数 \(\operatorname{p}\)，
  \(\operatorname{p}(a, b) = [a \perp b]\ [(a - b) \ \operatorname{mod} \ 2\ = \ 1]\)
  
  考虑每个数字的贡献，因为 \(a\) \(b\) 的差为奇数 所以\(a\) \(b\)
  的奇偶性不同。 - 对于偶数 \(x\) 贡献为 \(\varphi(x)\) - 对于奇数 \(x\)
  贡献为 \(\frac{\varphi(x)}{2}\)，即 与 \(x\) 互质的偶数个数。
  
  答案就是：
  \[2\times[\ \sum_{i=1}^{n}\limits{[i\ \operatorname{mod} \ 2\ = 1]\frac{\varphi(i)}{2}} + \sum_{i=1}^{n}\limits{[i\ \operatorname{mod} \ 2\ = 0]\varphi(i)}\ ]\]
  
  \textbf{50pts} 不知道怎么杜教筛降复杂度。
  
  \section{code}\label{code-2}
  
  \begin{Shaded}
  \begin{Highlighting}[]
  \CommentTok{// 线性筛 phi}
  \PreprocessorTok{\#define ULL }\DataTypeTok{unsigned}\PreprocessorTok{ }\DataTypeTok{long}\PreprocessorTok{ }\DataTypeTok{long}\PreprocessorTok{ }
  \DataTypeTok{void}\NormalTok{ doit}\OperatorTok{()\{}
      \DataTypeTok{int}\NormalTok{ n }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}
  \NormalTok{    ULL ans }\OperatorTok{=} \DecValTok{0}\OperatorTok{;}
      \ControlFlowTok{for}\OperatorTok{(}\DataTypeTok{int}\NormalTok{ i }\OperatorTok{=} \DecValTok{1}\OperatorTok{;}\NormalTok{ i }\OperatorTok{\textless{}=}\NormalTok{ n}\OperatorTok{;}\NormalTok{ i}\OperatorTok{++)\{}
  \NormalTok{        ans }\OperatorTok{+=} \OperatorTok{(}\NormalTok{i }\OperatorTok{\&} \DecValTok{1}\OperatorTok{)} \OperatorTok{?} \OperatorTok{(}\NormalTok{phi}\OperatorTok{[}\NormalTok{i}\OperatorTok{]} \OperatorTok{\textgreater{}\textgreater{}} \DecValTok{1}\OperatorTok{)} \OperatorTok{:}\NormalTok{ phi}\OperatorTok{[}\NormalTok{i}\OperatorTok{];}
      \OperatorTok{\}}
  \NormalTok{    printf}\OperatorTok{(}\StringTok{"}\SpecialCharTok{\%llu\textbackslash{}n}\StringTok{"}\OperatorTok{,}\NormalTok{ ans }\OperatorTok{\textless{}\textless{}} \DecValTok{1}\OperatorTok{);}
  \OperatorTok{\}}
  \DataTypeTok{int}\NormalTok{ main}\OperatorTok{()\{} 
      \DataTypeTok{int}\NormalTok{ T }\OperatorTok{=}\NormalTok{ read}\OperatorTok{();}\NormalTok{ euler}\OperatorTok{(}\FloatTok{1e7} \OperatorTok{+} \DecValTok{2}\OperatorTok{);} \ControlFlowTok{while}\OperatorTok{(}\NormalTok{T}\OperatorTok{{-}{-})}\NormalTok{ doit}\OperatorTok{();} \ControlFlowTok{return} \DecValTok{0}\OperatorTok{;} 
  \OperatorTok{\}}
  \end{Highlighting}
  \end{Shaded}
  
  
  \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)))
  (.../fancyvrb.sty)
  (.../longtable.sty)
  (.../booktabs.sty)
  (.../array.sty)
  (.../calc.sty)
  (.../footnotehyper.sty)
  (.../soul.sty
  (.../soul-ori.sty)
  (.../infwarerr.sty)
  (.../etexcmds.sty))
  (.../xeCJKfntef.sty
  (.../ulem.sty))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.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)
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  Missing character: There is no ， (U+FF0C) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no ， (U+FF0C) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no ， (U+FF0C) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  
  Package longtable Warning: Column widths have changed
  (longtable)                in table 1 on input line 196.
  
  [1] [2]
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 285.
  
  
  Package longtable Warning: Column widths have changed
  (longtable)                in table 2 on input line 300.
  
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/m/it' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 324.
  
  [3]
  
  Package longtable Warning: Table widths have changed. Rerun LaTeX.
  
  [4] (.../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 (4 pages).
  Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
  Package hyperref Warning: Rerun to get /PageLabels entry.
  Package longtable Warning: Table widths have changed. Rerun LaTeX.
  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)))
  (.../fancyvrb.sty)
  (.../longtable.sty)
  (.../booktabs.sty)
  (.../array.sty)
  (.../calc.sty)
  (.../footnotehyper.sty)
  (.../soul.sty
  (.../soul-ori.sty)
  (.../infwarerr.sty)
  (.../etexcmds.sty))
  (.../xeCJKfntef.sty
  (.../ulem.sty))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.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)
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  Missing character: There is no ， (U+FF0C) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no ， (U+FF0C) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  Missing character: There is no ， (U+FF0C) in font LatinModernMath-Regular/OT:sc
  ript=math;language=dflt;!
  [1] [2]
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 285.
  
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/m/it' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 324.
  
  [3] [4] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (4 pages).
  Transcript written on .../input.log.
[WARNING] Missing character: There is no ， (U+FF0C) (U+FF0C) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no ， (U+FF0C) (U+FF0C) in font LatinModernMath-Regular/OT:sc
[WARNING] Missing character: There is no ， (U+FF0C) (U+FF0C) in font LatinModernMath-Regular/OT:sc