baidu A

题意：

求序列头尾为1的情况，中间n-1个数填充小于等于m的序列的个数

解题思路：

我们考虑DP[N]的情况，

比如{1a₁a₂....a_n-11}

那么对于从{a₁ 到 a_n-2}我们都有m-1种选择，即

那么对于{a_n-1}而言，

我们可能有m-1种选择（即它的前一位为1，最后尾也是1），

也可能是m-2种选择（即它的前一位不为1，最后尾是1）

那么我们先让他乘以(m-2)，

即

那么少算的地方在哪里呢？当然是漏掉了前一位为1，最后尾也为1的这个情况

也就是{1a₁a₂...a_n-31a_n-11}

而这时候的{a_n-1}我们实际上已经遍历了m-2种情况，只剩下一种

自然也就剩下了{1a₁a₂...a_n-31}这种情况了，是不是发现了DP公式了？

那么我们可以写出DP公式：

DP_n=m-1^n-2*(m-2)+DP_n-2

等比数列求和就行了

因为N非常大，所以要用nlogn的方法求等比

代码：

const int MO = 1000000007;
long long m, n;
long long powmod(long long a, long long b)
{
long long c = 1;
while (b>0)
{
if (b % 2 != 0)
c = c*a%MO;
a = a*a%MO;
b = b / 2;
}
return c;
}
long long T(long long m, long long n)
{
if (n <= 1) return 1;
long long TN2 = T(m, n / 2);
if (n % 2 == 0)
{
return (TN2 + powmod(m, n / 2) * TN2) % MO;
}
else
{
return (TN2 + powmod(m, n / 2) * TN2 + powmod(m, n - 1)) % MO;
}
}
int main(){
while (cin >> n >> m) {
if (n == 1) {
cout << "1" << endl;
}
else if (n == 2) {
if (m > 1)
cout << "1" << endl;
else
cout << "0" << endl;
}else{
if (m >= 2) {
ll ans = m - 2;
ll a = (m - 1) * (m - 1);
ll nn = (n - 1) / 2;
ans = T(a, nn);

if (n % 2 == 1)
cout << ans * (m - 1) % MO * (m - 2) % MO << endl;
else
cout << ans * (m - 2) % MO << endl;
//cout << sum(a, nn) << endl;
}
else
cout << "0" << endl;
}
}
return 0;
}