HDU - 4990

题目链接:

https://vjudge.net/contest/280104#problem/G

碎碎念：

第一篇博客 ε≡٩(๑>₃<)۶
一开始不知道这题在干什么，网上找了很久，看了很多人的答案，理解后自己写了出来。

代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;

const int maxn = 1e6 + 10;


/*		直接复制题目代码会TLE
		关键是找规律：1 2 5 10 21 42 85.......
		第一个奇数为01， 第二个为101， 第三个为10101 
		当n为奇数：f(n) = 1 + 2^2 + 2^4 + ... + 2^(n-1) = 4^0 + 4^1 + 4^2 + .... + 4^((n-1)/2)  = (2 ^(n+1) - 1) / 3
		当n为偶数： f(n) = 2 * (4^0 + 4^1 + 4^2 + .... + 4^((n-2)/2)) = (2 ^(n + 1) - 2) / 3
 
*/


ll quick_pow(ll a, ll n, ll mod){
	ll ans = 1;
	while(n>0){
		if(n & 1){
			ans = ans * a % mod;
		}
		a = a * a % mod;
		n >>= 1;
	}
	return ans;
}


int main(){

	ll n, m;
	while(scanf("%lld%lld", &n, &m) != EOF){
		ll ans = 0;
		
		if(n & 1){
			ans = (quick_pow(2, n+1, 3 * m) - 1) / 3;			//mod3
		}
		else{
			ans = (quick_pow(2, n+1, 3 * m) - 2) / 3;			//这是由上面推导而来，不可能出现负数 
		}
	
		printf("%lld\n", ans);

	}

	return 0;
}