假設 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....我覺得這個資料有些無聊..
#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;
}