SRM448 div2 hard

メモ化再起。マークでは色なので気をつけてください。

#include <cstring>
#include <string>
#include <vector>

#define MOD 1234567891
typedef long long LL;
using namespace std;

class TheCardLineDivTwo
{
	public:

		int n;
		LL cache[13][2][(1<<16)];
		vector<string> cards;


		char m2n(char c)
		{
			if(c=='S')	return 0;
			if(c=='C')	return 0;
			if(c=='D')	return 1;
			if(c=='H')	return 1;
			return -1;
		}

		char n2n(char c)
		{
			if(c=='A')	return 0;
			if('2'<=c && c<='9')	return c-'1';
			if(c=='T')	return 9;
			if(c=='J')	return 10;
			if(c=='Q')	return 11;
			if(c=='K')	return 12;
			return -1;
		}

		LL rec(char num,char mark,int left)
		{
			LL &r=cache[(int)num][(int)mark][left];
			if(r!=-1)
				return r;
			if(left==0)
				return r=1;
			r=0;
			
			for(int next=0;next<n;next++)
				if( left&(1<<next) && (cards[next][0]==num || cards[next][1]==mark) )
					r=(r+rec(cards[next][0],cards[next][1],left^(1<<next)))%MOD;
			return r;
		}

		int count(vector <string> _cards)
		{
			cards=_cards;
			n=cards.size();
			for(int i=0;i<n;i++)
			{
				cards[i][0]=n2n(cards[i][0]);
				cards[i][1]=m2n(cards[i][1]);
			}
			memset(cache,-1,sizeof(cache));

			LL ans=0;
			for(int i=0;i<n;i++)
				ans=(ans+rec(cards[i][0],cards[i][1],((1<<n)-1)^(1<<i)))%MOD;

			return (int)ans;
		}
};