iven an extremely large non-negative integer nn, you are asked to count the number of pairs (i,j)(i,j) of integers satisfying the following conditions:
0\leq j\leq i\leq n0≤j≤i≤n;
ii & n=in=i; and
ii & j=0j=0.
Here & represents the bitwise AND operator.
For simplicity, the binary representation of nn will be given. Meanwhile, you only need to output the answer modulo (10^9+7)(10
9
+7).
Input
The first line contains an integer T~(1\le T\le 20)T (1≤T≤20) indicating the number of test cases.
Each of the following TT lines contains a string S~(1 \le |S| \le 10^5)S (1≤∣S∣≤10
5
) which is the binary representation of the non-negative integer nn. Note that leading zeros of SS could appear in the input.
Output
For each test case, output a line containing the answer described above modulo (10^9+7)(10
9
+7).
题目大致意思：s是一串0和1的串，i和j满足条件当且仅当i&s==0 和 j&i=0 j<=i<=s 最后问i这样的i和j有几个?
思路：
i&s ==0说明在s的二进制位上有0的部分i只能填1，有1的部分既可以填1也可以填0，i&j =0 在i二进制位中有1的地方j相应位置只能为0，有0的部分可以填1也可以填0，我的想法是枚举每个1的位置，即把当前1的位置当作i的最高位，用前缀和来维护i后面0的个数，那么就可以轻松看出i的选法有2i次，由于乘法原理，我们还要乘上j的选法，我一开始算出来的是C(k,i)*2i次的总和，k代表i后面1的个数，C(k,i)代表k个1中选i个选法然后每个1都有两种，结果发现可以化简成2i*3k，最后别忘记加1，即i和j都取0的时候也是一种选法。最后想说一下为什么是3的k次呢？我的理解是：当s的某一位为1的时候，我们可以分而治之，分类讨论一下，i在该位取1的时候，和取0的时候，取1的时候j只能取0，取0的时候j可以取0和1，所以每一位有1的位置都有3种选法乘起来就行了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=100010;
typedef long long ll;
const int mod=1e9+7;
int qsm(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=(ll)res*a%mod;
a=(ll)a*a%mod;
b>>=1;
}
return res;
}
int sum[N];
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int n=s.size();
s=' '+s;
sum[n+1]=0;
for(int i=n;i>=1;i--)
sum[i]=sum[i+1]+(s[i]=='0');
int res=0;
for(int i=1;i<=n;i++)
{
if(s[i]=='1')
{
res=(1ll*res+(ll)qsm(2,sum[i])*qsm(3,(n-i-sum[i]))%mod)%mod;
}
}
cout<<(res+1)%mod<<endl;
}
return 0;
}
京公网安备 11010502036488号