牛客寒假算法基础集训营5 J 炫酷数学

链接：https://ac.nowcoder.com/acm/contest/331/J
来源：牛客网

小希最近想知道一个东西，就是A+B=A|B(其中|为按位或)的二元组有多少个。

当然，直接做这个式子对小希来说太难了，所以小希改变了一些条件，她仅想知道其中的情况，其中N为2的幂次。

当然，(A=1,B=0)和(A=0,B=1)被认为是不同的二元组。

对于这种问题一点都不懂。。。。。

法1：打表找规律 3^m

法2：二进制分析，每一位只有00, 01，10 这3种情况

举例 1+2 == 1|2

1: 0001

2: 0010

0011 == 3

除了那3种还有 11 但是11会进位肯定不等

每一位3种情况共m位因为n=2^m

所以答案为 3^m

 1 #include<stdio.h>
 2 #include<math.h>
 3 typedef long long ll;
 4 const int mod=998244353;
 5 
 6 ll m_pow(ll a,ll b) {
 7     ll tmp=a%mod;
 8     ll sum=1;
 9     while(b) {
10         if(b&1) sum=(sum*tmp)%mod;
11         tmp=tmp*tmp%mod;
12         b>>=1;
13     }
14     return sum;
15 }
16 
17 int main() {
18     int m;
19     scanf("%d",&m);
20     printf("%lld",m_pow(3,m));
21     return 0;
22 }