鏈接：https://ac.nowcoder.com/acm/problem/14718
來源：牛客網(wǎng)

時(shí)間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 32768K，其他語言65536K
64bit IO Format: %lld

題目描述

一天小明同學(xué)拿著m種顏色的油漆去涂刷n塊格子，在涂刷的過程中他發(fā)現(xiàn)有很多種涂色方案，并很快的算出了答案，然后他發(fā)現(xiàn)如果涂好顏色的格子中只要存在某兩個(gè)相鄰的格子顏色一樣，他就會感到開心，他想知道有多少種讓他開心的涂刷方案。

輸入描述:

輸入僅包含一行，包含兩個(gè)數(shù)n，m分別表示格子數(shù)和顏色數(shù)。（1 <= n <= 1e12, 1 <= m <= 1e12)

輸出描述:

輸出一行包含一個(gè)整數(shù)，讓小明開心的涂刷方案數(shù)。 答案對1000000007取模

一共有 mn個(gè)中所有的方案，我們只需要減去任意兩個(gè)相鄰的都不相同的即可，
考慮第一位，可以染色的可能有m種，如果第一位染了m種其中一種顏色，
那么第二位，只有m-1個(gè)選擇，同理第三位，還是有m-1個(gè)選擇，
因?yàn)榈谝晃坏念伾€可以選,所以所有的可能應(yīng)該為：mn?m?(m?1)n?1,直接快速冪即可

""" 一共有 mn個(gè)中所有的方案，我們只需要減去任意兩個(gè)相鄰的都不相同的即可，考慮第一位，可以染色的可能有m種，如果第一位染了m種其中一種顏色，那么第二位，只有m-1個(gè)選擇，同理第三位，還是有m-1個(gè)選擇，因?yàn)榈谝晃坏念伾€可以選,所以所有的可能應(yīng)該為：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)

總結(jié)

以上是生活随笔為你收集整理的牛客14718 开心的涂刷的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。