1 条题解

  • 0
    @ 2026-11-15 21:04:04

    题目分析

    碰到异或的题,一定要考虑很重要的一个性质,即 a⊕b⊕b=aa\oplus b\oplus b=a。

    也即,异或偶数次同一个数之后值不变。

    对于这道题,我们可以考虑 A0A_0(记作 aa)的每一个数对 AtA_t(记作 bb)的影响。

    假定 n=5n=5,对于 a1a_1,bib_i 异或 a1a_1 的次数如下表:

    • 第一次变换:[1,1,1,1,1][1,1,1,1,1];
    • 第二次变换:[1,2,3,4,5][1, 2, 3, 4, 5];
    • 第三次变换:[1,3,6,10,15][1, 3, 6, 10, 15];
    • 第四次变换:[1,4,10,20,35][1, 4, 10, 20, 35];
    • ……

    可以发现,该表从左下往右上看是组合数表。

    于是我们可以通过求组合数轻松得到每一个数对后面的数的影响次数。不过我们并不在意这个次数本身,而更关注这个次数的奇偶性。

    如果知道 Lucas 定理,那有个平凡的结论。

    O(1)O(1) 判断组合数 C(n,k)C(n, k) 的奇偶性:

    结论:若 n & k=kn\ \&\ k = k,则 C(n,k)C(n, k) 为奇数;否则为偶数。

    数学表达:

    $C(n, k) \text{ 是奇数 } \iff \text{在二进制下,} k \text{ 的每一位 1 都对应 } n \text{ 的该位也是 1。}$

    即,kk 的二进制表示是 nn 的二进制表示的子集。

    也可以不用Lucas 定理证明:

    1. 二进制位分析

    • 将 nn 和 kk 表示为二进制: $n = \sum_{i=0}^{r} n_i \cdot 2^i, \quad k = \sum_{i=0}^{r} k_i \cdot 2^i$ 其中 ni,ki∈{0,1}n_i, k_i \in \{0, 1\}。

    • 关键观察:

      • 若存在某一位 ii 使得 ni=0n_i = 0 但 ki=1k_i = 1,则 C(n,k)C(n, k) 为偶数。
      • 反之,若对所有 ii,ki=1  ⟹  ni=1k_i = 1 \implies n_i = 1,则 C(n,k)C(n, k) 为奇数。

    2. 归纳法证明

    • 基例:

      • 当 k=0k = 0 时,C(n,0)=1C(n, 0) = 1(奇数),且 n&0=0n \& 0 = 0 满足条件。
      • 当 k=nk = n 时,C(n,n)=1C(n, n) = 1(奇数),且 n&n=nn \& n = n 满足条件。
    • 递推关系: 组合数满足递推式: C(n,k)=C(n−1,k)+C(n−1,k−1) C(n, k) = C(n-1, k) + C(n-1, k-1) 根据归纳假设:

      • 若 C(n−1,k)C(n-1, k) 和 C(n−1,k−1)C(n-1, k-1) 均为奇数,则 (n−1)&k=k(n-1) \& k = k 且 (n−1)&(k−1)=k−1(n-1) \& (k-1) = k-1。
      • 此时可推出 n&k≠kn \& k \neq k,因此 C(n,k)C(n, k) 为偶数。

    依据此方法可以进行完整推导。

    至此本题完成解答,a2,a3,…,ana_2,a_3,\ldots,a_n 一概同理进行计算。

    E

    x=10A−19,y=109−19x=\frac{10^A-1}{9},y=\frac{10^9-1}{9}。

    先考虑计算 gcd⁡(x,y)\gcd(x,y)。

    有结论 gcd⁡(xn−1,xm−1)=xgcd⁡(n,m)−1 \gcd(x^n-1,x^m-1)=x^{\gcd(n,m)}-1 以下给出证明

    不妨假设 n≥mn \geq m,因为 gcd⁡(xm,xm−1)=1\gcd(x^m,x^m-1)=1 $\gcd(x^n-1,x^m-1)=\gcd(x^m(x^{n-m}-1)+x^m-1,x^m-1)=\gcd(x^m(x^{n-m}-1),x^m-1)$

    因此 gcd⁡(xn−1,xm−1)=gcd⁡((xn−m−1),xm−1) \gcd(x^n-1,x^m-1)=\gcd((x^{n-m}-1),x^m-1) 类比辗转相除法的过程,最终 gcd⁡(xn−1,xm−1)=xgcd⁡(n,m)−1 \gcd(x^n-1,x^m-1)=x^{\gcd(n,m)}-1 c=gcd⁡(A,B),ac=A,bc=Bc=\gcd(A,B),ac=A,bc=B

    答案为 $\frac{10^c-1}{9} \times \frac{10^{ac}-1}{10^c-1}\times \frac{10^{bc}-1}{10^c-1}$

    10ac−1=(10c−1)∑i=0a−110ic 10^{ac}-1=(10^c-1)\sum_{i=0}^{a-1} 10^{ic}

    可以利用快速幂直接求解,具体实现参考代码:

    • 1

    信息

    ID
    190
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    2
    已通过
    1
    上传者