点此看题面
大致题意： 求\(\sum_{x=0}^{a-1}\sum_{y=0}^{b-1}[(x\&y)<k]\)。
数位\(DP\)
显然数位\(DP\)吧。
我们设\(f_{n,f1,f2,f3}\)表示当前处理到第\(n\)位，\(a\)是否卡在上界，\(b\)是否卡在上界，\(k\)是否卡在上界的方案数。
转移时枚举\(a\)和\(b\)这一位的填写状况，就能确定\(k\)这一位的填写状况了。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define LL long long
#define Reg
using namespace std;
int a,b,k;LL f[35][2][2][2];
I LL DP(CI x,CI f1,CI f2,CI f3)//数位DP
{if(!~x) return 1;//若处理完RI l1=f1?a>>x&1:1,l2=f2?b>>x&1:1,l3=f3?k>>x&1:1;//求a,b,k这一位上界if(f[x][f1][f2][f3]) return f[x][f1][f2][f3];LL res=0;//若搜过，直接返回l1&&l2&&l3&&(res+=DP(x-1,f1,f2,f3));//1,1l1&&(res+=DP(x-1,f1,f2&&!l2,f3&&!l3));//1,0l2&&(res+=DP(x-1,f1&&!l1,f2,f3&&!l3));//0,1res+=DP(x-1,f1&&!l1,f2&&!l2,f3&&!l3);//0,0return f[x][f1][f2][f3]=res,res;//记下答案并返回
}
int main()
{RI Tt,i;scanf("%d",&Tt);W(Tt--)scanf("%d%d%d",&a,&b,&k),--a,--b,--k,memset(f,0,sizeof(f)),//读入，清空printf("%lld\n",DP(30,1,1,1));//求解，输出return 0;
}