baidu A
题意：
求序列头尾为1的情况，中间n-1个数填充小于等于m的序列的个数
解题思路：
我们考虑DP[N]的情况，
比如{1a1a2....an-11}
那么对于从{a1 到 an-2}我们都有m-1种选择，即%5E%7Bn-2%7D)
那么对于{an-1}而言，
我们可能有m-1种选择（即它的前一位为1，最后尾也是1），
也可能是m-2种选择（即它的前一位不为1，最后尾是1）
那么我们先让他乘以(m-2)，
即%5E%7Bn-2%7D*(m-2))
那么少算的地方在哪里呢？当然是漏掉了前一位为1，最后尾也为1的这个情况
也就是{1a1a2...an-31an-11}
而这时候的{an-1}我们实际上已经遍历了m-2种情况，只剩下一种
自然也就剩下了{1a1a2...an-31}这种情况了，是不是发现了DP公式了？
那么我们可以写出DP公式：
DPn=m-1n-2*(m-2)+DPn-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);
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;
}
#百度#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;
}
查看5道真题和解析
