一、题目描述：
给你四个整数 $N,A_1,A_2,A_3$。求满足以下条件的正整数三元组 $(X_1,X_2,X_3)$ 的数量。
对于 $i\in [1,3],A_i\mid X_i$ 且 $X_1\oplus X_2\oplus X_3=0$。答案对 $998244353$ 取模。
数据范围：$1\le N \le 1\times 10^{18},1\le A_1,A_2,A_3\le 10$。
二、解题思路：
首先我们发现 $N$ 很大，$A_i$ 很小，所以想到 $数位dp$。当然我是想不到的。
而且这题状态也很离谱，我想了好久才想懂。解释一下 $dp[i][A][B][C][l_1][l_2][l_3][f_1][f_2][f_3]$ 的意思。
$在二进制从底往高的第\ i\ 位中满足特定条件的组合 (X_1,X_2,X_3) 对答案做出的贡献。条件如下：$
$X_1\ mod\ A_1 = A,X_2\ mod\ A_2 = B,X_3\ mod\ A_3 =C,l_i\ 表示\ X_i\ 是否顶格,f_i\ 表示\ X_i\ 是否为\ 0$
好，如果理解了状态的含义，转移是简单的。只需要让每一位异或和都为\ 0\ 就行了。
时间复杂度 $O(8\times log_2^n\times A_1\times A_2\times A_3)$。代码属实难看。
三、完整代码：
1 #include<bits/stdc++.h> 2 #define M 998244353 3 #define ll long long 4 using namespace std; 5 ll n,a,b,c,len,v[70]; 6 ll f[70][10][10][10][2][2][2][2][2][2]; 7 void S(ll &x,ll y){x+=y;if(x>=M)x-=M;} 8 ll L(ll x){return x<<1;}ll R(ll x){return x<<1|1;} 9 ll D(ll p,ll x,ll y,ll z,ll l1,ll l2,ll l3,ll f1,ll f2,ll f3){ 10 if(!p) return !x&&!y&&!z&&f1&&f2&&f3; 11 if(~f[p][x][y][z][l1][l2][l3][f1][f2][f3]) 12 return f[p][x][y][z][l1][l2][l3][f1][f2][f3]; 13 bool A=v[p]||(!l1),B=v[p]||(!l2),C=v[p]||(!l3); 14 ll r=D(p-1,L(x)%a,L(y)%b,L(z)%c,A^1,B^1,C^1,f1,f2,f3); 15 if(A&B) S(r,D(p-1,R(x)%a,R(y)%b,L(z)%c,l1,l2,C^1,1,1,f3)); 16 if(A&C) S(r,D(p-1,R(x)%a,L(y)%b,R(z)%c,l1,B^1,l3,1,f2,1)); 17 if(B&C) S(r,D(p-1,L(x)%a,R(y)%b,R(z)%c,A^1,l2,l3,f1,1,1)); 18 return f[p][x][y][z][l1][l2][l3][f1][f2][f3]=r; 19 } 20 int main(){ 21 ios::sync_with_stdio(false); 22 cin.tie(0);cout.tie(0); 23 cin>>n>>a>>b>>c; memset(f,-1,sizeof f); 24 while(n) v[++len]=n&1,n>>=1; 25 cout<<D(len,0,0,0,1,1,1,0,0,0)<<'\n'; 26 return 0; 27 }
四、写题心得：
这两天写了两三道 $数位dp$ 的题，也来总结一下吧：
$1、记忆化搜索确实好用，以后不写递推了。=> Exp++!$
$2、一些与数字有关，数据范围又很极端的题(val=1\times 10……{18}\ 或者\ val\le 100)，或许应该用\ 数位dp\ 来写。=> Exp++!$
$3、转移不一定要\ O(1)\ 地转移，可以通过将一维数据放在转移里面来降低空间复杂度和初始化时间。(如\ P4127[AHOI2009]同类分布)=> Exp++!$