Problem Description
小丁最近对位运算很感兴趣,通过学习,他知道了按位与 ⊗,按位异或 ⊕,以及按位或 ⊖ 三种常见位运算。
按位与 ⊗:二进制下每一位做与,即 0⊗0=0,0⊗1=0,1⊗0=0,1⊗1=1。
按位异或 ⊕:二进制下每一位做异或,即 0⊕0=0,0⊕1=1,1⊕0=1,1⊕1=0。
按位或 ⊖:二进制下每一位做或,即 0⊖0=0,0⊖1=1,1⊖0=1,1⊖1=1。
现在,对于一个在 [0,) 中的整数 𝑛,小丁想要知道,有多少组也在 [0,
) 中的整数 𝑎,𝑏,𝑐,𝑑,满足:𝑎⊗𝑏⊕𝑐⊖𝑑=𝑛
注意,运算符是从左往右依次顺序结合的,即可以认为原表达式为:(((𝑎⊗𝑏)⊕𝑐)⊖𝑑)=𝑛
Input
本题单个测试点内包含多组测试数据。
第一行一个整数 𝑇(1≤𝑇≤10),表示数据组数。
对于每组数据,一行两个整数 𝑛,𝑘(1≤𝑘≤15,0≤𝑛<)。
Output
对于每组数据输出 𝑞 行,每行一个整数表示答案。
核心代码
void solve()
{
int t;
cin >> t;
while (t--) {
int n, k, sum = 0;
cin >> n >> k;
sum = pow(4,k);
int j = 0;
rep(p, 0, 62) {
if ((n >> p) & 1) j++;
}
sum *= pow(3,j);
cout << sum << "\n";
}
图解
以n=1,k=2为例。无论n等于0还是1,a和b都可以任取[0,),所以对于每一位来说,ab有4种组合;
(以下都为单个位数的讨论)
n=0时,d必须为0,(a&b^c)必须为0,故cd只有1种组合
n=1时,d=0,(a&b^c)必须为1;d=1,abc任取,故cd有3种组合
因此,abcd的数据组数为,(cnt1为n中位数为1的个数)