E - Prefix-free Game AtCoder Regular Contest 087

E - Prefix-free Game

問題概略

0,1の高さLの完全二分木でお互いにコマを置いていく。コマが置かれた親と子は使えない。置けなくなったら負け

Sn で初期配置が渡される

制約

• $1\le N\le {10}^5$
• $1\le L\le {10}^{18}$
• $s_1$, $s_2$, ..., $s_N$ はすべて相異なる。
• $\{s_1,s_2,...,s_N\}$ は良い文字列集合である。
• $|s_1|+|s_2|+...+|s_N|\le {10}^5$

解法

コマを何個か置いた状態は、それぞれ独立したゲームの形になりgrundy数を使える。

あるノードで、子ノードがあれば、高さ（L-深さ）の完全二分木が存在する

そんなかんじで

class BitTrie
{
    Node root = new Node(0);

    public void add(String s)
    {
        Node cur = root;
        for (int i = 0; i < s.length(); i++)
        {
            if (s.charAt(i) == '0')
            {
                if (cur.left == null) cur.appendLeft();
                cur = cur.left;
            }
            else
            {
                if (cur.right == null) cur.appendRight();
                cur = cur.right;
            }
        }
        cur.hit();
    }

    public void dfs(Node root)
    {
        if (root.hit > 0) return;
        if (root.left != null) dfs(root.left);
        else Main.grundy ^= (Main.L - root.depth) & -(Main.L - root.depth);

        if (root.right != null) dfs(root.right);
        else Main.grundy ^= (Main.L - root.depth) & -(Main.L - root.depth);
    }

    class Node
    {
        Node left = null;
        Node right = null;
        int depth;
        int hit;

        Node(int dep)
        {
            depth = dep;
        }

        public void appendLeft()
        {
            left = new Node(depth + 1);
        }

        public void appendRight()
        {
            right = new Node(depth + 1);
        }

        public void hit()
        {
            hit++;
        }
    }
}

public class Main
{
    static StringBuilder sb = new StringBuilder();
    static FastScanner sc = new FastScanner(System.in);
    static int INF = 12345678;
    static long LINF = 123456789123456789L;
    static long MINF = -123456789123456789L;
    static long MOD = 1000000007;
    static int[] y4 = {0, 1, 0, -1};
    static int[] x4 = {1, 0, -1, 0};
    static int[] y8 = {0, 1, 0, -1, -1, 1, 1, -1};
    static int[] x8 = {1, 0, -1, 0, 1, -1, 1, -1};
    static long[] F;//factorial
    static boolean[] isPrime;
    static int[] primes;
    static char[][] map;

    static int N;
    static long L;
    static long grundy;

    public static void main(String[] args)
    {
        //longを忘れるなオーバーフローするぞ
        N = sc.nextInt();
        L = sc.nextLong();
        String[] s = new String[N];
        BitTrie bt = new BitTrie();

        for (int i = 0; i < N; i++)
        {
            s[i] = sc.next();
            bt.add(s[i]);
        }
        bt.dfs(bt.root);
        System.out.println(grundy != 0 ? "Alice" : "Bob");

    }