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; } };