SRM431 div1 medium

なんかそんなに状態ないんじゃねと思ってメモ化した。
rng_58さんのコードを見るとAが10以上のときは0らしい。

#include <map>

typedef long long LL;
using namespace std;

class MegaCoolNumbers 
{
	public:

		int N,A;
		map<LL,LL> cache;

		LL rec(int pos,int diff,int group,int before)
		{
			LL key=pos;
			key=key*20+diff;
			key=key*2000+group;
			key=key*20+before;

			if(pos==N)
				return (group==A)?1:0;
			else if(cache.find(key)!=cache.end())
				return cache[key];
			else
			{
				LL r=0;
				if(diff<10)
					for(int now=before;now<10;now++)
						if(now-before==diff)
							r=(r+rec(pos+1,diff,group,now))%1000000007;
						else
							r=(r+rec(pos+1,10,group+1,now))%1000000007;
				else
					for(int now=before;now<10;now++)
						r=(r+rec(pos+1,now-before,group,now))%1000000007;
				return cache[key]=r;
			}
		}

		int count(int _N, int _A) 
		{
			N=_N,A=_A;
			LL ans=0;
			cache.clear();
			for(int i=1;i<10;i++)
				ans=(ans+rec(1,10,1,i))%1000000007;;
			return ans;
		}
};