C - And and Pair
题意：
问有多少组(i,j)满足要求。
要求为：
0<=j<=i<=n
i&n=i
i&j=0
答案mod 1e9+7
题解：
这个和我的思路时一样的，且讲的更清楚
i&n=i说明n为0的地方，i必须为0；n为1的地方，i随意(两种选择)
i&j=0说明i为1的地方，j必须为0；i为0的地方，j随意(两种选择)
j还要<=i
所以我的思路：
对于一组S：101010
我们从前往后开始扫，第一位为1时，我们可以认为i在这一位是1，对于j的取值，因为j在i为0的地方随便取，后面5位中，最少有3个0，最多有5个0(因为1的位置i是随便取得，i可以选1)
那么对于i为10x0x0（x表示这位有两种情况），我们可以确定j的情况，j为0x?x?x,（x表示有两种选择，?表示要根据i的情况定）
这个情况的答案就是：
0的个数为3个：C20 *23
0的个数为4个：C21 *24
0的个数为5个：C22 *25
求和：
sum=C20 *23+C21 *24+C22 *25
我们把23提出来：
sum=23 (C20 *20+C21 *21+C22 *22)=23 (2+1)2
(用的二项式定理，比赛时没想到：)
(x+1)n= (Cn0 *x0+Cn1 *x1+…+Cnn *xn)
现在将结论推广：
设k为后面0的数量
t为后面1的数量
答案就是sum=2k 3t
遍历字符串，不断更新k和t，然后取和
代码：
#include <bits/stdc++.h>#define ll long long#define maxn 100001using namespace std;const ll mod = 1000000007;ll pow_2[maxn+10],pow_3[maxn+10];ll power(ll a,ll b){ll res = 1;while(b){if(b&1) res = res*a%mod;a = a*a%mod;b>>=1;}return res;}void init(){for(int i=0;i<=maxn;i++){pow_2[i] = power(2,i);pow_3[i] = power(3,i);}}int main(){init();int t;string s;cin>>t;while(t--){ll num0=0,num1=0,sum=0;cin>>s;for(int i=0;i<s.size();i++){if(s[i]=='0') num0++;//0的数量 else num1++;//1的数量 }for(int i=0;i<s.size();i++){if(s[i]=='0'){num0--;//除了最高位0的数量 continue;}else{num1--;//除了最高位1的数量 sum = (sum + pow_2[num0] * pow_3[num1] % mod) % mod;}}cout<<(sum+1) % mod<<endl;}return 0;}
