YACS|2022年11月月赛|丙组 积木染色

题目描述

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

输入格式

输入两个正整数n,m

输出格式

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

数据范围

• 对于 30% 的数据，1≤n,m≤10
• 对于 60% 的数据，1≤n,m≤10^4
• 对于 100% 的数据，1≤n≤10^15,1≤m≤10^9

样例数据

输入:

3 2

输出:

2

说明:

合法的染色方案有：{1,2,1} {2,1,2}

解题：

题意很简单，就是要求m*(m-1)^(n-1)。

1. 循环求解，超时！

2. 直接递归，需要开很大数组，内存超限！

优化思路：

求x^y，先将y转化为二进制。即转化为: x^y = x^(2^0)+ x^(2^1)+...+ x^(2^k) 的问题。

然后，求x^(2^k)的问题时使用记忆化递归实现。

因n<10^15, 则k<50。只需长度50的记忆数组。

代码如下：

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

long long s[55]={0};
int b[55];
int cnt; //二进制位数 
//x^(2^y) 递归 
long long fun(long long x, long long y){
	if(y==0){
		return x;
	}
	if(s[y]) return s[y];
	else{
		s[y] = fun(x,y-1)*fun(x,y-1)%1000000007;
		return s[y];	
	}

}


//十进制转二进制
void OctToBin(long long x){
	cnt=0;
	while(x){
		b[cnt++] = x%2;
		x /= 2;
	}
} 

 
int main() {
	long long n,m, num=0;

	cin>>n>>m;
	
	OctToBin(n-1);

	num = m;
	for(int i=0; i<cnt; i++){
		if(b[i])
			num = num*fun(m-1, i)%1000000007;
	}

	cout<<num;
	return 0;
}