上海市计算机学会竞赛平台2022年11月月赛丙组染色问题
题目描述
𝑛n 个点排成一列，需要给每个点一个颜色，颜色有 𝑚m 种。请问有多少种方法，能使任意相邻两个点的颜色均不相同？
输入格式
两个整数：表示 𝑛n 与 𝑚m
输出格式
单个整数：表示染色方案数模 1,000,000,0071,000,000,007 的余数。
数据范围
- 对于 30%30% 的数据，1≤𝑛,𝑚≤101≤n,m≤10
- 对于 60%60% 的数据，1≤𝑛,𝑚≤100001≤n,m≤10000
- 对于 100%100% 的数据，1≤𝑛≤10151≤n≤1015
- 1≤𝑚≤1091≤m≤109
样例数据
输入:
3 2
输出:
2
说明:
合法的染色方案有：{1,2,1} {2,1,2}
详见代码:
#include<bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long f(long long k, long long p)
{
if(p == 1) return k;
long long t = f(k, p / 2);
if(p % 2 == 0)
{
return (t * t) % mod;
}
else
{
return (((t * t) % mod) * k) % mod;
}
}
int main()
{
long long n, m, ans;
cin >> n >> m;
ans = m * f(m - 1, n - 1) % mod;
cout << ans << endl;
return 0;
}原文地址：https://blog.csdn.net/a121677_/article/details/140207566
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！