C.And and Pair
题意
给出一个上限n (n非常大用长度1e5的二进制表示)
求出有多少对pair(i,j)满足
答案对1e9+7取模
题解
组合数解法参考
dp解法参考
首先根据题目条件
i&n=i,那么若n的第k位二进制位上为0 ,则i的第k位上必须为0
否则n的第k位上为1,则i的第k位上 可以是1/0
其次i&j=0,那么i的第k位上为0时 j可以为1/0
i的第k位上为1时 j必须为0
由于一定要满足j<=i的数对
所以可以从n的最低位枚举到最高位
若当前n的第k位为1那么将这一位作为i的最高位
若当前n的第k位为0那么跳过，因为i的第k位上为0时 j可以为1/0
那么从第k位到后面出现的第一个1(设此处为s)之间j的二进制都必须为0
否则不满足j<=i的条件
这样就相当于在统计以第s位为i的最高位时的可行数对
当枚举到最高位为k时，统计从最低位到k-1之间有cnt0个0 ,cnt1个1
那么选择可选择的j就有$2^{cnt0}$种(i的第k位上为0时 j可以为1/0, i的第k位上为1时 j必须为0)
剩下的cnt1个1中i选择其中y个位置变为0其他位为1，同时又对应$2^y$ 种 j
所以以k为i的最高位时 有 $2^{cnt0}∑{i=0}^{cnt1}C{cnt1}^{i}2^i$ 对符合要求的(i,j)
这里有一个组合数的等效转换公式$∑{i=0}^{cnt1}C{cnt1}^{i}2^i=3^{cnt1}$ 具体证明可以参考第一个🔗
这样转化就避免了组合数取模求逆元的麻烦
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
const double Pi=acos(-1);
const ll Mod=1e9+7;
ll p2[Max],p3[Max];
int main(){
Turnoff;
int t;cin>>t;
p2[0]=p3[0]=1;
for(int i=1;i<=1e5;i++){
p2[i]=(p2[i-1]*2)%Mod;
p3[i]=(p3[i-1]*3)%Mod;
}
while(t--){
string s;cin>>s;
int cnt1=0,cnt0=0;
ll ans=1;
reverse(s.begin(),s.end());
for(int i=0;i<s.size();i++){
if(s[i]=='1'){
ans=(ans+(p2[cnt0]*p3[cnt1])%Mod)%Mod;
cnt1++;
}
else cnt0++;
}
cout<<ans<<endl;
}
}
|
比起组合数学推公式 ，dp更直观设计三维dp(k,0/1,0/1)
第一维表示现在枚举到第几位，
第二维度表示数对中的i在这一位表示是什么，
第三维度表示的是j在这一位表示的是什么
对于以第k位为i最高位对答案的贡献为+=dp(k,1,0)表示i的第k位为1 ，j的第k位为0的数对有几个
(理由见上面分析)
于是有转移方程
1
2
3
4
5
6
7
8
9
10
11
| if (node[i] == '0') {
f[i][0][0] = ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
f[i][0][1] = ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
}
else {
f[i][1][0] = ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
f[i][0][0] = ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
f[i][0][1] = ((f[i + 1][0][0]) % mod + (f[i + 1][0][1]) % mod + (f[i + 1][1][0]) % mod) % mod;
}
ans += f[i][1][0];
|