题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5187

Problem Description

As one of the most powerful brushes, zhx is required to give his juniors n problems.
zhx thinks the ith problem's difficulty is i . He wants to arrange these problems in a beautiful way.
zhx defines a sequence {ai} beautiful if there is an i that matches two rules below:
1: a1..ai are monotone decreasing or monotone increasing.
2: ai..an are monotone decreasing or monotone increasing.
He wants you to tell him that how many permutations of problems are there if the sequence of the problems' difficulty is beautiful.
zhx knows that the answer may be very huge, and you only need to tell him the answer module p .

 

 

Input

Multiply test cases(less than 1000 ). Seek EOF as the end of the file.
For each case, there are two integers n and p separated by a space in a line. (1≤n,p≤1018 )

 

 

Output

For each test case, output a single line indicating the answer.

 

 

Sample Input


 

2 233

3 5

 

 

Sample Output


 

2

1

Hint

In the first case, both sequence {1, 2} and {2, 1} are legal. In the second case, sequence {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} are legal, so the answer is 6 mod 5 = 1

题目大意：给出一个n，出现1~n的一个数列，这个数列可以升序再降序，也可以降序再升序，但是只能拐一次弯（或者不拐弯）

问有多少种情况，对q取模

1.取最大数，每个位置i放一次，每个i位置之前有i-1和数，共有C（i-1，n-1）中组合

sum（n）=C（0,n-1）+C(1,n-1)+C(2,n-1)+...+C(n-1,n-1);

利用二项式定理，求出sum（n）=2^(n-1)

2.取最小数，同理。

两项相加，去除重复计算的单增和单减的连个序列

得ans=2^n-2;

对p取模

因为会爆ll，所以进行高精度乘法

高精度乘法：https://blog.csdn.net/qq_40482358/article/details/80038753

ac：

一开始我是用的数组模拟高精度乘法：

//这里我一开始用的是数组模拟，但是我看有大佬直接用了上面得那个 
//于是我也就学习了一波，但是这个还是辛苦写的，就留做纪念把。。。 
ll tack(ll a,ll b,ll mod)
{
	int arr1[50],arr2[50];
	clean(arr1,0);
	clean(arr2,0);
	int k1=0;
	while(a)
	{
		arr1[k1++]=a%10;
		a=a/10;
	}
	int k2=0;
	while(b)
	{
		arr2[k2++]=b%10;
		b=b/10;
	}
	int a1[50];
	int a2[50];
	clean(a1,0);
	clean(a2,0);
	for(int i=k1-1;i>=0;--i)
		a1[k1-i-1]=arr1[i];
	for(int i=k2-1;i>=0;--i)
		a2[k2-i-1]=arr2[i];
	int ans[50];
	clean(ans,0);
	for(int i=0;i<k1;++i)
	{
		for(int j=i;j<k2+i;++j)
		{
			int can=a1[i]*a2[j-i]+ans[j];
			int sum=can%10;
			int temp=can%10;
			ans[j]=sum;
			if(temp)
				ans[j+1]=ans[j+1]+temp;
		}
	}
	int i=49;
	while(ans[i]==0)
		i--;
	ll res=0;
	for(i;i>=0;--i)
		res=(res*10+ans[i])%mod;
	return res;
}

好麻烦。。。有大佬用的更简单得高精度，学习一波，我就换成简单的那个了。。。QAQ

学习后修改的高精度：

#include<stdio.h>
#include<string.h>  
#include<math.h>  
  
#include<map>   
//#include<set>
#include<deque>  
#include<queue>  
#include<stack>  
#include<bitset> 
#include<string>  
#include<iostream>  
#include<algorithm>  
using namespace std;  

#define ll long long  
#define INF 0x3f3f3f3f  
//#define mod 1000000007
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b) 
#define clean(a,b) memset(a,b,sizeof(a))// 水印 
//std::ios::sync_with_stdio(false);

ll tack(ll a,ll b,ll mod)
{
    ll res=0;
    while(b)
    {
        if(b&1) 
			res=(res+a)%mod;
        a=(a+a)%mod;
        b=b>>1;
    }
    return res;
}

ll quick(ll x,ll n,ll mod)
{
	ll res=1;
	while(n)
	{
		if(n&1)
			res=tack(res,x,mod)%mod;
		x=tack(x,x,mod)%mod;
		n=n>>1;
	}
	return res%mod;
}

int main()
{
	ll n,p;
	while(cin>>n>>p)
	{
		/*
		组合数的二项式定理： 
		sigma(c(i,m))=2^m
		(2^n-2)%mod
		*/
		if(p==1)
			cout<<0<<endl;
		else if(n==1)
			cout<<1<<endl;
		else
			cout<<(quick(2,n,p)-2+p)%p<<endl;
	}
}