假设 k = 5 , n>k , (1,2,3,4,5) -> 1=5,2=4,3任意
(2,3,4,5,6) -> 2=6,3=5,4任意...综合上面的可得出1=3=5,2=4=6
(3,4,5,6,7) -> 3=7,4=6,5任意...综合上面的可得出1=3=5=7,2=4=6
....... 综上可得..奇数位的数应该相同,偶数位的数应该相同
再假设k = 4, n>k (1,2,3,4) - >1=4,2=3
(2,3,4,5) - > 2=5,3=4...综合上面的可得出1=2=3=4=5
(3,4,5,6) -> 3=6,4=5...综合上面的可得出 1=2=3=4=5=6
....... 综上所得..所有的数必须相同
大致的思路有了...但是要注意几个特殊的情况.. 这些情况的造成是因为没有有交集的回文串..不能上下综合得出条件..
例如...k=1的时候..回文串都是独立的....总数是m^n
k=n的时候..回文串只有一个..当然也是独立的...总数是m^((n+1)/2)
k>n的时候...串可以任意了.m^n....我觉得这个数据有些无聊..
Program:
#include<iostream>
#include<stack>
#include<queue>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<cmath>
#define ll long long
#define oo 1000000007
#define MAXN 100005
using namespace std;
int n,m,k;
int POW(ll m,ll n)
{
int i;
ll ans=1;
for (i=1;i<=n;i++) ans=(ans*m)%oo;
return (int)ans;
}
int main()
{
while (~scanf("%d%d%d",&n,&m,&k))
{
if (k>n || k==1) printf("%d\n",POW(m,n));
else
if (k==n) printf("%d\n",POW(m,(k+1)/2));
else
if (k%2) printf("%d\n",m*m);
else
printf("%d\n",m);
}
return 0;
}