Artifact Content
Not logged in

Artifact 20f85c4e20ad270e0db6abd1a025bafd319e0122


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

template<typename T>
struct DP3
{
	int N1, N2, N3;
	vector<T> data;
	DP3(){}
	DP3(int N1, int N2, int N3, const T& t = T())
		: N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); }
	T& operator()(int i1, int i2, int i3)
		{ return data[ ((i1*N2)+i2)*N3+i3 ]; }
	void swap(DP3& rhs)
		{ data.swap(rhs.data); }
};

class GameWithGraphAndTree { public:
	vector<string>        graph;
	vector< vector<int> > children;
	vector<int>           subtree_size;

	int calc(vector <string> graph_, vector <string> tree_) 
	{
		int N = graph_.size();

		graph = graph_;
		children.resize(N);
		subtree_size.resize(N);
		computeChildren(-1, 0, tree_);

		memo = DP3<LL>(N,N,1<<N,-1);

		LL answer = 0;
		for(int gv=0; gv<graph.size(); ++gv)
			answer += vertical(0, gv, (1<<N)-1);
		return int(answer % 1000000007);
	}

	void computeChildren(int tparent, int tv, const vector<string>& tree)
	{
		subtree_size[tv] = 1;
		for(int tc=0; tc<tree.size(); ++tc)
			if( tree[tv][tc] == 'Y' && tc!=tparent ) {
				children[tv].push_back(tc);
				computeChildren(tv, tc, tree);
				subtree_size[tv] += subtree_size[tc];
			}
	}

	LL vertical(int tv, int gv, int mask)
	{
		return horizontal(tv, gv, mask&~(1<<gv), 0); 
	}

	DP3<LL> memo;
	LL horizontal(int tv, int gv, int mask, int i)
	{
		if( i == children[tv].size() ) 
			return 1;
		int tu = children[tv][i];

		if( memo(tv,gv,mask) >= 0 )
			return memo(tv,gv,mask);

		LL answer = 0;
		for(int subset=mask; subset; subset=(subset-1)&mask)
			if( __builtin_popcount(subset) == subtree_size[tu] )
				for(int gu=0; (1<<gu)<=subset; ++gu)
					if( graph[gv][gu]=='Y' && ((1<<gu)&subset) )
						answer += vertical(tu, gu, subset) * horizontal(tv, gv, mask&~subset, i+1);

		return memo(tv,gv,mask) = answer % 1000000007;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, GameWithGraphAndTree().calc(graph, tree));}
int main(){

CASE(0)
	string graph_[] = {"NYN",
 "YNY",
 "NYN"};
	  vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 
	string tree_[] = {"NYY",
 "YNN",
 "YNN"};
	  vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_)); 
	int _ = 2; 
END
CASE(1)
	string graph_[] = {"NYNNN",
 "YNYYY",
 "NYNYY",
 "NYYNY",
 "NYYYN"};
	  vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 
	string tree_[] = {"NYNNN", 
 "YNYNN",
 "NYNYN",
 "NNYNY",
 "NNNYN"};
	  vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_)); 
	int _ = 12; 
END
CASE(2)
	string graph_[] = {"NYNNNY",
 "YNYNNN",
 "NYNYNN",
 "NNYNYN", 
 "NNNYNY",
 "YNNNYN"};
	  vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 
	string tree_[] = {"NYNNYN",
 "YNNYNY",
 "NNNNYN",
 "NYNNNN",
 "YNYNNN",
 "NYNNNN"};
	  vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_)); 
	int _ = 0; 
END
CASE(3)
	string graph_[] = {"NYNNYN",
 "YNNYNY",
 "NNNNYN",
 "NYNNNN",
 "YNYNNN",
 "NYNNNN"};
	  vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 
	string tree_[] = {"NNNYYN", 
 "NNYNNN",
 "NYNNYY", 
 "YNNNNN",
 "YNYNNN",
 "NNYNNN"};
	  vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_)); 
	int _ = 2; 
END
CASE(4)
	string graph_[] = {"NYNNNYNNY",
 "YNNNNNNYN",
 "NNNNYYNYY",
 "NNNNNYNNY",
 "NNYNNNYNY",
 "YNYYNNNYN",
 "NNNNYNNYN",
 "NYYNNYYNN",
 "YNYYYNNNN"};
	  vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 
	string tree_[] = {"NNYNNNYYN",
 "NNNNYNNNN",
 "YNNNNNNNN",
 "NNNNNNYNN",
 "NYNNNNNYY",
 "NNNNNNNNY",
 "YNNYNNNNN",
 "YNNNYNNNN",
 "NNNNYYNNN"};
	  vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_)); 
	int _ = 90; 
END
CASE(5)
string graph_[] = {"N"};
	  vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 
	  string tree_[] = {"N"};
	  vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_)); 
	int _ = 1; 
END
CASE(6)
	string graph_[] = {
	"NYYYYYYYYYYYYY",
	"YNYYYYYYYYYYYY",
	"YYNYYYYYYYYYYY",
	"YYYNYYYYYYYYYY",
	"YYYYNYYYYYYYYY",
	"YYYYYNYYYYYYYY",
	"YYYYYYNYYYYYYY",
	"YYYYYYYNYYYYYY",
	"YYYYYYYYNYYYYY",
	"YYYYYYYYYNYYYY",
	"YYYYYYYYYYNYYY",
	"YYYYYYYYYYYNYY",
	"YYYYYYYYYYYYNY",
	"YYYYYYYYYYYYYN"};
	  vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 
	string tree_[] = {
			"NYNNNNNNNNNNNN",
			"YNYNNNNNNNNNNN",
			"NYNYNNNNNNNNNN",
			"NNYNYNNNNNNNNN",
			"NNNYNYNNNNNNNN",
			"NNNNYNYNNNNNNN",
			"NNNNNYNYNNNNNN",
			"NNNNNNYNYNNNNN",
			"NNNNNNNYNYNNNN",
			"NNNNNNNNYNYNNN",
			"NNNNNNNNNYNYNN",
			"NNNNNNNNNNYNYN",
			"NNNNNNNNNNNYNY",
			"NNNNNNNNNNNNYN",
	};
	  vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_)); 
	int _ = 178290591; 
END
CASE(7)
	string graph_[] = {
	"NYYYYYYYYYYYYY",
	"YNYYYYYYYYYYYY",
	"YYNYYYYYYYYYYY",
	"YYYNYYYYYYYYYY",
	"YYYYNYYYYYYYYY",
	"YYYYYNYYYYYYYY",
	"YYYYYYNYYYYYYY",
	"YYYYYYYNYYYYYY",
	"YYYYYYYYNYYYYY",
	"YYYYYYYYYNYYYY",
	"YYYYYYYYYYNYYY",
	"YYYYYYYYYYYNYY",
	"YYYYYYYYYYYYNY",
	"YYYYYYYYYYYYYN"};
	  vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 
	string tree_[] = {
			"NYYYNNNNNNNNNN",
			"YNNNYYYNNNNNNN",
			"YNNNNNNYYYNNNN",
			"YNNNNNNNNNYYYY",
			"NYNNNNNNNNNNNN",
			"NYNNNNNNNNNNNN",
			"NYNNNNNNNNNNNN",
			"NNYNNNNNNNNNNN",
			"NNYNNNNNNNNNNN",
			"NNYNNNNNNNNNNN",
			"NNNYNNNNNNNNNN",
			"NNNYNNNNNNNNNN",
			"NNNYNNNNNNNNNN",
			"NNNYNNNNNNNNNN",
	};
	  vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_)); 
	int _ = 178290591; 
END
CASE(8)
	string graph_[] = {"NYYYYYYYYYYYYY", "YNYYYYYYYYYYYY", "YYNYYYYYYYYYYY", "YYYNYYYYYYYYYY", "YYYYNYYYYYYYYY", "YYYYYNYYYYYYYY", "YYYYYYNYYYYYYY", "YYYYYYYNYYYYYY", "YYYYYYYYNYYYYY", "YYYYYYYYYNYYYY", "YYYYYYYYYYNYYY", "YYYYYYYYYYYNYY", "YYYYYYYYYYYYNY", "YYYYYYYYYYYYYN"};
	  vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 
	string tree_[] = {"NYYYYYYYYYYYYY", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN"};
	  vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_)); 
	int _ = 178290591; 
END
}
// END CUT HERE