問題
給定 n (≤1e9)，計算 E = (1/n²) Σ_{0≤i,j。
按位獨立性
XOR 運算各二進制位獨立。對第 k 位（權值 2ᵏ）：
- 設 [0, n-1] 中第 k 位為 0 的數有
cnt0 個，為 1 的有 cnt1 = n - cnt0
- XOR 該位為 1 的有序對數：
2 * cnt0 * cnt1（0^1 和 1^0）
- 該位對期望貢獻：
(2 * cnt0 * cnt1 / n²) * 2ᵏ
計算 cnt0
0..n-1 中第 k 位週期為 2^{k+1}，每週期前 2ᵏ 個為 0，後 2ᵏ 個為 1。
long long cnt0 = (n >> (k+1)) << k; // 完整週期貢獻
long long rem = n & ((1LL<<(k+1)) - 1); // 餘數部分
cnt0 += min(rem, 1LL<
完整代碼
#include <cstdio>
using namespace std;
int main() {
int T; scanf("%d", &T);
while (T--) {
long long n; scanf("%lld", &n);
double ans = 0;
for (int k = 0; k < 31; ++k) { // n < 1e9 < 2^30
long long cycle = 1LL << (k+1);
long long half = 1LL << k;
long long cnt0 = (n / cycle) * half + min(n % cycle, half);
long long cnt1 = n - cnt0;
ans += (2.0 * cnt0 * cnt1 / (n * n)) * (1LL << k);
}
printf("%.2f\n", ans);
}
return 0;
}
複雜度
- 時間 O(log n) 每測試案例（31 位循環）
- 空間 O(1)
數學驗證
對 n=2：數對 (0,0)(0,1)(1,0)(1,1) → XOR 和 = 0+1+1+0=2 → 期望 2/4=0.5。公式計算：k=0 位，cnt0=1, cnt1=1 → 貢獻 (2*1*1/4)*1 = 0.5。吻合。
