首页分享【XJOI】种花 flower

【XJOI】种花 flower

来源：花匠小妙招时间：2024-11-12 08:10

种花 flower

题目描述

OI太可怕了，我决定回家种田。
我在后院里开辟了一块圆形的花圃，准备种花。种花是一种艺术，通过一定技术手法，花材的排列组合会让花变得更加的赏心悦目，这就是花艺。
当然你知道，我在种田之前是OIer，所以我不懂花艺，只会排列组合。我把花圃从圆心向外画线，分成了N" role="presentation">N块扇形，分别编号为1" role="presentation">1，2" role="presentation">2，3" role="presentation">3.....N" role="presentation">N，再从村里的商店采购了M" role="presentation">M种花。然后我大胆的决定：花圃中的每块只种M" role="presentation">M种花中的一种，相邻的两块不能种同一种花。我反应比较慢，所以我请来了机房里手速最快的强袭黯灭勋章鱼人守卫来帮我，让他试一下每种排列，看看哪种最令人赏心悦目。
有一些人，他们的美丽就在身边，也许就在自己身上，像艺术家一样，他们的眼光独到特别，可就因为他们不是艺术家，他们不被人们认可，被称之为另类。简单真实的事情总可以绽放最鲜艳的花，我欣赏这样的人的心理，当然拒绝粗鲁地对待一切。
正想着，他居然告诉我已经尝试完了。这怎么可能？这可一共有.......多少种方案来着？
众所周知的是，我的智商很低。
我想知道种花的方案一共有几种。

输入格式：

仅一行，包含两个整数，分别为N" role="presentation">N和M" role="presentation">M。

输出格式：

仅一行，包含一个整数，表示方案数。这个数可能很大，你只需要输出这个数对1000000007" role="presentation">1000000007取模的结果。

样例输入：

3 3 样例输出：

6 数据范围：

对于20%的数据，0<N≤5" role="presentation">0<N≤5，1<M≤5" role="presentation">1<M≤5
对于60%的数据，0<N≤500,000" role="presentation">0<N≤500,000
对于100%的数据，0<N≤1018" role="presentation">0<N≤1018，1<M≤109" role="presentation">1<M≤109

时间限制：

空间限制：

128M

提示：

remove!!!

题解

此题的题意就是将m" role="presentation">m种点放到n" role="presentation">n个围成圈的位置里，要求相邻的点不能相同。
我们先假设n" role="presentation">n个位置是一条链，那么方案数就是m(m−1)n−1" role="presentation">m(m−1)n−1。
那么如果是环的话方案数就是m(m−1)n−1" role="presentation">m(m−1)n−1再减去最后一个位置和第一个位置重复的个数就行了。
考虑一下当倒数第二个位置和第一个位置相同的话，因为最后一个位置和倒数第二个位置是不同的，所以这部分的最后一个位置和第一个位置是不会相同的。
当倒数第二个位置和第一个位置不相同的话，倒数第二个位置和第一个位置的每一种不相同的情况下，最后一个位置都会存在和第一个位置一样的情况被计算在m(m−1)n−1" role="presentation">m(m−1)n−1中。
所以方案数就是m(m−1)n−1" role="presentation">m(m−1)n−1减去倒数第二个位置和第一个位置不相同的方案数。
如果F[n]" role="presentation">F[n]表示有n" role="presentation">n个位置时的方案数。
那么F[n]=m(m−1)n−1−F[n−1]" role="presentation">F[n]=m(m−1)n−1−F[n−1]就是方案数的递推方程了。
这里要注意一下：
F[1]=m" role="presentation">F[1]=m是显而易见的。
但是当n=2" role="presentation">n=2时，倒数第二个位置就是第一个位置，所以F[2]=m(m−1)" role="presentation">F[2]=m(m−1)。
题目说0<N≤1018" role="presentation">0<N≤1018，但是递推方程的时间复杂度是O(n)" role="presentation">O(n)的。
所以我们用等比数列求和来优化一下。
得到F[n]=(m−1)n+(m−1)(−1)n" role="presentation">F[n]=(m−1)n+(m−1)(−1)n
接着我们再用快速幂优化后时间复杂度就变成了O(log2n)" role="presentation">O(log2n)。
上代码：

#define mod 1000000007

using namespace std;

long long n,m;

long long ksm(long long x,long long p){

long long s=x,ans=1;

while(p){

if(p&1) ans*=s;

s*=s;

s%=mod;

ans%=mod;

p/=2;

}