ARC129-A Smaller XOR

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2 1 2");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 2 19");
            //10
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1000000000000000000 1 1000000000000000000");
            //847078495393153025
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mN = wkArr[0];
        long L = wkArr[1];
        long R = wkArr[2];

        long Result1 = ExecDP(R);
        long Result2 = ExecDP(L - 1);

        //Console.WriteLine("区間[0,{0}]でXORが{1}未満なのは{2}通り", R, mN, Result1);
        //Console.WriteLine("区間[0,{0}]でXORが{1}未満なのは{2}通り", L - 1, mN, Result2);

        Console.WriteLine(Result1 - Result2);
    }

    // 区間[0,pR] で桁DPを行って、何通りあるかを返す
    static long ExecDP(long pR)
    {
        string BinStr = Convert.ToString(pR, 2);
        char[] BinArr = BinStr.ToCharArray();

        // 場合の数[R未満確定フラグ,N未満確定フラグ]なDP表
        long[,] PrevDP = new long[2, 2];
        PrevDP[0, 0] = 1;

        long UB = BinArr.GetUpperBound(0);

        var CurrBitDict = new Dictionary<long, long>();
        long Curr2Beki = 1;
        for (long I = UB; 0 <= I; I--) {
            CurrBitDict[I] = Curr2Beki;
            Curr2Beki *= 2;
        }

        for (long I = 0; I <= UB; I++) {
            long[,] CurrDP = new long[2, 2];
            for (long J = 0; J <= 1; J++) {
                for (long K = 0; K <= 1; K++) {
                    if (PrevDP[J, K] == 0) continue;

                    for (char NewChar = '0'; NewChar <= '1'; NewChar++) {
                        if (J == 0 && BinArr[I] < NewChar) continue;

                        long NewJ = J;
                        if (BinArr[I] > NewChar) NewJ = 1;

                        int CurrNum = NewChar - '0';

                        long NewK = K;
                        if (K == 0) {
                            long ExtractN = mN & CurrBitDict[I];
                            long ExtractCurr = CurrBitDict[I] * CurrNum;
                            if ((ExtractN ^ ExtractCurr) > ExtractN) {
                                continue;
                            }
                            if ((ExtractN ^ ExtractCurr) < ExtractN) {
                                NewK = 1;
                            }
                        }
                        CurrDP[NewJ, NewK] += PrevDP[J, K];
                    }
                }
            }
            PrevDP = CurrDP;
        }

        long Answer = 0;
        Answer += PrevDP[0, 1];
        Answer += PrevDP[1, 1];
        return Answer;
    }
}

解説

場合の数[R未満確定フラグ,N未満確定フラグ]
を更新する、2進数での桁DPで解いてます。