专栏文章

题解：B4372 [GXPC-S 2025] 异或之力 / xor

YYeaMiko
B4372题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miohwoov
此快照首次捕获于
2025/12/02 19:29
3 个月前
此快照最后确认于
2025/12/02 19:29
3 个月前
查看原文

题解 B4372 [GXPC-S 2025] 异或之力 / xor

题目要求：

对于给定的nn，我们考虑所有长度为nn的0101字符串（即数字00到2n−12^n-1）。对于每个数字CC（当C>1C>1时），我们需要计算其异或之力，即所有分解C=A+BC=A+B（AA,BB为正整数）中，AA异或BB的最大值PP与最小值QQ的差(P−QP-Q）。然后，我们要找出所有CC中最大的异或之力，并对109+710^9+7取模。

关键结论：

1. 最小值Q：
  • 当CC为偶数时，可以分解为A=C/2A=C/2, B=C/2B=C/2，此时AA异或B=0B=0，所以最小值Q=0Q=0。
  • 当CC为奇数时，设kk为CC的最低位的连续1的个数（从最低位开始连续的11的个数），例如C=11C=11（二进制10111011），最低位连续两个11，则k=2k=2，此时最小值Q=2k−1Q=2^k-1（即3）。实际上，我们可以取A=(C+2k−1)/2A=(C+2^k-1)/2, B=(C−2k+1)/2B=(C-2^k+1)/2，则AA异或B=2k−1B=2^k-1。而且这是最小的异或值。
2. 最大值P：
当CC为奇数时，最大值PP等于CC。因为可以分解为A=1A=1,B=C−1 B=C-1，则AA异或B=1(C−1)=CB = 1^(C-1) = C（因为C−1C-1是偶数，最低位为00，而11的最低位为1，所以异或后最低位为1，而高位与C−1C-1相同，而C−1C-1的高位与CC相同，所以整个就是CC）。 当CC为偶数时，情况较复杂：    - Plan a. 如果CC是22的幂（即C=2kC=2^k），那么最大值P=C−2P=C-2。因为分解时，AA和BB不能同时为2(k−1)2^(k-1)（因为那样异或为00，不是最大），最大异或值可以通过分解为A=2k−2A=2^k-2,B=2 B=2（注意A+B=2kA+B=2^k）得到，此时AA异或B=(2k−2)2=(2k)−2B=(2^k-2)^2 = (2^k) - 2（因为2k−22^k-2的二进制是k−1k-1位全11后面一个00，而22是11后面k−1k-1个00，异或后得到kk位中最高位为00，其余位为11，即2k−1−12^k-1-1实际上，我们计算：例如k=3k=3，C=8C=8，分解为66和22：66的二进制110110，22的二进制010010，异或得到100100即44，而8−2=68-2=6，不对,再分解为33和55：33的二进制011011，55的二进制101101，异或为110110，即66，而6=8−26=8-2。所以确实为C−2C-2。   Plan b. 如果CC是44的倍数（即CC modmod 4==04 ==0）且不是22的幂，那么最大值P=C−2P=C-2。例如C=12（1100）C=12（1100），分解为44和88：4(0100)和8(1000)异或得到12(1100)？不对，应该是1100。但实际上，分解为6和6：异或为0；分解为5和7：5(0101)和7(0111)异或为2（0010）；分解为4和8：4(0100)和8(1000)异或为1100（12），所以最大值是12。所以这里之前的结论可能有误。 重新审视最大值P（对于偶数C）：   事实上，对于任意C，我们总是可以取A=1, B=C-1，则A异或B = 1^(C-1)。
当C为偶数时，C-1为奇数，且C-1的二进制表示就是C的二进制表示最低位0变为1，其他位不变。
那么1^(C-1)的结果：因为1只在最低位有1，而C-1的最低位是1，所以异或后最低位为0，而次低位？
实际上，1的二进制是...0001，C-1的二进制是...????1，异或后相当于将C-1的最低位置0，然后加上1（因为异或后最低位0，而原本最低位是1，相当于减1再置最低位为0？）这并不直接等于C。
 实际上，我们有一个 重要性质：
对于任意CC，有A+B=CA+B=C，则 A⊕B=A⊕A⊕B = A⊕ (C−A)(C-A) =C−2 = C - 2 (( AA & (( C−AC-A )) ))。
 因此，A⊕BA⊕B的最大值就是C减去两倍的某个值的最小值，即当A和C-A的二进制位没有重叠的1时，A⊕B=C。     而什么时候没有重叠？
 当A和C-A的二进制位没有同时为1的位，即A&C=0。
   所以，最大值P等于满足A&C=0（即A是C的二进制表示中1对应的子集）的A中，A⊕(C-A)的最大值？
   实际上，A⊕(C-A) = A+(C-A)（因为A和C-A没有公共1，所以异或等于加和），即C。    但是，只有当存在这样的分解时，最大值P才等于C。    然而，对于偶数C，如果C的二进制表示中最低位是0，那么A和B必须同时是奇数或偶数，但要求A和C-A没有公共1，这要求C的每一位至多在一个数中出现，即C的二进制位没有连续的1？    实际上，当C是2的幂时，我们无法将C分解成两个没有公共1的数（因为C只有一个1，那么A必须包含这个1，而B=0，但B不能为0，所以不行）。    因此，对于2的幂，我们无法达到C。
   经过查阅和思考，我们有以下结论：  
  • 最大值P：我们可以通过分解A=(C-1), B=1，得到异或值为(C-1)^1。对于偶数C，C-1是奇数，1是奇数，但这样得到的值并不一定是最大的。
实际上，最大值P等于小于C的最大的2^k-1形式的数？这个结论也不对。
 根据题目中的例子：C=6（110）时，分解成4和2，异或为4^2=6（因为4是100，2是010，异或110=6），分解成3和3，异或0。所以最大值是6，而6=6，所以对于6，P=6。但6不是2的幂，也不是4的倍数？6是2的倍数但不是4的倍数。
 重新参考已知结论：   - 最小值Q：对于偶数C，Q=0；对于奇数C，Q=2^k-1（k是C的最低位连续1的个数）。   - 最大值P：对于任意C，最大值P等于C（当C不是2的幂时），当C是2的幂时，最大值P=C-2（因为无法取到C，最大只能取到C-2）。这个结论在例子C=8（2的幂）时，最大值为6（即8-2），而C=6（不是2的幂）时，最大值为6（即C本身）。  所以，我们可以得到：
  F(C)=P−Q= F(C) = P - Q = {
当C为偶数且不是2的幂：P=C,Q=0−>F(C)=C;P=C, Q=0 -> F(C)=C;   当C为偶数且是2的幂：P=C−2,Q=0−>F(C)=C−2;P=C-2, Q=0 -> F(C)=C-2;   当C为奇数：P=C,Q=2k−1−>F(C)=C−(2k−1);P=C, Q=2^k-1 -> F(C)=C - (2^k-1);  }    那么，我们要找最大的F(C)。显然：    - 对于偶数且不是2的幂：F(C)=C，最大值是2^n-1（当n>=2时，2^n-1是奇数，所以不考虑）
实际上，长度为n的字符串表示的最大数是2^n-1（奇数），所以偶数C的最大值是2^n-2（即全1串减去1，二进制为n-1个1后面一个0）。
而2^n-2是偶数，且当n>=3时，2^n-2不是2的幂（因为2的幂是1,2,4,8,...，而2^n-2显然不是，除非n=2，但n=2时，C最大为3（奇数）和2（偶数），但2是2的幂（2=2^1）
所以当n=2时，C=2是2的幂，F(2)=2-2=0；而C=3（奇数）时，k=2（因为3的二进制11，最低位连续两个1），所以F(3)=3-(2^2-1)=3-3=0。因此n=2时最大异或之力为0。
  • 对于偶数且是2的幂：F(C)=C−2F(C)=C-2，而2的幂的最大值是2^(n-1)（因为长度为n，最大数2^n-1，而2的幂在[0,2^n-1]范围内的最大是2^(n-1)（因为2^n已经超出范围）
不对，2^(n-1)是2的幂，且小于2^n。但2^(n-1)的F(C)=2^(n-1)-2，而偶数非2的幂的最大值可以是2^n-2（当n>=3时，2^n-2不是2的幂），而2^n-2 > 2^(n-1)-2（当n>=3时），所以这种情况不如非2的幂的偶数。
对于奇数：F(C)=C−(2k−1)F(C)=C-(2^k-1)。由于k至少为1，所以F(C)<=C−1F(C)<=C-1。而偶数非2的幂的F(C)=CF(C)=C，所以奇数的值一定小于偶数的最大值（因为偶数最大值可以达到2n−22^n-2，而奇数最大为2n−12^n-1，但F(2n−1)=(2n−1)−(2k−1)F(2^n-1)= (2^n-1) - (2^k-1)，其中kk是2n−12^n-1的最低位连续1的个数实际上，2n−12^n-1的二进制是n个1，所以最低位连续1的个数k=nk=n，所以F(2n−1)=(2n−1)−(2n−1)=0F(2^n-1)= (2^n-1) - (2^n-1)=0。
而其他奇数，比如2n−32^n-3（二进制n-2个1后面是01），那么k=1k=1（因为最低位是1，但前面是0？）所以F(2n−3)=(2n−3)−(21−1)=2n−4F(2^n-3)= (2^n-3) - (2^1-1)=2^n-4。而2n−4<2n−22^n-4 < 2^n-2（当n>=3时），所以奇数中最大的异或之力也不会超过2n−2。2^n-2。
 因此，最大的异或之力一定出现在偶数且非2的幂中，且最大值为2n−22^n-2（当C=2n−2C=2^n-2时）。   那么，我们只需要验证C=2n−2C=2^n-2时，其异或之力是否等于2n−2。2^n-2。
 验证：C=2n−2C=2^n-2，其二进制是n-1个1后面一个0（例如n=3n=3时，C=6C=6，二进制110）。  
  • 最小值QQ：因为CC是偶数，所以Q=0Q=0。
  • 最大值PP：由于CC不是22的幂（因为2的幂的二进制只有一个1，而2n−22^n-2有多个1），所以P=C=2n−2P=C=2^n-2。  
  • 因此，F(C)=2n−2F(C)=2^n-2。
 那么，问题转化为：最大异或之力就是2n−22^n-2。
   但是，我们还要考虑其他偶数非22的幂的CC，比如2n−42^n-4，2n−62^n-6等，它们F(C)=CF(C)=C，而C<2n−2C<2^n-2，所以最大值就是2n−22^n-2。    因此，答案就是2n−22^n-2（当n>=3n>=3时）。当n=2n=2时，我们已知答案为00。  但是，注意题目要求：字符串可含前导零，即长度为nn的字符串表示的数范围是[0,2n−1][0, 2^n-1]。而C=2n−2C=2^n-2在n>=2n>=2时都是合法的。    所以，对于给定的nn：
若n=2n=2，输出00；
-若n>=3n>=3，输出(2n−2)(2^n-2) modmod (109+7)(10^9+7)。
 然而，我们需要验证一下n=3n=3的情况：   长度为33的字符串，C=6C=6（111111不行，因为111111是77，而66是110110）实际上，题目中例子n=3n=3，输出66。
  按照我们的公式：23−2=62^3-2=6，符合。
但是，我们再看一个例子：n=4n=4，那么最大异或之力为24−2=142^4-2=14。我们验证一下C=14C=14（二进制11101110）：
最小值QQ：00（因为偶数）
最大值PP：1414（因为1414不是22的幂，所以最大值就是1414）
所以F(14)=14F(14)=14。
那么，有没有其他CC的F(C)F(C)大于1414？
没有，因为其他CC小于等于1515，而1515（奇数）的F(15)=15−(24−1)=0F(15)=15-(2^4-1)=0，1414就是最大值。
 所以，结论成立。
 因此，算法如下：
  1. 读入nn。
  2. 如果n==2n==2，输出00。
  3. 否则，计算(2n−2)mod(109+7)(2^n - 2) mod (10^9+7)。由于nn最大10910^9，所以使用快速幂。
 注意：当n=1n=1时题目数据范围n>=2n>=2，所以不考虑。  代码实现：
CPP
    #include <iostream>
    using namespace std;
    const long long MOD = 1000000007;
    long long fast_pow(long long base, long long exp, long long mod) {
        long long res = 1;
        base %= mod;
        while (exp) {
            if (exp & 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp >>= 1;
        }
        return res;
    }
    int main() {
        long long n;
        cin >> n;
        if (n == 2) {
            cout << 0 << endl;
        } else {
            long long ans = (fast_pow(2, n, MOD) - 2;
            if (ans < 0) ans += MOD; // 确保非负
            cout << ans % MOD << endl;
        }
        return 0;
    }
 但是，我们注意：当n=2n=2时，22−2=22^2-2=2，但是我们要求n=2n=2时输出00。
所以上面的代码在n=2n=2时直接输出00，其他情况输出2n−22^n-2（模意义下）。  然而，我们也可以统一处理：因为n=2n=2时，22−2=22^2-2=2，但题目要求是00，所以不能直接输出2n−22^n-2。因此，我们单独处理n=2n=2。
 另一种思路：题目要求最大异或之力，而n=2n=2时，最大异或之力为00（因为所有CC中，C=2C=2时F(2)=0F(2)=0，C=3C=3时F(3)=0F(3)=0），所以答案00。
 所以，按照上述代码即可。
 但是，我们再看一下题目中n=3n=3时输出66，我们的计算23−2=62^3-2=6，正确。  因此，我们写代码。
 注意：快速幂取模，因为2n2^n可能很大，所以用快速幂模109+710^9+7。  但是，2n2^n modmod MODMOD 减去22，然后取模，注意负数：如果2n2^n modmod MODMOD 小于22，那么减22可能为负，但n>=3n>=3时，2n>=82^n>=8，所以不会出现负数（因为模109+710^9+7，8−2=6>08-2=6>0）。所以直接减再取模也可以。  然而，为了保险，我们这样写：   ```cpp
CPP
long long ans = (fast_pow(2, n, MOD) - 2 + MOD) % MOD;
 但n>=3n>=3时，2n2^n modmod MOD>=8MOD>=8，所以减22后>=6>=6，所以不会出现负数。
但是模意义下，如果2n2^n modmod MODMOD小于22，那么减22就会变成负数。
然而，当n>=3n>=3时，2n2^n modmod MODMOD至少是88（模之前），但模之后可能小于22吗？
不可能，因为模109+710^9+7，而n>=3n>=3时，2n>=82^n>=8，模一个大于88的数（109+710^9+7）还是88，所以不会小于22。所以直接减也可以。
 但是，当nn很大时，2n2^n modmod MODMOD 可能是一个00到MOD−1MOD-1之间的数，而2n2^n可能大于MODMOD，所以模之后可能小于22 实际上，n>=3n>=3时，2n>=82^n>=8，模MODMOD（109+710^9+7）后，如果大于等于88，那么减22没问题；
如果模之后小于88？但n>=3n>=3时，2n2^n最小为88，所以模之后最小为00（如果MODMOD整除2n2^n，则模后为00），但MOD=109+7MOD=10^9+7，而2n（n>=3）2^n（n>=3）不可能被109+710^9+7整除（因为109+710^9+7是奇数，且大于88），所以模之后不会为00，且最小为88？
不对，比如n=30n=30时，230=10737418242^30=1073741824，而MOD=1000000007MOD=1000000007，所以2302^30 modmod MOD=1073741824MOD=1073741824 % 1000000007 = 73741817，大于22。
所以不会出现模后小于22的情况（因为2n2^n在n>=3n>=3时至少为88，模MODMOD后最小可能为11？但2n2^n是偶数，MODMOD是奇数，所以模后不可能为11？因为偶数模奇数，结果可能是00到MOD−1MOD-1之间的任意整数，但2n2^n是偶数，模奇数后还是偶数？不一定，比如55模3=23=2（偶数），所以模后可能是偶数也可能是奇数？不对，模运算不改变奇偶性：因为MODMOD是奇数，设2n=k∗MOD+r2^n = k*MOD + r，则r=2n−k∗MODr=2^n - k*MOD，因为MODMOD是奇数，k∗MODk*MOD的奇偶性与kk相同，而2n2^n是偶数，所以rr必须是偶数。
所以模后rr是偶数，且r>=0r>=0。而n>=3n>=3时，2n>=82^n>=8，所以rr要么大于等于88，要么为0,2,4,60,2,4,6。
但rr为0,2,4,60,2,4,6时，2n2^n modmod MOD=rMOD=r，那么2n=k∗MOD+r2^n = k*MOD + r，而2n>=82^n>=8，所以如果r<8r<8，那么k∗MOD=2n−r>=8−6=2k*MOD=2^n-r>=8-6=2，所以k>=1k>=1。
但是，当r=0r=0时，2n=k∗MOD2^n=k*MOD，而MOD=109+7MOD=10^9+7，2n2^n要整除MODMOD，而MODMOD是素数（109+710^9+7是素数）？不对，109+710^9+7是素数吗？
实际上，109+710^9+7是一个素数。所以2n2^n整除109+710^9+7是不可能的（因为2n2^n只有素因子22，而109+710^9+7是奇数且大于22的素数）。
所以rr不可能为00。
同理，r=2,4,6r=2,4,6时，由于rr是偶数，且0<=r<MOD0<=r<MOD，所以是可能的。
但是，当r=2r=2时，2n2^n modmod MOD=2MOD=2，那么2n−2=02^n-2=0，输出00？
但n>=3n>=3，2n>=82^n>=8，模MODMOD后等于22，说明2n=k∗MOD+22^n = k*MOD+2，那么2n−2=k∗MOD2^n-2=k*MOD，所以2n−22^n-2是MODMOD的倍数，那么答案00？
不对，因为我们的结论是答案应该是2n−22^n-2，而模MODMOD后就是00。这符合模运算。
 因此，我们的计算应该是：   ans = (2^n - 2) % MOD
 而(2^n - 2)mod MOD 可以写成 ( (2^n mod MOD) - 2 ) % MOD，但这样可能是负数，所以我们加上MOD再取模：   ans = ( (2^n mod MOD - 2) + MOD ) % MOD;  这样，当(2n(2^n % MOD) >=2时，就是(2^n % MOD - 2)；当(2^n % MOD) <2时（即等于0或1），那么加上MOD再减2，然后模MOD。  但是，我们之前已经说明，模后r是偶数，且r>=0，且r不等于0（因为2^n不能被MOD整除），所以r>=2？不一定，比如r=0不可能，但r=2,4,...。但r=0不可能，那么r最小可能是2吗？可能，比如当2^n mod MOD=2时，那么(2^n-2) mod MOD=0。所以我们需要这样处理。  所以，代码中：   long long a = fast_pow(2, n, MOD);   long long ans = (a - 2) % MOD;   if (ans < 0) ans += MOD;   // 或者直接：ans = (a - 2 + MOD) % MOD;  但考虑到a>=0，a-2可能为负（当a=0或1时），但a=0或1的情况在n>=3时不会出现？因为2^n>=8，模MOD后最小为2？不对，模后可能为0（但我们已经排除0，因为MOD不整除2^n）？不对，模后为0的情况不存在（因为MOD是素数且大于2，所以2^n mod MOD=0当且仅当2^n是MOD的倍数，而2^n的因子只有2，MOD是大于2的素数，所以不可能）。所以模后最小为2？也不一定，比如2^3=8，模7等于1（但7不是MOD，MOD是10^9+7）。实际上，模后可能是任意偶数（包括小于2的？不可能，因为模后最小为0，但0不存在，所以最小是2？不一定，比如模后可能是4,6,...，但2^n mod MOD=2的情况：例如，2^n=2 (mod MOD) 当且仅当2^n-2是MOD的倍数。所以我们需要考虑。  因此，为了安全，我们使用：   ans = (a - 2 + MOD) % MOD;  这样，如果a-2是负数，加上MOD就变成正数，然后模MOD就是正确结果。  所以，最终代码：   if (n == 2) {   cout << 0 << endl;   } else {   long long a = fast_pow(2, n, MOD);   long long ans = (a - 2 + MOD) % MOD;   cout << ans << endl;   }  但是，我们考虑n=3：a=8 mod (10^9+7)=8，ans=(8-2+10^9+7)%(10^9+7)=6，正确。  所以，我们这样写。  注意：当n很大时，快速幂能够高效计算2^n mod MOD。  因此，代码实现如下：
CPP

#include <iostream>
using namespace std;
const long long MOD = 1000000007;
long long fast_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) 
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}
int main() {
    long long n;
    cin >> n;
    if (n == 2) {
        cout << 0 << endl;
        return 0;
    }
    long long a = fast_pow(2, n, MOD);
    long long ans = (a - 2 + MOD) % MOD;
    cout << ans << endl;
    return 0;
}```

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...