T4 积木染色

内存限制: 256 Mb时间 : 1000 ms

积木染色

题目描述

有 n块积木排成一排，小爱需要给每块积木染色，颜色有 m 种，请问有多少种方法，能使相邻两块积木的颜色均不相同？

输入格式

输入两个正整数n,m

输出格式

输出满足条件的方案数模10${}^9$+7 的结果

数据范围

对于 30% 的数据，1≤n,m≤10
对于 60% 的数据，1≤n,m≤10${}^4$
对于 100% 的数据, 1≤n≤10${}^{1}5$,1≤m≤10${}^9$

样例数据

输入:
3 2
输出:
2
说明:
合法的染色方案有：{1,2,1} {2,1,2} 

思路1

30分：简单排列组合

#include<bits/stdc++.h>
using namespace std; 
int main() {
   long long n,m,ans;
   cin>>n>>m;
   long long mm,nn;
   mm=m-1;
   nn=n-1;
   for(int i=1;i<=n-1;i++){
   	ans=1;
   	ans=ans*mm;
   }
   long long anss=m*ans;
   cout<<anss<<endl;
   return 0;
} 

思路2

简单推导(60分）

#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
long long n,ans,m;

int main(){
	cin>>n>>m;
	ans=m;
	for(int i=2;i<=n;++i){
		ans*=m-1;
		ans%=mod;
	}
	cout<<ans<<endl;
	return 0;
}

最后

以上就是从容时光最近收集整理的关于2022年上海11月月赛T4积木染色T4 积木染色内存限制: 256 Mb时间 : 1000 ms积木染色题目描述输入格式输出格式数据范围样例数据思路1思路2的全部内容，更多相关2022年上海11月月赛T4积木染色T4内容请搜索靠谱客的其他文章。