炫酷數學 

鏈接：https://ac.nowcoder.com/acm/contest/331/J
來源：牛客網
 

時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld

題目描述

小希最近想知道一個東西，就是A+B=A|B(其中|爲按位或)的二元組有多少個。

當然，直接做這個式子對小希來說太難了，所以小希改變了一些條件，她僅想知道其中A,B<N的情況，其中N爲2的冪次。

當然，(A=1,B=0)和(A=0,B=1)被認爲是不同的二元組。

輸入描述:

第一行輸入一個非負整數M。

N=2M,M≤100

 

即2的M次爲N。

輸出描述:

一個整數ans，對998244353取模。

示例1

輸入

 

0

輸出

 

1

示例2

輸入

 

71

輸出

 

588378066

解題思路：直接看或許看不出來什麼，但是如果我們先暴力跑一遍前幾個就會發現一些規律

規律如下

 

 

 

不難發現，這是3的次冪，所以這道題其實就是裸的快速冪而已

#include<stdio.h>
int main()
{
	int m;
	scanf("%d", &m);
	long long int ans = 1, k = 3;
	while(m)
	{
		if(m % 2)
		ans = ans * k % 998244353;
		k = k * k % 998244353;
		m = m / 2;
	}
	printf("%lld\n", ans % 998244353);
}