Project Euler 728 题解

标签：dots rang frac 题解 sum mid Project bmod 728

Problem 728 Circle of Coins

得到 Wallbreaker5th 的指导。

\(F\) 就是求这些环上区间（记为 \(A\)）的异或线性基大小。令 \(A'_i\gets A_i\oplus A_{i+1}\)。现在求 \(\lang A'\rang\) 的线性基。如果可能从全黑和全白间转换，那么 \(\dim \lang A'\rang=\lang A\rang-1\)，否则不 \(-1\)。这个转换的条件是 \(\frac k{(n,k)}\equiv 1 \pmod 2\)。

接下来观察到 \(A'_i,A'_{i+k\bmod n},A'_{i+2k\bmod n}\dots\) 覆盖到的集合对于不同等价类（\(i,i+k\dots\) 在一个等价类）无交。因此这些是独立的。

对于一个等价类去掉无法覆盖到的位置，等价类就形如 \(110000,011000,001100,\dots 100001\)，有 \(\frac n{(n,k)}\) 个向量。线性基的大小是：\(\frac n{(n,k)}-1\)，这是显然的。所以得到：

\[F(n,k)=2^{n-(n,k)+[\frac k{(n,k)}\equiv 1 \pmod 2]} \]

尝试计算答案。

\[S(N)=\sum _{n=1}^N 2^n\sum_{d\mid n} 2^{-d}\sum _{d\mid k}2^{[V_2(d)=V_2(k)]}\sum_{t\mid(\frac kd ,\frac nd)}\mu (t)\\ =\sum_{n=1}^N 2^n\sum_{d\mid n}2^{-d}\sum_{dt\mid n}\mu(t)\sum_{k=1}^{\frac n{dt}}2^{k\bmod 2} \]

记 \(F(n)=\sum_d 2^{-d}\mu(\frac nd),G(n)=\sum_{i\le n}2^{i\bmod 2},H=F*G\)，则：

\[S(N)=\sum_{n=1}^N 2^nH(n) \]

所以可以 \(O(n\log n)\) 解决。

标签：dots,rang,frac,题解,sum,mid,Project,bmod,728
From： https://www.cnblogs.com/british-union/p/18460294/PE_down_with_copyright