https://wiki.cvbbacm.com/ 2026-04-30T07:20:09+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-05-21T17:43:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics&rev=1590054180&do=diff 理论 理论部分太长惹。。晚点填 题目 1、模板: poj2154 Color 给正$n$边形染$m$种颜色，问有多少种染色方案。 对任意正$n$边形有如下$2n$阶二面体群： $G = \{\rho^0,..,\rho^{n-1},\tau^1,\ldots,\tau^n\}$ 然后通过$\text{Burnside定理}$:$$N(G,\mathcal{C})=\frac 1{|G|}\sum_{f\in G}|\mathcal{C}(f)|$$求解 对于旋转产生的置换$\rho^i$产生的贡献$|\mathcal{C}(\rho^i)|$，奇偶都一样，要通过$gcd$$|\mathcal{C}(\rho^i)|=m^{gcd(n,i)}$$$ \begin{cases} & \sum |\mathcal{C}(\tau^i)| & = & n\times m^{n/2+1} & (n\%2==1) \\ & \sum |\mathcal{C}(\tau^i)| & = & \frac n2\times m^{n/2}+\frac n2\times m^{n/2+… text/html 2020-05-18T23:23:33+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:wangzai_milk:wzx27:pe&rev=1589815413&do=diff 题目连接:<https://projecteuler.net/problem=401> 题意 定义函数$sigma2:x \mapsto x所有因数的平方和$，求$\sum_{i=1}^{n}sigma2(i)$对$m$取模，其中$n=10^{15},m=10^9$。 题解 考虑每个因数$k$的贡献$k^2$，那么 $$ 原式=\sum_{i=1}^{n} \left \lfloor \frac{n}{i} \right \rfloor \times i^2 = \sum_{i=1}^{\left \lfloor \frac{n}{\sqrt n+1} \right \rfloor } (\left \lfloor \frac{n}{i} \right \rfloor \times i^2) \; +\; \sum_{i=1}^{\sqrt n} (f( \left \lfloor \frac{n}{i} \right \rfloor ) - f( \left \lfloor \frac{n}{i+1} \right \rfloor )) $$ 其中$f(k)=\sum_{i…