哪家网站做的好,为何网站需改版,建材网站素材,建设网站的体会链接#xff1a;https://ac.nowcoder.com/acm/problem/14718 来源#xff1a;牛客网
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K 64bit IO Format: %lld
题目描述
一天小明同学拿着m种颜色的油漆去涂…链接https://ac.nowcoder.com/acm/problem/14718 来源牛客网
时间限制C/C 1秒其他语言2秒 空间限制C/C 32768K其他语言65536K 64bit IO Format: %lld
题目描述
一天小明同学拿着m种颜色的油漆去涂刷n块格子在涂刷的过程中他发现有很多种涂色方案并很快的算出了答案然后他发现如果涂好颜色的格子中只要存在某两个相邻的格子颜色一样他就会感到开心他想知道有多少种让他开心的涂刷方案。
输入描述:
输入仅包含一行包含两个数nm分别表示格子数和颜色数。1 n 1e12, 1 m 1e12)
输出描述:
输出一行包含一个整数让小明开心的涂刷方案数。 答案对1000000007取模 一共有 mn个中所有的方案我们只需要减去任意两个相邻的都不相同的即可 考虑第一位可以染色的可能有m种如果第一位染了m种其中一种颜色 那么第二位只有m-1个选择同理第三位还是有m-1个选择 因为第一位的颜色还可以选,所以所有的可能应该为mn−m∗(m−1)n−1,直接快速幂即可 一共有 mn个中所有的方案我们只需要减去任意两个相邻的都不相同的即可考虑第一位可以染色的可能有m种如果第一位染了m种其中一种颜色那么第二位只有m-1个选择同理第三位还是有m-1个选择因为第一位的颜色还可以选,所以所有的可能应该为mn−m∗(m−1)n−1,直接快速幂即可n, m list(map(int, input().split()))MODULE 1000000007
ans pow(m, n, MODULE) - m * pow(m - 1, n - 1, MODULE)
print(ans % MODULE)
