CF1710C

y0y68 · 2022-07-27 09:45:43 · 题解

数位DP入门题，给一种写起来很简洁的做法。

对于三个数 x,y,z ，除了大小限制外，剩余的限制只有 x⊕y+x⊕z>y⊕z，y⊕x+y⊕z>x⊕z，z⊕x+z⊕y>x⊕y。

这三个式子是轮换的，先考虑第二个式子。

设 x,y,z 在某个二进制位上分别是 a,b,c，那个只有 2^3=8 种 a,b,c 的组合，我们将 a,b,c,b⊕a,b⊕c,a⊕c 的表给打出来：

我们发现 b⊕a+b⊕c 总是不小于 a⊕c，那么对于所有数位，只需存在一位是 b⊕a+b⊕c>a⊕c 的情况（当且仅当 a=0,b=1,c=0 或 a=1,b=0,c=1），那么我们就能保证 y⊕x+y⊕z>x⊕z，对于另外两个限制将这个结论给轮换一下即可。

所以我们可以在 DP 中多记三个量，分别表示目前能否保证x⊕y+x⊕z>y⊕z，y⊕x+y⊕z>x⊕z，z⊕x+z⊕y>x⊕y。

然后就写完了，时间复杂度 O(2^9n)，十分合理：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int mod=998244353;
char a[N];
int n,dp[N][2][2][2][2][2][2];
inline int dfs(int k,bool l1,bool l2,bool l3,bool _x,bool _y,bool _z){
    if(k>n)return _x&&_y&&_z;
    if(dp[k][l1][l2][l3][_x][_y][_z]!=-1)return dp[k][l1][l2][l3][_x][_y][_z];
    int res=0;
    for(int x=0;x<=(l1?a[k]-'0':1);x++)for(int y=0;y<=(l2?a[k]-'0':1);y++)for(int z=0;z<=(l3?a[k]-'0':1);z++)
        res=(res+dfs(k+1,l1&(x==a[k]-'0'),l2&(y==a[k]-'0'),l3&(z==a[k]-'0'),_x|(x==0&&y==1&&z==1)|(x==1&&y==0&&z==0),_y|(y==0&&x==1&&z==1)|(y==1&&x==0&&z==0),_z|(z==0&&x==1&&y==1)|(z==1&&x==0&&y==0)))%mod;
    return dp[k][l1][l2][l3][_x][_y][_z]=res;
}
int main(){
    scanf("%s",a+1);
    n=strlen(a+1);
    memset(dp,-1,sizeof dp);
    printf("%d\n",dfs(1,1,1,1,0,0,0));
    return 0;
}