题解：AT_abc138_f [ABC138F] Coincidence

Lv5_Railgun · 2024-10-02 15:47:30 · 题解

为什么大家写的都是记忆化搜索，没人写正向递推（）

原题传送门

看到数据范围，考虑 O(1) 算法，然而并不可行，所以我们考虑 O(\log n) 算法，就是数位 dp。

考虑将 y \bmod x 这一坨东西转换，我们注意到，x \oplus y \ge y-x ，所以为了满足条件 y-x \le x \bmod y , 接着，我们又注意到 x \bmod y = x-\lfloor x/y \rfloor \times y，易得，当且仅当 \lfloor x/y \rfloor=1 ，即 2 \times y>x 时，有 y-x \le x \bmod y ，且当 2 \times y>x 时，x \bmod y = x-y ，所以我们可以将问题转化为y-x=x \oplus y。

可以发现，对于一位的二进制，当 x_{i}=1 ，y_{i}=1 或 0 ，当 x_{i}=0 ，y_{i} 只能等于 0 ，x 与 y 二进制位数一样，特殊的，为了保证 2 \times y>x ，对于 x 与 y 的第一位，必须都取 1。

我们可以利用数位 dp 解决该问题。

#include<bits/stdc++.h> 
using namespace std;
#define int long long
const int mod=1e9+7;
int dp[66][2][2][2];//dp[i][j][k][l]为，当前处理第i位，x取顶的状态是i，y取顶的状态是j，x，y是否都已取值的状态为l 
int l,r;
int cal(int x,int y){
    for(int i=0;i<=60;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) for(int l=0;l<2;l++) dp[i][j][k][l]=0;
    dp[60][1][1][0]=1; 
    for(int i=59;i>=0;i--){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                for(int l=0;l<2;l++){
                    bool nowj,nowk;
                    if(j==1&&!((x>>i)&1)){
                        nowj=1;
                    }
                    else nowj=0;
                    if(k==1&&!((y>>i)&1)){
                        nowk=1;
                    }
                    else nowk=0;
                    dp[i][nowj][nowk][l]=(dp[i][nowj][nowk][l]+dp[i+1][j][k][l])%mod;
                    if(nowj==0&&nowk==0) dp[i][j][k][1]=(dp[i][j][k][1]+dp[i+1][j][k][l])%mod;
                    if(nowj==0&&l==1) dp[i][j][nowk][l]=(dp[i][j][nowk][l]+dp[i+1][j][k][l])%mod;
                }
            }
        }
    }
    return dp[0][0][0][1]+dp[0][0][1][1]+dp[0][1][0][1]+dp[0][1][1][1];
}
signed main(){
    cin>>l>>r;
    int add=cal(r,r)%mod,add2=cal(l-1,r)%mod,add3=cal(l-1,l-1)%mod,add4=cal(r,l-1)%mod;
    cout<<(add-add2+add3-add4+mod)%mod<<endl;//做二维差分，得出答案 
}