题干：

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

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

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

输入描述:

第一行输入一个非负整数M。

N=2M,M≤100N=2M,M≤100

 

即2的M次为N。

输出描述:

一个整数ans，对998244353取模。

示例1

输入

复制

0

输出

复制

1

示例2

输入

复制

71

输出

复制

588378066

 

解题报告：

  写个暴力打表发现，答案就是3^m。

一个题解：

很显然a+b=a|b等式成立的条件是a和b的二进制表示中，在同一位不能全为1
假设现在a+b=a|b，a和b是已知的，且a,b写成二进制均为n-1位数（可含前导零）。那么现在把a,b添加一位数，变成n位数（显然n位数都能从n-1位变过来），如果等式仍要成立的话，那么只有3种情况

a后添0，b后添0
a后添0，b后添1
a后添1，b后添0
也就是说从n-1位数变为n位数，组合的方法数变为原来的3倍，且n=0时答案为1显然。

我的题解：

   其实拆成含有前导零的m位数，考虑每一位，只有分别在(0,0)(0,1)(1,0)的三种情况时满足条件，根据乘法原理，得到答案。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
const ll mod = 998244353;
ll qpow(ll a, ll k) {
	ll res = 1;
	while(k) {
		if(k&1) res = (a*res)%mod;
		k>>=1;
		a = (a*a)%mod;
	}
	return res;
}
int main()
{
	int m;
	cin>>m;
	//ll n = qpow(2,m);
	cout << (qpow(3,m));
//	ll ans = 0;
//	for(ll i = 0; i<n; i++) {
//		for(ll j = 0; j<n; j++) {
//			if(i+j == (i|j)) ans++;
//		}
//	}
//	cout << ans;
	return 0 ;
 }