cafelier@SRM

SRM474 1000

あとで | 13:29 |

• 大筋ではあってた。submitしたものから
  • メモ化の表をmapからvectorにして7倍速
  • subtreeのノード数と割り当てようとしているグラフのノード数が一致していることのチェックを、グラフノードからルートを割り当てるループより先に回したら4倍速
  • くらいで。まあ後者はそりゃそう書かなきゃだなあ。

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