好久没写博客了。。。停更了不知道多少个月了

题目链接:https://codeforces.com/gym/104053/problem/M

题目大意为：给定一个数字k，然后构建出长度为k的数列，使得数列当中的数字两两异或得出的结果加和最终等于给定的数字n，但是数列中每个数字不得大于给定的数字m。

考虑数位dp，记忆化搜索函数为

ll dfs(int index,int y,int now);

其中，index为m的在二进制下的第多少位，y用于记录当前的k个数字当中有多少个当前位取值还受到上界限制，now为在当前位需要产生多少个1才能将之前位留下来的1消除掉

在当前位可以产生的1的个数为cnt₀,cnt₁(分别代表当前位所有数字0的个数和1的个数)。

本题关键点：在当前位假设需要产生p个1，但是我们只生产了q(q<p)个1出来,那么还需要产生的p-q个1，在低1位则需要(p-q)*2个1来填补

然后我这道题超时过两次，后通过优化剪枝方案通过，剪枝方案如下

if(now<0||((now*1ll)<<(index-1))>((1ll<<index)-1)*(k/2)*(k-k/2)) return 0;

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=1e9+7;
ll n,m,jie[100],inv[100],dp[55][20][81*55];
int k;
int bn[100],bm[100];
ll qpow(ll A,ll B){
    if(B==0) return 1;
    ll tmp=qpow(A,B>>1);
    tmp*=tmp;
    tmp%=MOD;
    if(B&1) tmp*=A;
    return tmp%MOD;
}
ll C(ll A,ll B){
    if(A<B) return 0;
    return ((jie[A]*inv[B])%MOD*inv[A-B])%MOD;
}
ll dfs(int index,int y,int now){
    if(now<0||((now*1ll)<<(index-1))>((1ll<<index)-1)*(k/2)*(k-k/2)){
        return 0;
    }
    if(index==0) return now==0;
    if(dp[index][y][now]!=-1) return dp[index][y][now];
    ll sum=0;
    if(bm[index]){
        for(int i=0;i<=k;i++){
            for(int j=0;j<=min(y,i);j++){
                if(y<j||k-y<i-j) continue;
                sum+=dfs(index-1,j,(now-(k-i)*i+bn[index])*2)*C(y,j)%MOD*C(k-y,i-j)%MOD;
                sum%=MOD;
            }
        }
    }
    else{
        for(int i=0;i<=min(k,k-y);i++){
            if(k-y<i) continue;
            sum+=dfs(index-1,y,(now-(k-i)*i+bn[index])*2)*C(k-y,i)%MOD;
            sum%=MOD;
        }
    }
    return dp[index][y][now]=sum;
}
int main(){
    memset(dp,-1,sizeof(dp));
    jie[0]=1;
    for(int i=1;i<51;i++){
        jie[i]=jie[i-1]*i;
        jie[i]%=MOD;
    }
    for(int i=0;i<51;i++){
        inv[i]=qpow(jie[i],MOD-2);
    }
    scanf("%lld%lld%d",&n,&m,&k);
    int cnt=0;
    while(n){
        bn[++cnt]=n&1;
        n>>=1;
    }
    cnt=0;
    while(m){
        bm[++cnt]=m&1;
        m>>=1;
    }
    cout<<dfs(50,k,0);
    return 0;
}