学步园

学到了两个东西，一是快速乘法，二是。。。对于取模要考虑到负数情况，若小于零了记得加上p

思路其实好简单。。。。。为什么比赛的时候就是懒得想。。。。。

可以发现，对于最大和最小的两个数，两边的数字取值是任意的且是排列唯一的。对于其他值除了全列升序和降序外没有其他方案了，所以直接看最大数和最小数就好。然后发现这两个数的排列有两种情况会重叠，就是全列升序和全列降序的时候。

#include <stdio.h>
#define ll long long
ll quickmul(ll m,ll n,ll k) //只要把乘号换成加号就好了
{
    ll b=0;
    while(n>0)
    {
        if(n&1)
            b=(b+m)%k;
        n=n>>1;
        m=(m+m)%k;
    }
    return b;
}
ll quickpow(ll m,ll n,ll k)
{
    ll b = 1;
    while (n > 0)
    {
        if (n & 1)
            b = quickmul(b,m,k)%k;
        n = n >> 1 ;
        m = quickmul(m,m,k)%k;
    }
    return b;
}
int main()
{
    ll n,p;
    while(scanf("%lld%lld",&n,&p)!=EOF)
    {
        if(p==1) {printf("0\n");continue;} //这里注意考虑边界情况
        if(n==1) {printf("1\n");continue;} //同上
        ll tmp;
        tmp=quickpow(2,n,p);
        tmp=(tmp-2)%p;
        if(tmp<0) tmp+=p;  //!!!坑点
        printf("%lld\n",tmp);
    }
    return 0;
}