2023-01-15
题目传送门
翻译
难度&重要性(1~10):4
题目来源
AtCoder
题目算法
dp/模拟
解题思路
我们都知道,异或是一种不进位的加法,而要想 $ a + b = a \oplus b $ 就不能进位,也就是说每一位不能是 $ ( 1,1 ) $ 就有 $ ( 0,1 ),( 1,0 ),( 0,0 )$ 三种可能。
举例: $ 10 ,11 $ 是不可行的,因为它会进位,而 $ 100,010 $ 就可以。
然后,我们需要让它满足 $ a+b \le L $ 即 $ a \oplus b \le L $ 而我们都知道,比较两个数的大小,是从高位往低位比较的。所以我们只需要保证 $ a \oplus b $ 中第 \(k\) 位小于 \(L\) 前面的一样,后面的位数可以随便填,其方案数为 \(3^{k}\)。因为异或 \(1\) 有两种方案 $ ( 0,1 ),( 1,0 ) $ 所以前面部分方案数为 $ 2^{n-k-1} $。
完成状态
已完成
Code
#include<bits/stdc++.h>
using namespace std;
string s;
long long sum,p[100005],P=1,Mod=1e9+7,len;
int main(){
cin>>s;
p[0]=1;len=s.size();
for(int i=1;i<=len;i++)p[i]=(p[i-1]*3)%Mod;
for(int i=0;i<len;i++)
if(s[i]=='1')
sum=(sum+P*p[len-i-1])%Mod,P=(P*2)%Mod;
sum=(sum+P)%Mod;
cout<<sum;
return 0;
}