NOIP集训day3模赛T1

简化后的题意：我们需要计算所有满足条件的整数对

(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，则无解

计数问题

计算

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

凭什么呢？

回顾数学推导

当 i&j=0 时：

S = i|j

的二进制表示中，每个为1的位要么来自

i

，要么来自

j

，不会同时来自两者
最小的 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：

状态设计：

$ti$ , $tj$ ：(缩写tight)i和j是否紧贴上界
在DP过程中动态确定第一个1的位置（决定位宽）

贡献计算：

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

DP状态转移

维护两个DP数组：

$W[ti][tj]$ ：满足条件的数对数量
$C[ti][tj]$ ：总贡献

对于每个位的三种选择

(0,0)

(0,1)

(1,0)

：

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

边界处理（防爆零）

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

至于为什么？

在数位DP中：

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

同理对于 j。

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

O(l^2)

，能过。

AC code:

CPP

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#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;
}

文章操作

问题？