ARC133D Range XOR

题目链接：【ARC133D】 Range XOR

非常好数位 dp。

思路

根据异或的前缀和，我们可以把式子化成这样。

\[\sum_{i=l}^r\sum_{j=i}^r [s_j\oplus s_{i-1}==v] \]

然后先去掉 \(l \leq r\) 的限制。

\[\sum_{i=l-1}^{r-1}\sum_{j=l}^r [s_j\oplus s_i==v] \]

但是这个玩意没有对称性，很蛋疼，先把区间拉平。

\[\sum_{i=l-1}^r\sum_{j=l-1}^r [s_j\oplus s_i==v] \]

然后考虑这个式子多算的部分，发现多算的只有 \(i=j\) 的情况和 \((i,j)\) 与 \((j,i)\) 算了 \(2\) 次。

把 \(i=j\) 的部分减去后再除以 \(2\) 就可以得到要的东西。

设

\[S(n,m)=\sum_{i=0}^n\sum_{j=0}^m[s_i\oplus s_j==v] \]

最后我们想要求的东西是

\[\sum_{i=l-1}^r\sum_{j=l-1}^r [s_j\oplus s_i==v]=S(r,r)-2S(l-2,r)+S(l-2,l-2) \]

由于 \(S(r,l-2)=S(l-2,r)\)。

这样子还是很不友好，我们观察一下 \(s_i\) 的性质。

我们会发现

\[s_0=0\\ s_1=1\\ s_2=3\\ s_3=0\\ s_4=4\\ s_5=1\\ s_6=7\\ s_7=0\\ \cdots \]

显然有规律：

\[s_i=\begin {cases} i\ \ \ \ \ \ \ \ \ i \equiv 0\ (\mod 4)\\ 1\ \ \ \ \ \ \ \ \ i \equiv 1\ (\mod 4)\\ i+1\ \ \ i \equiv 2\ (\mod 4)\\ 0\ \ \ \ \ \ \ \ \ i \equiv 3\ (\mod 4)\\ \end{cases} \]

可以使用数学归纳法证明，证明比较简单，留给读者自行思考。

如果 \(i\equiv 1,3(\mod 4)\) 或 \(j \equiv 1,3 (\mod 4)\) 的话，\(s_i\) 或 \(s_j\) 为常量，直接算就好。

我们先把后两位确定下来，接着删除末两位，消除模 \(4\) 的限制。

剩下的等价求

\[\sum_{i=0}^{\lfloor n/4 \rfloor} \sum_{j=0}^{\lfloor m/4 \rfloor} [l \oplus r == \lfloor v/4 \rfloor] \]

这里可以考虑先枚举最后两位，如果是 \(1\) 或 \(3\) 可以直接乘一个常量，如果是 \(2\) 或 \(0\) 可以用数位 dp 来解决这个问题。

时间复杂度大概是 \(O(\log n)\)。

CODE

#include<bits/stdc++.h>
using namespace std;

#define ll long long

const ll mod=998244353;
const int maxn=65,kL=60;

ll l,r,v;
ll f[maxn][2][2];

ll kB[4]={0,1,3,0};

ll S(ll i,ll n,ll ln,ll m,ll lm,ll v)
{
    if(i==-1) return 1;
    ll &fs=f[i][ln][lm];
    if(~fs) return fs;
    fs=0;
    for(ll kn=0,vn=(ln?(n>>i&1):1);kn<=vn;kn++)
    {
        for(ll km=0,vm=(lm?(m>>i&1):1);km<=vm;km++)
        {
            if((kn^km)==(v>>i&1)) fs=(fs+S(i-1,n,ln&&kn==vn,m,lm&&km==vm,v))%mod;
        }
    }
    return fs;
}
ll bS(ll n,ll m,ll v)
{
    memset(f,-1,sizeof(f));
    return S(kL-1,n,1,m,1,v);
}
ll S1(ll n,ll m)
{
    if(n<0||m<0) return 0;
    ll s=0;
    for(ll i=0;i<4;i++)
    {
        for(ll j=0;j<4;j++)
        {
            ll w=(v^kB[i]^kB[j]);
            if(w&3) continue;
            ll ci=(n>>2)-((n&3)<i);
            ll cj=(m>>2)-((m&3)<j);
            s=(s+bS((i&1)?0:ci,(j&1)?0:cj,w>>2)*((i&1)?(ci+1)%mod:1)%mod*((j&1)?(cj+1)%mod:1)%mod)%mod;
        }
    }
    return s;
}
ll S2(ll l,ll r)
{
    return ((S1(r,r)-2*S1(l-1,r)+S1(l-1,l-1))%mod+mod)%mod;
}

int main()
{
    scanf("%lld%lld%lld",&l,&r,&v);
    printf("%lld",(S2(l-1,r)-(v==0)*(r-l+2)%mod+mod)*(mod+1)/2%mod);
}

526互联

ARC133D Range XOR

ARC133D Range XOR

思路

CODE