100分AC题解 谨慎使用

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int P=1e9+7;
const int M=1005;
int f[M];
int inv[M];
int c[M][M];
int Inv[200005];
int dp[65][M][2];
int t[65];
LL z;

inline int a(int x,int y){return x+y>=P?x+y-P:x+y;}
inline int d(int x,int y){return x-y<0?x-y+P:x-y;}
inline int m(int x,int y){return 1ll*x*y%P;}

inline int qp(int a,int b){
    if(b<0)return 0;
    int res=1;
    a%=P;
    while(b){
        if(b&1)res=m(res,a);
        a=m(a,a);
        b>>=1;
    }
    return res;
}

void init(int n){
    f[0]=1;
    for(int i=1;i<=n;++i)f[i]=m(f[i-1],i);
    inv[n]=qp(f[n],P-2);
    for(int i=n-1;~i;--i)inv[i]=m(inv[i+1],i+1);
    for(int i=0;i<=n;++i){
        c[i][0]=1;
        for(int j=1;j<=i;++j)c[i][j]=m(m(f[i],inv[j]),inv[i-j]);
    }
    Inv[0]=Inv[1]=1;
    for(int i=2;i<=200000;++i)Inv[i]=m(P-P/i,Inv[P%i]);
}

int calc(int n,LL r){
    for(int w=0;w<=60;++w)
        for(int i=0;i<=n;++i)
            dp[w][i][0]=dp[w][i][1]=0;
    memset(t,0,sizeof(t));
    int p=0;
    LL tr=r;
    while(tr)t[p++]=tr%2,tr/=2;
    int k0=z&1;
    for(int i=k0;i<=n;i+=2){
        int g=(i%2)<=t[0];
        dp[0][i/2][g]=c[n][i];
    }
    int zt[65]={0};
    for(int w=0;w<=60;++w)zt[w]=(z>>w)&1;
    for(int w=0;w<60;++w){
        for(int i=0;i<=n;++i){
            for(int j=0;j<2;++j){
                if(!dp[w][i][j])continue;
                int k=zt[w+1];
                for(int x=k;x<=n;x+=2){
                    int s=(i+x)%2;
                    int g;
                    if(s<t[w+1])g=1;
                    else if(s==t[w+1])g=j;
                    else{g=0;continue;}
                    int ni=(i+x)/2;
                    dp[w+1][ni][g]=a(dp[w+1][ni][g],m(dp[w][i][j],c[n][x]));
                }
            }
        }
    }
    int res=0;
    for(int i=0;i<=n;++i){
        for(int j=0;j<2;++j){
            if(!dp[60][i][j])continue;
            int x=i;
            int now=61;
            int g=j;
            while(x){
                int num=x%2;
                if(num<t[now])g=1;
                else if(num>t[now])g=0;
                if(!g)break;
                x/=2;now++;
            }
            if(g)res=a(res,dp[60][i][j]);
        }
    }
    return res;
}

signed main(){
    init(1000);
    int n;LL l,r;
    scanf("%d%lld%lld%lld",&n,&l,&r,&z);
    int ar=calc(n,r);
    int al=l?calc(n,l-1):0;
    int ans=d(ar,al);
    printf("%d\n",ans);
    return 0;
}

T4

20 分

暴力搜索不是 $0$ 的位置的值，然后用组合数计算一下加上 $0$ 的方案数，复杂度是拆分数级别的。

40 分

写一个简单 dp 就行，复杂度 $\mathcal{O}(nr^3)$。

$n=2$

本质上是要求 $\sum_{i=0}^r [l\le (i+ i\oplus z)\le r]$。

考虑在二进制下使用数位 dp 解决问题，如果从高位向低位 dp，很难满足两数之和在 $l\sim r$ 之间这个限制。

在此之前先解决一个问题，如何从低位到高位比较大小？（判断一个数是否大于等于一个已知的数 $x$）

可以用一个 $tag$ 来维护，$tag=1$ 表示在这个数最低的前 $i$ 位时大于等于 $x$ 最低的的前 $i$ 位。

现在新增一位，如果这个数新增的这一位大于 $x$ 新增的这一位，那么 $tag$ 一定为 $1$。

如果相等，则 $tag$ 的值不变，即看最低的前 $i$ 位比较结果。

如果 这个数新增的这一位小于 $x$ 新增的这一位，那么 $tag$ 一定为 $0$。

于是就可以从低位向高位 dp，枚举当前这一位填不填，有没有进位，就可以做到 $\mathcal{O}(\log r)$ 的复杂度。

正解

其实跟 $n=2$ 差不多，无非是有没有进位变成了进位是多少，每次转移枚举 $A$ 中有多少个数当前二进制位为 $1$。

时间复杂度 $\mathcal{O}(n^2\log r)$。