数学

洛谷题库 P9118 [春季测试 2023] 幂次

我们有非常易于理解的暴力解法:直接对于 b=3,4b=3,4\cdots,求出所有可以当作底数的 aa,计算 aba^b 后放入数据结构/排序去重;特别处理 b=2b=2 的情况即可。在此不再赘述。

不过,我们注意到若有正整数 xx,满足 x>1,x=a0b0  (a0,b0N)x>1,x=a_0^{b_0}\ \ (a_0,b_0\in \mathbb N),且 a,bN,a0ab\forall a,b\in\mathbb N,a_0\neq a^b(即底数 a0a_0 不可再开根),那么 b,bb0,x=(a0b0/b)b\forall b,b\mid b_0,x=(a_0^{b_0/b})^b。这意味着假如不去重地暴力添加 nb\lfloor\sqrt[b]{n}\rfloor 到答案中,上文中 xx 将被算 {bb00(modb)}|\{b\mid b_0\equiv 0\pmod b\}| 次。

于是这就变成莫反的模板题了:记 g(b)g(b) 表示“能被 aba^b 表出的 xx 之数量”,f(b0)f(b_0) 表示“恰能被 x=a0b0x=a_0^{b_0} 表出,不可被 x=ab,b<b0x=a^b,b<b_0 表出的 xx 的数量”。易得 g(b)=bb0f(b0)g(b)=\sum_{b\mid b_0}f(b_0),故 f(b0)=b0bg(b)μ(b/b0)f(b_0)=\sum_{b_0\mid b}g(b)\mu(b/b_0)。显然,当 b>log2nb>\log_2 n 时仅有 a=1a=1 满足 abna^b\leq n,故我们只需计算 log2n\lfloor\log_2 n\rfloorbb,最后特判 a=1a=1。预处理出 μ\mu 的值,暴力求取反演式,复杂度为 O(log2n)\operatorname{O}(\log^2 n)


其实并不需要这么麻烦。我们根本不需要反演:根据 g(b)=bb0f(b0)g(b)=\sum_{b\mid b_0}f(b_0),假若 b0,b0>b,f(b0)\forall b_0,b_0>b,f(b_0) 都已经计算完成,那么我们直接得到 f(b)=g(b)bb0,b0>bf(b0)f(b)=g(b)-\sum_{b\mid b_0,b_0>b}f(b_0)。由 bb 从大往小计算即可,复杂度相同。

More
  • 2023年3月10日

本文将简单推导两种方式进行的离散傅里叶变换,用另种视角解释并优化算法。参考了 Seniorious yhx-12243 的 NTT 到底写了些什么(详细揭秘) 一文、OI Wiki 快速傅里叶变换 条目 和 rushcheyo 转置原理及其应用 讲稿。

离散傅里叶变换

我们计算数列 {an}\{a_n\} 的离散傅里叶变换 DFT(a,n)k=j=0n1aje2πinkj \newcommand\DFT{\operatorname{DFT}}\DFT(a,n)_k=\sum_{j=0}^{n-1}a_j\mathrm{e}^{\frac{-2\pi\mathrm{i}}{n}kj}

卷积定理循环卷积得到,我们对同样长为 nn 的数列 {bn}\{b_n\}DFT\DFT,并令数列 ck=DFT(a,n)kDFT(b,n)kc_k=\DFT(a,n)_k\DFT(b,n)_k,则有 IDFT(c,n)k=j+qk(modn)ajbq \newcommand\IDFT{\operatorname{IDFT}}\IDFT(c,n)_k=\sum_{j+q\equiv k\pmod n}a_jb_q

于是我们可以利用该原理实现常规意义下的数列卷积:有长为 nn 的数列 {an}\{a_n\},长 mm 的数列 {bm}\{b_m\},则将 a,ba,b 高位补 00,分别作 n+m1n+m-1 位的 DFT\DFT,点值相乘后 IDFT\IDFT 即可得到 ck=i+jk(modn+m1)aibj=i+j=k0i<n0j<maibjc_k=\sum_{i+j\equiv k\pmod{n+m-1}}a_ib_j=\sum_{\substack{i+j=k\\0\leq i<n\\0\leq j<m}}a_ib_j

为行文方便,下文采用 DFT(a,n)k=i=0n1aiωnik\DFT(a,n)_k=\sum_{i=0}^{n-1}a_i\omega_n^{ik} 的定义,其中 ωn=exp(2πi/n)\omega_n=\exp(2\pi\mathrm{i}/n),即 nn 阶单位根。 (更多…)

More
  • 2023年2月23日

近一个月来第一次赛时通过一道题。真是可喜可贺。

A – 单调

一开始以为与网络流相关;后来考虑 DP;结果是个贪心或者乱搞。

题意简述

给定长为 n  (n105)\newcommand\bigO{\operatorname{O}}n\ \ (n\leq 10^5) 的序列 ai,ai{1,2,3}\langle a_i\rangle,a_i\in\{1,2,3\}。匹配尽可能多的子序列,每个子序列均为 1,2,3\langle 1,2,3\rangle3,2,1\langle 3,2,1\rangle,且一个位置最多被一个子序列占用。求最大匹配数。 (更多…)

More
  • 2023年2月9日

洛谷题库 P6031 Cards 加强版

对于每一轮对局的 m!m! 种排列,对于编号为 aa 的牌,恒有 (m1)!(m-1)! 种是以牌 aa 为首的。因此一轮可以归为 mm 种情况,首张为王牌的概率为 1m\frac{1}{m}

这是某场模拟考试给出的部分分: SubtaskConstraintsPointsDependencies1n,m,k522k=123k5000101,24m1001015nk56k105101,2,37k5×106201,2,3,684117 \begin{array}{cccc} \text{Subtask}&\text{Constraints}&\text{Points}&\text{Dependencies}\\ \hline 1&n,m,k\leq 5&2&\\ 2&k=1&2&\\ 3&k\leq 5000&10&1,2\\ 4&m\leq 100&10&1\\ 5&n\leq k&5&\\ 6&k\leq 10^5&10&1,2,3\\ 7&k\leq 5\times 10^6&20&1,2,3,6\\ 8&&41&1\sim 7 \end{array} (更多…)

More
  • 2023年1月31日

AGC058D – Yet Another ABC String

A,B,C\mathtt{A,B,C} 换成 0,1,20,1,2。记 a,b,ca,b,c 是题面中 A,B,C\mathtt{A,B,C} 的数量,n=a+b+cn=a+b+c。我们称位置 ii 不合法,当且仅当 Si2+2Si1+1Si(mod3)S_{i-2}+2\equiv S_{i-1}+1\equiv S_i\pmod 3。将其视为两条边 (i2,i1),(i1,i)(i-2,i-1),(i-1,i),那么所有不合法的位置造成的连边将会形成若干条链。

考虑容斥。直接钦定指定数量的位置不合法,其方案是难以计算的。又因为容斥系数是 (1)c(-1)^ccc 为钦定的非法位置数量,那么将整个串分成若干个部分分别计算方案,带上容斥系数相乘后累加,结果不变。故而尝试从上文的链入手:易得对于固定长度的一条链,能够连成它的非法位置集合不变。设 f(l,0)f(l,0) 表示“大小为偶数,且能够连成长度恰为 ll 的链”的非法位置集合数量;f(l,1)f(l,1) 则是大小为奇数。染色方案位置集合方案是独立的;则设整个串按顺序被分成了链 (l1,l2,,ls)(l_1,l_2,\cdots,l_s)(此处的“链”长度均不小于 33),答案即为 (l1,,ls)染色方案数((l1,,ls))i=1s((1)f(li,1)+f(li,0))\sum_{(l_1,\cdots,l_s)}\operatorname{染色方案数}\left((l_1,\cdots,l_s)\right)\prod_{i=1}^s\left((-1)f(l_i,1)+f(l_i,0)\right) (更多…)

More
  • 2022年12月16日

NOIP+?准省选难度?已经到了能力的边缘么?

但有点奇怪的是,这三道题的思考方向全部正确,T1 甚至只差临门一脚了;可惜部分分给得不那么让人舒服。

另外,这种“为了卡常而卡常”的时间限制着实令人不适;尤其是当 CWOI 的评测机本身配置落后的情况下。不过这也反过来使得我重新开始关注更底层的常数优化。

简略题解

A – 种花

(更多…)

More
  • 2022年12月16日

这道破题拖了我整整一天。

代数推导

转化为容斥模型

题目所给限制可以表述为,aabb 均为单调不降的序列,长度相等(记为 kk),且 a1=0,ak=n,b1=0,bk=m,i[2,k],ai=ai1bi=bi1a_1=0,a_k=n,b_1=0,b_k=m,\nexists i\in[2,k],a_i=a_{i-1}\land b_i=b_{i-1}

考虑差分序列 ai=aiai1(i[2,k]){a_i}’=a_i-a_{i-1}\quad(i\in[2,k])bi{b_i}’ 同理,它与原序列形成双射。于是不存在 ai=bi=0{a_i}’={b_i}’=0 的差分序列合法。考虑 i=2kai=n\sum_{i=2}^{k}{a_i}’=n,也就是和为 nnk1k-1 元线性方程组的一组非负整数解;bb’ 同理。容易计算“钦定至少有 cc 个位置不合法”的方案数——利用容斥原理即可得到长为 kk 的合法序列对个数为 c=0k2(k1c)(n+(k1)1c(k1)1c)(m+(k1)1c(k1)1c)(1)c\sum_{c=0}^{k-2}\binom{k-1}{c}\binom{n+(k-1)-1-c}{(k-1)-1-c}\binom{m+(k-1)-1-c}{(k-1)-1-c}(-1)^c 答案累加上式结果 ×k\times k(更多…)

More
  • 2022年12月1日

AtCoder Regular Contest 148 D – mod M Game

鲁莽的尝试?

一个非常显然的 Bob 的必胜局面是:对于任意 x{0,1,,M1}x\in \{0,1,\cdots,M-1\},在这 2N2N 个数中的出现次数均为偶数。由此 Bob 可以选择与 Alice 上一轮选的相同的数而获胜。

那……其他局面就一定是 Alice 必胜么?

我们只依靠该结论交一份代码。不出意料,没有通过。不过它只错了两成的测点!看来大体方向是正确的。

正解

(更多…)

More
  • 2022年9月12日

一场相当有收获的比赛。比赛链接

A – 石老板举世无双

解法一

尝试观察规律。我们发现,在完成ss次操作以后,左端点的可能取值为xa+(2sx)b2s,x[1,2s]\dfrac{xa+(2^s-x)b}{2^s}, x \in [1, 2^s],右端点的可能取值为xa+(2sx)b2s,x[0,2s)\dfrac{xa+(2^s-x)b}{2^s}, x \in [0, 2^s)。假如现在我们达到最终状态,其l=(x+1)a+(2sx1)b2s,r=xa+(2sx)b2sl=\dfrac{(x+1)a+(2^s-x-1)b}{2^s}, r=\dfrac{xa+(2^s-x)b}{2^s}。那么,在xx的二进制表示中,如果从高到底pos\mathrm{pos}位为11,则在第pos\mathrm{pos}轮中,有check (mid) == 0,向右区间递归;否则向左区间递归。这是很容易解释的:若向右递归,则右端点不变。而在下一层,右端点表示中a,ba, b的所有系数乘22,所以体现为二进制位末尾添一个00。反之,就变成(x+(x+1))/2(x+(x+1))/2,在下一层中体现为2x+12x+1。如果其有popc(x)\operatorname{popc}(x)位为11,则到达该状态的概率为p0popc(x)p1spopc(x)p_0^{\operatorname{popc}(x)}p_1^{s-\operatorname{popc}(x)}

s=3s=3时的状态l=3a+5b8,r=2a+6b8l=\dfrac{3a+5b}{8}, r=\dfrac{2a+6b}{8}为例。22的三位二进制表示为0b010\text{0b010},则推断出在前三轮分别向右、左、右区间递归,到达其的概率为p0p12p_0p_1^2(更多…)

More
  • 2022年5月17日

考虑这个排列是怎样生成的。转述一下题意,可以发现,popcount(PiPi+1mod2n)=K\operatorname{popcount}(P_i \oplus P_{i+1 \mod {2^n}})=K,也即全集msk=2N1\text{msk}=2^N-1的一个大小为KK的子集。

由于这是一个环排列,我们不妨令P0=0P_0=0。这样一来,Pi=j=1iSj,Sj=KP_i=\operatorname{\bigoplus}\limits_{j=1}^{i}S_j, |S_j|=K。结合上文可知,这是一个相邻元素二进制位恰相差KK位的格雷码问题。有K=1K=1时,满足条件的SjS_j恰有NN个,也就是NN位格雷码。

考虑推广。我们发现,如果按照类格雷码的方式生成排列,则所有的SjS_j应构成异或空间,其大小应当恰为2N2^N,并且由线性空间知识可以得到,该线性空间的(基的大小)应当恰为NN。这恰好符合NN位格雷码的构造。因此,只要满足上述条件,就一定能够生成符合题意的排列。

可以证明,除了2K(K=NN>1)2\mid K \lor (K=N \land N>1)以外,总是有满足条件的线性空间生成的。

下述解法的时间复杂度O((NK)+2N)\operatorname{O}\left(\dbinom{N}{K}+2^N\right)(更多…)

More
  • 2022年4月11日