数位 DP

标签：limits int sum cin continue DP dp 数位

2023.1.9 省选模拟赛 I A

【题意】
给定 \(x,y\)，求

\[\sum \limits_{i \in [0, 2^k - x)} \sum \limits_{j \in [y, 2^k)} [i \& j = 0] \times [(i+x) \& (j-y) = 0] \]

\(x,y \le 2^{200000}\)，通过二进制方式给出。
【分析】
首先这个 \(j-y\) 不好处理。应该将其换成 \(j\)，得到这样的比较清楚的柿子：

\[\sum \limits_{i \in [0, 2^k - x)} \sum \limits_{j \in [0, 2^k-y)} [i \& (j+y) = 0] \times [(i+x) \& j = 0] \]

然后我们考虑有加法的话，记录进位即可。令 \(dp_{i, 0/1, 0/1}\) 表示考虑到第 \(i\) 位，\(i+x,j+y\) 下一位分别有没有进位。枚举 \(i,j\) 的取值即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
void cmax(int &x, int y) {if(x < y) x = y;}
void cmin(int &x, int y) {if(x > y) x = y;}
//调不出来给我对拍！
char x[200010],y[200010];
int dp[200010][2][2];
const int mod=1e9+7;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    int n;cin>>n;
    for(int i=n-1;i>=0;i--){cin>>x[i];x[i]-='0';}
    for(int i=n-1;i>=0;i--){cin>>y[i];y[i]-='0';}
    dp[0][0][0]=1;  //x这一维度向右平移
    f(d,0,n-1){
        f(i,0,1)f(j,0,1){
            //枚举i,j这一位的取值。
        //    if(i==1&&j==1)continue;
            f(k, 0, 1) f(l,0, 1) {
                //枚举上一位有没有往前进位。
                if((i+x[d]+k)&j)continue;
                if((j+y[d]+l)&i)continue;
                dp[d+1][(i+x[d]+k>=2?1:0)][(j+y[d]+l>=2?1:0)]+=dp[d][k][l];
                dp[d+1][(i+x[d]+k>=2?1:0)][(j+y[d]+l>=2?1:0)]%=mod;
            }
        }
    }
    cout<<dp[n][0][0]<<endl;
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
}

标签：limits,int,sum,cin,continue,DP,dp,数位
From： https://www.cnblogs.com/Zeardoe/p/17045789.html