数位dp——牛客多校H

电玩女神 2023-10-11 09:14 17阅读 0赞

/* x[1,A] y[1,B] x^y<C 或 x&y>C 把ABC拆成二进制后按位进行数位dp dp[pos][s1][s2][f1][f2] 表示从高到低第pos位，条件一状态为s1，条件2状态为s2，x在pos为的限制状态为f1,y在pos的限制状态为f2的方案数 条件状态s=0|1|2表示前pos位数运算结果<C前pos位数,=C前pos位数，>C前pos位数 dp时枚举下一位的所有可能情况，如果当前状态已经确定(满足或不满足)，那么下一位取什么都可以，即下一位的条件状态可以直接继承当前位 反之当前状态不确定，即前pos位的值和C相等，那么需要通过当前为来进行判断下一位的条件状态 终止条件：pos==30 s1==2||s2==0，值为1，反之为0 考虑要减去的情况 x=0,y=[1,min(C-1,B)]都可行 y=0,x=[1,min(C-1,A)]都可行 x=0,y=0也可行 */
    #include<bits/stdc++.h>
    using namespace std;
    #define maxn 35
    #define ll long long
    ll A,B,C,dp[maxn][3][3][2][2];
    vector<int>v1,v2,v3;
     
    ll dfs(int pos,int S1,int S2,int f1,int f2){
        ll &res=dp[pos][S1][S2][f1][f2];
        if(res!=-1)return res;
        if(pos==30){
        //边界条件 
            if(S1==2||S2==0)return res=1;
            else return res=0;
        }
        res=0;
        int newS1,newS2,lim1,lim2;
        lim1=f1?v1[pos]:1;//x下一位的上界 
        lim2=f2?v2[pos]:1;//y下一位的上界 
        for(int i=0;i<=lim1;i++)//枚举xy的下一位 
            for(int j=0;j<=lim2;j++){
                int tmp1=i&j,tmp2=i^j;
                if(S1==1){
        //先处理条件1 
                     if(tmp1==v3[pos])newS1=1;
                     else if(tmp1<v3[pos])newS1=0;
                     else newS1=2;
                }
                else newS1=S1;
                if(S2==1){
                    if(tmp2==v3[pos])newS2=1;
                     else if(tmp2<v3[pos])newS2=0;
                     else newS2=2;
                } 
                else newS2=S2; 
                res=res+dfs(pos+1,newS1,newS2,f1&&(i==lim1),f2&&(j==lim2));
            } 
        return res;
    }
    void calc(ll x,vector<int> & v){ 
        v.clear();
        for(int i=30;i>0;i--){
            v.push_back(x&1);
            x>>=1;
        }
        reverse(v.begin(),v.end());//把数组倒置后就可以正常数位dp了 
    }
    int main(){
        int t;cin>>t;
        while(t--){
            memset(dp,-1,sizeof dp);
            cin>>A>>B>>C;
            calc(A,v1);calc(B,v2);calc(C,v3);
            ll res=dfs(0,1,1,1,1);//进入搜索时的状态
            res-=min(C-1,A)+min(C-1,B)+1;//0取不到，但数位dp时算了 
            cout<<res<<'\n';
        }
    }

转载于:https://www.cnblogs.com/zsben991126/p/11327242.html