n(1<=n<=100000000)头奶牛被关在一排房间中弹琴,琴的类型有m(1<=m<=100000000)种,如果相邻的奶牛使用同样一种琴弹琴的话,就可能造成争吵,问一共有多少种情况发生争吵。答案对100003取模。
时间: 2024-04-18 08:10:42 浏览: 18
假设有 $f_i$ 种方案可以让前 $i$ 头奶牛没有争吵,那么第 $i+1$ 头奶牛可以使用 $m-1$ 种不同的琴,因为不能使用和前一头奶牛相同的琴,所以总方案数为 $(m-1)f_i$。
现在考虑有争吵的方案数,如果第 $i$ 头奶牛和第 $i+1$ 头奶牛使用相同的琴,则第 $i-1$ 头奶牛必须使用和第 $i$ 头奶牛不同的琴,而第 $i+2$ 头奶牛必须使用和第 $i+1$ 头奶牛不同的琴。于是有 $f_{i-2}\times(m-2)\times(m-1)$ 种方案可以满足这种情况,其中 $f_{i-2}$ 表示前 $i-2$ 头奶牛没有争吵的方案数,$(m-2)$ 表示第 $i-1$ 头奶牛可以使用 $m-2$ 种琴,$(m-1)$ 表示第 $i$ 头奶牛和第 $i+1$ 头奶牛可以使用 $m-1$ 种琴。
如果第 $i$ 头奶牛和第 $i+1$ 头奶牛使用不同的琴,则前 $i-1$ 头奶牛没有争吵的方案数为 $f_{i-1}$,因为第 $i-1$ 头奶牛可以使用和第 $i$ 头奶牛不同的琴。同理,第 $i+2$ 头奶牛及以后的方案数为 $f_{n-i-1}$。于是有 $f_{i-1}\times(m-1)\times f_{n-i-1}\times(m-1)$ 种方案可以满足这种情况,其中 $(m-1)$ 表示第 $i$ 头奶牛和第 $i+1$ 头奶牛可以使用 $m-1$ 种琴。
综上所述,总方案数为 $\sum\limits_{i=2}^{n-1}[(m-1)f_i+f_{i-1}\times(m-1)\times f_{n-i-1}\times(m-1)]$。由于 $f_1=1$,可以通过递推计算 $f_i$,时间复杂度为 $O(n)$。这个式子的计算可以用前缀和优化到 $O(1)$。
代码如下:
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![gz](https://img-home.csdnimg.cn/images/20210720083447.png)