CF1710C 做题有感

· · 题解

为了语文成绩我决定要在博客锻炼文笔

古人云：x \oplus y 可以看作无进位加法

秋风吹起窗外的落叶，为我的窗户贴上了一层精致的窗花，我这才想起，我们可以令 x=a\oplus b，y=a \oplus c，z=b \oplus c，显然 x \oplus y \oplus z=0

喜鹊飞来飞去，欣喜地发现了一颗长满柿子的柿子树，我也正如这喜鹊，发现 x+y\ge x \oplus y=z ，取等条件为 x \wedge y=0，我恍然大悟

鲁迅曾经说过，暴力出奇迹

这启示我们可以直接暴力数位 dp，从低位到高位，定义 f_{i,ax,bx,cx,xy,xz,yz}，ax,bx,cx 用来保证 a,b,c\le n，xy,yz,xz 表示这些变量之间是否已经满足 x \wedge y \not = 0

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define cmin(a, b) (a)=min((a), (b))
#define cmax(a, b) (a)=max((a), (b))
#define mem(a, x) memset(a, x, sizeof(a))
#define rps(i, b, e) for(int i=(b);i<=(e);i++)
#define prs(i, e, b) for(int i=(e);i>=(b);i--)
#define rpg(i, g, x) for(int i=g.head[x];i;i=g.e[i].nxt)
#define opf(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
using namespace std;
template<class T>
inline void read(T &x) {
    x=0;
    bool f=false;
    char c=getchar();
    while(!isdigit(c))f|=(c=='-'), c=getchar();
    while(isdigit(c))x=x*10+(c-'0'), c=getchar();
    if(f)x=-x;
}
const int NR=2e5+10;
typedef long long LL;
const LL MOD=998244353;
LL n, f[NR][2][2][2][2][2][2];
char aa[NR];
int main() {
    scanf(" %s", aa+1);
    n=strlen(aa+1);
    rps(i, 1, n)aa[i]-='0';
    rps(ax, 0, 1)rps(bx, 0, 1)rps(cx, 0, 1)
        f[n+1][ax][bx][cx][1][1][1]=1;
    prs(i, n, 1)rps(ax, 0, 1)rps(bx, 0, 1)rps(cx, 0, 1)
        rps(ab, 0, 1)rps(ac, 0, 1)rps(bc, 0, 1) {
            rps(a, 0, (ax ? 1 : aa[i]))
                rps(b, 0, (bx ? 1 : aa[i]))
                    rps(c, 0, (cx ? 1 : aa[i])) {
                        f[i][ax][bx][cx][ab][ac][bc]+=
                            f[i+1][ax || a<aa[i]][bx || b<aa[i]][cx || c<aa[i]][ab || ((a^c) && (b^c))][ac || ((a^b) && (b^c))][bc || ((a^c) && (a^b))];
                        f[i][ax][bx][cx][ab][ac][bc]%=MOD;
                    }
        }
    printf("%lld\n", f[1][0][0][0][0][0][0]);
    return 0;
}