题意:
给定一个二进制表示的n,让你找满足如下要求的数对(i,j)的个数
$0 \leqslant j \leqslant i \leqslant n$
$ i & n = i $
$ i & j = 0 $
其中&代表按位与
题解:
打表发现对于单个i满足上述规律的j的数量为$2^{(num \ of \ 0 \ in(i)_2)}$
因此对着n的二进制可以从后往前dp计算每一位能够贡献出多少个i,这些i能够贡献出多少0
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <vector> #include <cstdio> #include <queue> #include <cmath> #include <map> #include <set> using namespace std; typedef long long ll; const int mod=1e9+7; const int maxn=1e5+10; ll num2[maxn]; ll num3[maxn]; char a[maxn]; int main(){ ll t; scanf("%lld",&t); getchar(); num2[0]=num3[0]=1; for(int i=1;i<maxn;i++){ num2[i]=(num2[i-1]*2)%mod; num3[i]=(num3[i-1]*3)%mod; } while(t--){ scanf("%s",a); ll len=strlen(a); ll y,x; y=x=0; ll num=0; for(ll i=len-1;i>=0;i--){ if(a[i]=='1'){ num=(num+(num2[x]*num3[y])%mod)%mod; y++; //printf("%lld %lld %lld \n",num2[x],num3[y],num); } else x++; } num=(num+1)%mod;//只算了i的最高位位1的情况,要算上i==0的情况 printf("%lld\n",num); } return 0; }