NOIP集训day3模赛T1

David0225 · 2025-11-26 14:15:19 · 个人记录

简化后的题意：我们需要计算所有满足条件的整数对 (i, j) 在 [0, n-1] 范围内的函数 f(i,j) 之和。函数 f(i,j) 定义为最小的正整数 k，使得 (i+k) XOR (j+k) = i+j 。如果不存在这样的 k，则 f(i,j) 为 0。

问题？

函数 f(i,j) 的定义：

最小的 正整数 k 使得 (i+k) XOR (j+k) = i+j
无解时 f(i,j) = 0

同时，注意到

当且仅当 i & j = 0 $ 时才有解
此时 f(i,j) = 2^l ，其中 l 是 i|j 的位宽
如果 i|j 全为1，则无解

计数问题

:::info[计算]

\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} [i \& j = 0] \times 2^{\text{位宽}(i|j)}

:::

凭什么呢？

回顾数学推导

当 i&j=0 时：

最小的 k 满足 k & S = 0 且 $k > 0$ 的就是 $2^{位宽(S)}

因为 2^{位宽(S)} 在 S 的所有为1的位上都是0，且在更高位上是1

举个栗子：
i=1 (01), j=2 (10)
i&j=0 ✓
S = i|j = 3 (11)，位宽=2
贡献：2² = 4
验证：f(1,2)=4（最小的k使得 (1+k) XOR (2+k) = 3）

总的来说

对于每个 S = i|j ，满足 i|j = S 且 i&j = 0的数对恰好有 2^{popcount(S)} 个
但需要保证 i < n 且 j < n

数位DP

由于 n 很大（题目告诉我们二进制长度可达3000），需要使用数位DP：

状态设计：

在DP过程中动态确定第一个1的位置（决定位宽）

贡献计算：

当遇到第一个1在位置k时，贡献为 2^{L-k}
使用预计算的2的幂次模 10^9+7

DP状态转移

维护两个DP数组：

对于每个位的三种选择 (0,0) , (0,1) , (1,0) ：

选择 (0,0) ：继续DP，不增加贡献
选择 (0,1) 或 (1,0) ：遇到第一个1，立即计算贡献

边界处理（防爆零）

初始化：处理完所有位时，只有 tight_i = false && tight_j = false 的状态有效
最终答案： C[1][1] （从最高位开始且都紧贴上界）

:::info[至于为什么？] 在数位DP中：

tight_i = true 表示到目前为止，i 的前缀与 n 的前缀完全相等
当处理完所有位时，如果 tight_i = true，意味着 i = n
但题目要求 i < n，所以 i = n 是不合法的

同理对于 j。 :::

简单来说，五哦们需要干三件事情：先看到数学性质；然后观察转化为计数问题；最终数位DP ，时间复杂度 O(l^2) ，能过。

AC code:

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int MOD = 1e9+7;
signed main()
{
    freopen("xor.in", "r", stdin);
    freopen("xor.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    string s;
    cin >> s;
    int l = s.length();
    int dp[2][2][3001] = {0};
    int* bits = new int[l];
    int* pow2 = new int[l + 1];

    for (int i = 0; i < l; i++) bits[i] = s[l - 1 - i] - '0';
    pow2[0] = 1;
    for (int i = 1; i <= l; i++) pow2[i] = (pow2[i - 1] * 2) % MOD;
    dp[1][1][l] = 1;
    for (int i = l - 1; i >= 0; i--)
    {
        int newdp[2][2][3001] = {0};
        for (int ti = 0; ti < 2; ti++)
        {
            for (int tj = 0; tj < 2; tj++) {
                for (int cdd = 0; cdd <= l; cdd++) {
                    if (dp[ti][tj][cdd] == 0) continue;
                    for (int choice = 0; choice < 3; choice++) {
                        int ibit, jbit;
                        if (choice == 0) {
                            ibit = 0;
                            jbit = 0;
                        } else if (choice == 1) {
                            ibit = 0;
                            jbit = 1;
                        } else {
                            ibit = 1;
                            jbit = 0;
                        }
                        int newti;
                        if (ti) {
                            if (ibit > bits[i]) continue;
                            newti = (ibit == bits[i]) ? 1 : 0;
                        } else {
                            newti = 0;
                        }
                        int newtj;
                        if (tj) {
                            if (jbit > bits[i]) continue;
                            newtj = (jbit == bits[i]) ? 1 : 0;
                        } else {
                            newtj = 0;
                        }
                        int T = ibit | jbit;
                        int newcdd = cdd;
                        if (T == 0) newcdd = min(cdd, i);
                        newdp[newti][newtj][newcdd] = (newdp[newti][newtj][newcdd] + dp[ti][tj][cdd]) % MOD;
                    }
                }
            }
        }
        for (int a = 0; a < 2; a++)
            for (int b = 0; b < 2; b++)
                for (int c = 0; c <= l; c++)
                    dp[a][b][c] = newdp[a][b][c];
    }
    int ans = 0;
    for (int cdd = 0; cdd <= l; cdd++) ans = (ans + dp[0][0][cdd] * pow2[cdd]) % MOD;
    cout << ans << endl;
    return 0;
}