快速乘+快速幂 板子 zhx's contest

InputMultiply test cases(less than 10001000). Seek EOFEOF as the end of the file.
For each case, there are two integers nn and pp separated by a space in a line. (1≤n,p≤10181≤n,p≤1018)OutputFor 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
        


思路:
标志为 最大最小值 （想到了图像）
所以对于每一个标志 你需要选一些数在 左成为单调 的   右边一定可以成为单调的且方案数为1
所以答案 为 sigema (1->n-1)  C(i)(n-1) 
通过杨辉三角推出 通项公式为 2^n-2;

板子  （快速乘 板子 和快速幂板子有异曲同工之妙）

// 
#include<bits/stdc++.h> 
using namespace std; 
#define ll long long 
ll n,p; 
#define maxnn 100100 
ll ksc(ll a,ll b,ll c)
{
    a=a%c;
    ll ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%c;
        b>>=1;
        a=(a+a)%c;
    }
    return ans;
}
ll ksm(ll a,ll b,ll c)
{
    a=a%c;
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ksc(ans,a,c)%c;
        b>>=1;
        a=ksc(a,a,c)%c;
    }
    return ans;
}
int main()
{
    while(cin>>n)
    {
        cin>>p;
        printf("%lld\n",(ksm(2,n,p)-2+p)%p);
    }
}

快速乘+快速幂 板子 zhx's contest

原文：https://www.cnblogs.com/OIEREDSION/p/11291717.html