jdoj 2192 染色问题

题目传送门

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);
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注