CF1710C XOR Triangle

数位 DP，对性质的观察。

注意到 $n\le 2\times 10^5$ ，直接考虑数位DP，但是因为这个限制并不能化成较好形式，还是很难做。

一开始得想法是钦定 $a\oplus b=x$，再根据 $x+y\ge x\oplus y$，对应的求出 $a\oplus b,b\oplus c$ 。但这样很难对 $a,b,c$ 的大小进行限制。

但是我们还是考虑利用 $x+y\ge x\oplus y$，这已经和我们的限制很接近了 $(a\oplus b) +(a\oplus c)>(b\oplus c)$ 。更进一步地，我们考虑按位来做，我们只需要有一满足 $(a_i\oplus b_i) +(a_i\oplus c_i)>(b_i\oplus c_i)$ 即可满足整个限制条件。我们只需要记录前面是否已经有一位满足即可。简单数位 DP 即可解决。时间复杂度 $\mathcal O(n)$。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N=2e5+10,mod=998244353;
int n;
char s[N];
int a[N];
int f[N][2][2][2][2][2][2];
inline int adj(int x){return x>=mod?x-mod:x;}
int dfs(int pos,bool l1,bool l2,bool l3,bool x,bool y,bool z)
{
    if(pos>n)return x&&y&&z;
    int &res=f[pos][l1][l2][l3][x][y][z];
    if(~res)return res;
    res=0;
    for(int i=0;i<=(l1?a[pos]:1);i++)
        for(int j=0;j<=(l2?a[pos]:1);j++)
            for(int k=0;k<=(l3?a[pos]:1);k++)
    res=adj(res+dfs(pos+1,l1&&(i==a[pos]),l2&&(j==a[pos]),l3&&(k==a[pos]),
        x||((i^j)+(i^k)>(j^k)),y||((j^i)+(j^k)>(i^k)),z||((k^i)+(k^j)>(i^j))));
    return res;
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++)a[i]=s[i]-'0';
    memset(f,-1,sizeof(f));
    printf("%d\n",dfs(1,1,1,1,0,0,0));
    return 0;
}