毎日格上の問題を倒すやつの21日目¹です。

初めての橙後半の難問です。

問題リンク

atcoder.jp

問題概要

以下の条件をすべて満たす $(l,r)$ の組の数を $998244353$ で割ったあまりを求めてね。

$L\leq l\leq r\leq R$
$l\oplus l+1 \oplus \dots \oplus r=V$

解法

$f(x)=1\oplus 2\oplus \dots x$ とします。

重要な事実として、以下が成り立ちます。²

$f(x)=\begin{cases}x\ (x\ \text{mod}\ 4= 0)\\1\ (x\ \text{mod}\ 4= 1)\\x+1\ (x\ \text{mod}\ 4= 2)\\0\ (x\ \text{mod}\ 4= 3)\end{cases}$

このとき、累積和の考え方を使用すれば $l\oplus l+1 \oplus \dots \oplus r=f(r)\oplus f(l-1)$ となることが容易にわかります。

よって、問題を一段階簡略化できます。

$L-1\leq l\lt r\leq R$

$f(r)\oplus f(l)=V$

この問題を考えていきたいのですが、のちのち厄介になる場合を先に処理していきます。

$V=0,1$ のとき… $f(x)=0,1$ になるような $x$ の数は容易に求められるため、掛け算で終わります。ほかの場合を考える必要がないことも後の考察を利用して証明可能です。
$R-L$ が非常に小さいとき…区間の幅を $N$ として、 $O(N\log N)$ で愚直に求めて構いません。

それ以外の場合を考えます。

$f(x)=0,1$ の場合は明らかに容易に求められます。

あとは、それ以外の場合です。

その場合、 $f(x)\ \text{mod}\ 4=0,3$ になることが確認できます。そのため、 $V\ \text{mod}\ 4=1,2$ の場合は考えなくてよいことがわかります。

それ以外の場合は、適切に範囲を決めて桁DPです。上限のみを指定するDPを4回やって包除原理すればよいです。³

提出コード

from collections import defaultdict

def cumxor(num):
    if num%4==0:
        return num
    if num%4==1:
        return 1
    if num%4==2:
        return num+1
    return 0

def dp(x,y):
    if x<0 or y<0:
        return 0
    digit=[[[[0,0],[0,0]],[[0,0],[0,0]]] for i in range(64)]
    digit[1][1][1][1]=1
    for i in range(2,64):
        jtf=[(1<<i)-1,x&((1<<i)-1)]
        ktf=[(1<<i)-1,y&((1<<i)-1)]
        for j in range(2):
            for k in range(2):
                for l in range(2):
                    digit[i-1][j][k][l]%=MOD
                    if (V>>i)&1==1:
                        digit[i][(jtf[j]+(1<<i))<=(x&((1<<(i+1))-1))][ktf[k]<=(y&((1<<(i+1))-1))][0]+=digit[i-1][j][k][l]
                        digit[i][jtf[j]<=(x&((1<<(i+1))-1))][(ktf[k]+(1<<i))<=(y&((1<<(i+1))-1))][1]+=digit[i-1][j][k][l]
                    else:
                        digit[i][(jtf[j]+(1<<i))<=(x&((1<<(i+1))-1))][(ktf[k]+(1<<i))<=(y&((1<<(i+1))-1))][l]+=digit[i-1][j][k][l]
                        digit[i][jtf[j]<=(x&((1<<(i+1))-1))][ktf[k]<=(y&((1<<(i+1))-1))][l]+=digit[i-1][j][k][l]
    return digit[-1][1][1][1]%MOD

def solve(jury=False):
    if jury:
        cum=defaultdict(int)
        cum[cumxor(L)]=1
        ret=0
        for i in range(L+1,R+1):
            ret+=cum[V^cumxor(i)]
            cum[cumxor(i)]+=1
            ret%=MOD
        return ret
    zero=(R+1)//4-L//4
    if L==0:
        zero+=1
    one=(R+3)//4-(L+2)//4
    if V==0:
        return ((zero*(zero-1)+one*(one-1))//2)%MOD
    if V==1:
        return (zero*one)%MOD
    if L==0:
        zero-=1
    ret=0
    if V%4==0:
        if L<=V<=R:
            ret+=zero
    elif V%4==3:
        if L<=V-1<=R:
            ret+=zero
    if (V^1)%4==0:
        if L<=(V^1)<=R:
            ret+=one
    elif (V^1)%4==3:
        if L<=(V^1)-1<=R:
            ret+=one
    ret%=MOD
    minz=L
    maxz=R
    while minz%4!=0:
        minz+=1
    while maxz%4!=0:
        maxz-=1
    mint=L
    maxt=R
    while mint%4!=2:
        mint+=1
    mint+=1
    while maxt%4!=2:
        maxt-=1
    maxt+=1
    if V%4==0:
        ret+=dp(maxz,maxz)
        ret-=dp(maxz,minz-4)
        ret-=dp(minz-4,maxz)
        ret+=dp(minz-4,minz-4)
        ret+=dp(maxt,maxt)
        ret-=dp(maxt,mint-4)
        ret-=dp(mint-4,maxt)
        ret+=dp(mint-4,mint-4)
    elif V%4==3:
        ret+=dp(maxz,maxt)
        ret-=dp(maxz,mint-4)
        ret-=dp(minz-4,maxt)
        ret+=dp(minz-4,mint-4)
        ret+=dp(maxt,maxz)
        ret-=dp(maxt,minz-4)
        ret-=dp(mint-4,maxz)
        ret+=dp(mint-4,minz-4)
    return ret%MOD

MOD=998244353
L,R,V=map(int,input().split())
L-=1
print(solve((R-L)<=100000)%MOD)

atcoder.jp

感想

今日死んでもギリ許せるくらいうれしい

3週間かぁ…よく続いたな↩
AtCoder ABC 121 D - XOR World (緑色, 400 点) - けんちょんの競プロ精進記録とか参照、理由は知らん↩
前半頑張った分後半めっちゃ失速した↩

halcの競プロ精進ブログ

はるくが競プロしたことを書き留めるなにか

【今日の精進】ARC133D - Range XOR

問題リンク

問題概要

解法

提出コード

感想