ブルーブリッジカップK好数(DP)

この文書は次のとおりです.http://blog.csdn.net/svitter
  アルゴリズムトレーニングK好数 
時間制限:1.0 s  メモリ制限:256.0 MB
      
問題の説明
自然数NのK進数表現のうち任意の隣接する2桁が隣接する数字でない場合,この数はK好数であると述べる.LビットK進数の中でK良い数の数を求めます.例えばK=4,L=2の場合,すべてのK好数は11,13,20,22,30,31,33の計7個である.この数が多いので、1000000007を型抜きした値を出力してください.
入力フォーマット
入力には、2つの正の整数、KおよびLが含まれます.
出力フォーマット
10,000,000,000,007の型取り後の答えの値を示す整数を出力します.
サンプル入力
4 2
サンプル出力
7
データ規模と約定
データの30%に対してKL <= 106;
50%のデータに対してK<=16,L<=10であった.
100%のデータに対して,1<=K,L<=100であった.
ようやくAから水が出てきましたDP==
以上のとおりです.
dp[i][j],iは全部で何桁あるかを表し,jは末尾桁が何桁であるかを表す.状態遷移方程式はdp[i][j]=sum(dp[i-1][p])(p!=j+1&&p!=j-1)である.
コード:

//============================================================================
// Name        : dp.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include <string.h>
#define lln long long int
#define mod 1000000007

int main()
{
	lln dp[110][110];
	int i, j, p;
	int k, l;
	lln sum;
	scanf("%d%d", &k, &l);
	{
		memset(dp, 0, sizeof(dp));
		for (i = 1; i <= k; i++)
		{
			dp[1][i] = 1;
		}
		dp[1][0] = 0;
		for (i = 2; i <= l; i++)
			for (j = 0; j < k; j++)
				for (p = 0; p < k; p++)
				{
					if (p == j - 1 || p == j + 1)//     
						continue;
					dp[i][j] += dp[i - 1][p];
					dp[i][j] = dp[i][j] % mod;
				}
		sum = 0;//         
                for (i = 0; i < k; i++)
		{
			sum += dp[l][i];
			sum %= mod;
		}
		printf("%lld
", sum);

	}
	return 0;
}