看到异或和,大概就是对二进制下每一位分开操作了。
题意大概就是比$k$小的$t=i\operatorname{xor}j$ 的贡献不要了,剩下的贡献减去$k$*剩下的数量。
所以把两个部分分开来看吧。
第一部分其实可以关注比$k$小,如何实现比$k$小?
若在二进制的高位上,$t$已经比$k$小了,那以后的低位无论怎么搞,也不可能大于$k$。
第二部分,剩下的贡献和剩下的数量其实可以一起算。
记$f_{pos,bn,bm,bk}$表示$pos$位上,$bn$表示$n$有没有达到上界,用于枚举状态,$bm$与$bn$类似。
$bk$比$bn$多出来一个用途就是判断第一部分,如果达到上界了,那么意味着当前枚举的状态可能属于第一部分。
对于多组询问,肯定考虑记忆化啦。
状态的继承可以参照代码。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e5+5;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct node
{
ll s,c;
node(ll s=0,ll c=0):s(s),c(c){}
}f[70][2][2][2];bool v[70][2][2][2];int mod;
inline ll add(ll &x,ll y){(x+=y)%=mod;return x;}
inline ll del(ll &x,ll y){(x+=mod-y)%=mod;return x;}
inline int len(ll n){int ans=0;while(n)n>>=1,++ans;return ans;}
ll n,m,k;
node dfs(int pos,int bn,int bm,int bk)
{
if(!pos)return node(0,1);
if(v[pos][bn][bm][bk])return f[pos][bn][bm][bk];
node ans=node(0,0);
bool fn=(n>>(pos-1))&1,fm=(m>>(pos-1))&1,fk=(k>>(pos-1))&1;
for(int i=0;i<=(bn?fn:1);++i)
for(int j=0;j<=(bm?fm:1);++j)//上界限制
{
int t=i^j;
if(bk&&t<fk)continue;
node now=dfs(pos-1,bn&&(i==fn),bm&&(j==fm),bk&&(t==fk));
ans.s=add(ans.s,(1ll<<(pos-1))*t%mod*now.c%mod+now.s);
ans.c=add(ans.c,now.c);
}
v[pos][bn][bm][bk]=1;
return f[pos][bn][bm][bk]=ans;
}
int main()
{
int T;qr(T);
while(T--)
{
memset(v,0,sizeof(v));
qr(n),qr(m),qr(k),qr(mod);n--;m--;
int ret=max(len(n),max(len(m),len(k)));
node ans=dfs(ret,1,1,1);
ll sum=del(ans.s,k%mod*ans.c%mod);
qw(sum);puts("");
}
return 0;
}
最后一次更新于2020-03-21
0 条评论