SRM601D1Med WinterAndSnowmen
xorについての知見が増えた
問題概要(原文)
以下を満たす集合 $A$,$B$ がある． $x=A_1 \oplus A_2 \oplus \ldots, y=B_1 \oplus B_2 \oplus \ldots,$ としたとき $x<y$ となるような $A,B$ の選び方は何通りあるか．
- $A \subseteq \{1,2,\ldots, N \}$
- $B \subseteq \{1,2,\ldots, M \}$
- $A \cap B = \phi$
考察
xor を取ったときに $x<y$ であるということは $2$ 進数表記で先頭 $d$ 桁において， $x$ と $y$ の値が一致し，$d+1$ 桁目が $0,1$ となっているということである．
そのような $d$ を全探索する方針で考える． $x$ と $y$ の先頭 $d$ 桁が一致するとは， $x \oplus y$ の先頭 $d$ 桁が全て $0$ ということと同値．
このようにして数えると， $O(max(N,M)^2log(max(N,M)))$ となる．
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class WinterAndSnowmen
{
public int getNumber(int N, int M)
{
const int MOD = 1000000007;
var max = Math.Max(N, M);
int ans = 0;
for (int k = 0; k <= 10; k++)
{
var dp = Enumerate(2048, x => new int[2, 2]);
dp[0][0, 0] = 1;
for (int i = 1; i <= max; i++)
{
var p = i >> k;
var q = p >> 1;
var r = p & 1;
var next = Enumerate(2048 >> k, x => new int[2, 2]);
for (int j = 0; j < 2048 >> k; j++)
for (int u = 0; u < 2; u++)
for (int v = 0; v < 2; v++)
{
if (dp[j][u, v] == 0) continue;
if (i <= N)
if ((next[j ^ q][u ^ r, v] += dp[j][u, v]) >= MOD) next[j ^ q][u ^ r, v] -= MOD;
if (i <= M)
if ((next[j ^ q][u, v ^ r] += dp[j][u, v]) >= MOD) next[j ^ q][u, v ^ r] -= MOD;
if ((next[j][u, v] += dp[j][u, v]) >= MOD) next[j][u, v] -= MOD;
}
dp = next;
}
ans += dp[0][0, 1];
ans %= MOD;
}
return ans;
}
static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
}
コメント
- 先頭 $d$ 桁が一致するのを全探索するのは思いついたが，$x \oplus y$ を状態に持つのは思いつかなかった
- 定数倍がめちゃくちゃきつかった．なんでこんな重いんだろう．キャッシュヒット効率とかは効きそう．
