题解：CF2252E Generational Triplets

· · 题解

做本题摘去大脑，这是不需要任何观察和推导的做法。

准备

对以下两个条件数位 dp：

考虑 a,b，令 d=b-a，c=b+d。

且 a\oplus b=c。

由于加减法列竖式是从低往高考虑，因此从低位向高位考虑。

考虑状态所需记录的条件，必要的是当前考虑到的位数 i，加减法的退位进位也要记录成 j,k。

以及条件 a<b<c\le n，当前 a 是否 \ne b 记录成 p，当前 c 是否 \le n 记录成 q。

这样判断 a<b 仅需判断 p=\text{true} 且 j=\text{false}。

## 分析 $f_{i,j,k,p,q}$ 表示考虑低 $i$ 位，$b-a$ 向下一位减法借位 $j$，$b+d$ 向下一位加法进位 $k$，$a$ 是否已经 $\ne b$，$c$ 是否 $\le n$。 设这一位 $a,b$ 分别填 $A,B$。 刷表，$f_{i-1,j,k,p,q}$ 将转移给状态 $f_{i,I,J,P,Q}$。 考虑减法，$D=B-A-j$。 $J=[D<0]$，那么 $d_i=D\bmod 2$。 考虑加法，$C=B+d_i+k$。 $K=[C\ge 2]$，那么 $c_i=C\bmod 2$。 $P=p\lor[A\ne B]$。 $Q=\begin{cases} q,c_i=n_i\\ 0,c_i>n_i\\ 1,c_i<n_i\\ \end{cases}

判断 [A\oplus B=c_i]=\text{true} 才能转移。

则答案是 f_{pos,0,0,1,1}（原因在准备部分讲过了）。

模拟即可。

Code

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1e9+7;
ll n;
int t,f[65][2][2][2][2]; 
//前 i 位，是否借位，是否进位，[a!=b]，[c<=n] 
void sum(int &x,int y){
    x=(x+y)%mod;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        memset(f,0,sizeof(f));
        f[0][0][0][0][1]=1;
        for(int i=0;i<=__lg(n)+1;i++)for(int j=0;j<=1;j++)for(int k=0;k<=1;k++)for(int p=0;p<=1;p++)for(int q=0;q<=1;q++)for(int a=0;a<=1;a++)for(int b=0;b<=1;b++){
            int J,K,P,Q;
            int D=b-a-j;
            J=(D<0);
            int d=D&1;
            int C=b+d+k;
            K=(C>=2);
            int c=C&1;
            if(c!=(a^b))continue;
            P=p|(a!=b);
            int ni=(n>>i)&1;
            if(c==ni)Q=q;
            else Q=(c<ni);
            sum(f[i+1][J][K][P][Q],f[i][j][k][p][q]); 
        }
        cout<<f[__lg(n)+1][0][0][1][1]<<'\n'; 
    }
    return 0;
}