Sum Equals Xor_牛客博客

Sum Equals Xor

$Description$
You are given a positive integer $L$ in base two.How many pairs of non-negative integers $(a,b)$ satisfy the following conditions?

$a+b<=L$
$a+b=a\ XOR\ b$

Since there can be extremely many such pairs, print the count modulo $10^9+7$ .

$Solution$
首先假设 $L$ 全是 $1$ 的时候,按相同长度来考虑,根据题意,如果 $a$ 的第 $i$ 位是 $0$ 则 $b$ 的第 $i$ 位必须是 $0$ .
所以答案就是 $\sum_{i=0}^{n}\binom{n}{i}\cdot 2^i=3^n$ .
算一般情况时,统计 $L$ 的前 $i$ 位有 $x$ 个 $1$ ,后面 $n-i$ 位答案就是 $3^{n-i}$ ,前 $i$ 位的有 $2^x$ 种情况,所以答案就是 $2^x\cdot 3^{n-i}$ ,累加起来就好.

$Code$

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf 
#define itn int
using namespace std;
const int N=2e5+5;
const long long mod=1e9+7;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
char s[N];
int main(){
        cin>>(s+1);
        auto ksm=[](ll a,ll b){
                ll ans=1;
                for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
                return ans;
        };
        int n=strlen(s+1);
        ll ans=0;
        int cnt=0;
        for(int i=1;i<=n;i++){
                if(s[i]=='1'){
                        ans=(ans+ksm(2,cnt)*ksm(3,n-i)%mod)%mod;
                        cnt++;
                }
        }
        o((ans+ksm(2,cnt))%mod);
}