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

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

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

当然，直接做这个式子对小希来说太难了，所以小希改变了一些条件，她仅想知道其中A,B<N的情况，其中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

 #include<stdio.h>

 #include<math.h>

 typedef long long ll;

 const int mod=;

 ll m_pow(ll a,ll b) {

     ll tmp=a%mod;

     ll sum=;

     while(b) {

         if(b&) sum=(sum*tmp)%mod;

         tmp=tmp*tmp%mod;

         b>>=;

     }

     return sum;

 }

 int main() {

     int m;

     scanf("%d",&m);

     printf("%lld",m_pow(,m));

     return ;

 }

巴特西

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

最新文章

热门文章