[排队]
2026-06-05 19:27:56
发布于：上海
6阅读
0回复
0点赞
[排队]
题目描述
老师带着 n 名学生前往小码博物馆参观，由于小码博物馆的的道路比较窄，现在老师让大家排成一列前去参观，每一个学生都一个兴趣爱好，一共有m 种。如果相邻的学生的兴趣爱好相同，就可能发生交头接耳，求有多少种状态可能发生交头接耳。
注意：学生已经排好序列，不需要重新安排顺序
答案对 100,003 取模。
提示
对于 100% 的数据，保证 1≤m≤10
8
，1≤n≤10
12
。
输入格式
输入只有一行两个整数，分别代表兴趣爱好数 m 和学生数 n。
输出格式
输出一行一个整数代表答案。
样例组
输入#1
输出#1
2 3
6
// ans=m^n - m*(m-1)^(n-1)
#include <cstdio>
long long p=0;
long long qu(long long x,long long y){ // 快速幂
if(y==0){ // y为0 递归触底反弹
return 1; // 返回1
}
else{
long long dq=qu(x,y/2);
if(y%2==0){
return ((dq%p)*(dq%p))%p;
}
else if(y%2==1){
return ((dq%p)*(dq%p)*(x%p))%p;
}
}
}
int main(){
long long m=0,n=0;
scanf("%lld %lld",&m,&n);
p=100003;
printf("%lld",(qu(m,n)-(m*qu(m-1,n-1))%p+p)%p);
return 0;
}
这里空空如也
有帮助，赞一个