Description
在一串未打结的项链上(意思就是说项链的左端和右端不相连)，有N颗珠子，你有M种颜色，然后就问你有多少种方法将每一颗珠子都染上颜色，使得任意两颗相邻的珠子的颜色不同。
Input
输入只有一行，三个正整数N、M和P，之间以一个空格隔开。
Output
输出只有一行，表示染色的方法总数模P。
思路：
首先我们看第一个珠子，m种颜色任意一种都可以，再看第二个珠子，因为其颜色不能与前一个珠子颜色相同，所以它有(m-1)种选择，以此类推......,因为一共有(n-1)个珠子有(m-1)种选择，根据乘法原理，最终答案ans=(m* (m-1)^(n-1) )%p。
这道题还是非常好想的，把这道题发上来主要还是因为快速加的板子QAQ
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,m,ans,p;
long long ksj(long long x,long long y)
{
long long sum=0;
while(y)
{
if(y&1)sum=(sum+x)%p;
x=(x+x)%p;
y>>=1;
}
return sum;
}
long long ksm(long long x,long long y)
{
long long nmp=1;
while(y)
{
if(y&1) nmp=ksj(nmp,x)%p;
x=ksj(x,x)%p;
y>>=1;
}
return nmp;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&p);
ans=ksj(m,ksm(m-1,n-1))%p;
printf("%lld",ans%p);
}
