「CODEVS1851」越狱

2014年1月5日3,9570

题目描述 Description

监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱

输入描述 Input Description

输入两个整数M，N.1<=M<=10^8,1<=N<=10^12

输出描述 Output Description

可能越狱的状态数，模100003取余

样例输入 Sample Input

2 3

样例输出 Sample Output

6

数据范围及提示 Data Size & Hint

6种状态为(000)(001)(011)(100)(110)(111)

代码

#include <cstdio>
#include <iostream>
const long long d=100003;
long long n,m;
int pow(long long p,long long k)
{
    long long temp=1,c=p;
    while(k)
    {
        if(k&1)temp=(temp*c)%d;
        c=(c*c)%d;
        k=k>>1;
    }
    return temp;
}
int main()
{
    scanf("%lld%lld",&m,&n);
    long long temp1=(pow(m-1,n-1)*m)%d;
    long long temp2=pow(m,n);
    printf("%lld\n",(temp2-temp1+d)%d);
    return 0;
}

#include <cstdio>

#include <iostream>

const long long d=100003;

long long n,m;

int pow(long long p,long long k)

{

long long temp=1,c=p;

while(k)

{

if(k&1)temp=(temp*c)%d;

c=(c*c)%d;

k=k>>1;

}

return temp;

}

int main()

{

scanf("%lld%lld",&m,&n);

long long temp1=(pow(m-1,n-1)*m)%d;

long long temp2=pow(m,n);

printf("%lld\n",(temp2-temp1+d)%d);

return 0;

}

« NOIP2013转圈游戏「JoyOI1118 – 1119」a^b1 – 2 »

hzwer.com _ Home | http://hzwer.com

「CODEVS1851」越狱

题目描述 Description

输入描述 Input Description

输出描述 Output Description

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

代码

分类目录

热门文章

Myfriends

近期评论