题目 Given an extremely large non-negative integer n, you are asked to count the number of pairs (i,j) of integers satisfying the following conditions:
0≤j≤i≤n; i & n=i; and i & j=0. Here & represents the bitwise AND operator.
For simplicity, the binary representation of n will be given. Meanwhile, you only need to output the answer modulo (109+7).
Input The first line contains an integer T (1≤T≤20) indicating the number of test cases.
Each of the following T lines contains a string S (1≤|S|≤105) which is the binary representation of the non-negative integer n. Note that leading zeros of S could appear in the input.
Output For each test case, output a line containing the answer described above modulo (109+7).
题意 给一个二进制数n 求满足 (1)0≤j≤i≤n; (2)i & n=i; (3)i & j=0. 这三个条件的所有数对(i,j)的数量
思路 关于第二个条件，对于n的每个为0的二进制位，i的对应二进制位也应为0。关于第三个条件，对于i的每个位1的二进制位，j的对应二进制位应该为0。得到这两个信息后我们不妨尝试找规律。最后结论为： 对于二进制数n，从右向左数，第i个1，其位于整个数的第k位，其贡献为3i-1+2k-1,答案就是所有的1的贡献加上1(没有算上i和j均为0这个数对)。
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) const int MAXN = 2e5 + 5; const ll mod = 1e9 + 7; int t, n, m, k, flag = 1; string s; ll qukpow_2(int b) { ll x = 2, ret = 1; while(b) { if(b&1) ret = ret * x % mod; x = x * x % mod; b >>= 1; } return ret; } int main(void) { IO; cin >> t; while(t--) { cin >> s; int len = s.size(); ll ans = 1, now = 0; for(int i = len - 1; i >= 0; i--) { if(s[i] == '1') { if(now) { now = now * 3 % mod; ans += now; ans = ans % mod; }else { now = qukpow_2(len - 1 - i); ans += now; ans = ans % mod; } }else { now = now * 2 % mod; } } cout << ans << '\n'; } }